Korva is a scroll of the internet’s best ideas.
Explore a little, even when winning
The Lava Maze
Picture a yellow dot in a maze. It has to reach a green exit, and some of the floor is lava. The dot moves up, down, left, or right at random, and each time it falls into a lava pit it keeps a little memory of that and avoids it next time. After enough falls it stumbles onto the exit by luck.
Adding Some Randomness
That run wins the game, but it takes a long, winding route when something close to a straight line would have worked. A dot that sticks to the path it knows never gets a better score. The fix is a small value called epsilon, say 10 percent. Before each move, the program picks a random number. If the number is below epsilon, the dot moves in a random direction. Otherwise it takes the move with the highest value so far.
Some of those random moves land in another lava pit. Repeated over many runs, though, the occasional detour is how the dot finds the shorter path. The same trap shows up at restaurants: someone who loves the first dish they order may never try anything else on the menu, and a better dish could be sitting right there.
Why do learners need to explore at all?
The tension between trying something new and repeating what works is called the explore-exploit tradeoff. Statistician William Thompson studied a version of it in 1933, asking how to split patients between two treatments while the evidence was still coming in. The problem later became known as the multi-armed bandit, after slot machines nicknamed one-armed bandits. Epsilon-greedy, the rule in this story, is one of the simplest known ways to handle it.
Why do some programs shrink epsilon over time?
A learner knows almost nothing at the start, so random moves are cheap and informative. Later they mostly waste effort on routes it has already ruled out. Many programs therefore begin with a high epsilon and lower it as experience builds up. In DeepMind's 2015 Nature paper on Atari-playing programs, epsilon fell from 1.0 to 0.1 over the first million frames.
Why do children explore more than adults?
Psychologist Alison Gopnik has argued that childhood is a period suited to exploration, while adulthood is spent using what has been learned. Her studies with preschoolers found children more willing than adults to test unlikely explanations of how a machine worked. The pattern resembles the schedule used in learning programs, which begin with a high rate of random moves and lower it with experience.
More from CS50
