epsilon-greedy
In plain wordsA simple rule for balancing trying new things against using what works: most of the time take the best-known option, but a small fraction of the time pick at random.
Describing the action-selection rule that, with probability 1 − ε, takes the greedy actionaction, n.: A choice an AI agent makes at one moment — move left, place a stone, type a command — which changes its situation and may earn it a reward. (the one with the highest estimated value) and, with probability ε, takes an action chosen uniformly at random. It is the simplest widely used answer to the exploration–exploitation trade-offexploration–exploitation trade-off, n.: The choice between trying something new that might turn out better and sticking with what already works — like picking a familiar restaurant versus testing a new one.: it ensures that every action keeps being tried, as tabular convergence proofs for Q-learningQ-learning, n.: A trial-and-error method in which an agent keeps a score for every move in every situation and nudges each score toward the reward it got plus the best score available next. and SARSASARSA, n.: A learning method in which an agent updates the score of its last move using the reward it got and the score of the move it actually picks next, so it learns the value of its own habits. require, and it costs no extra computation. In practice ε is annealed — the deep Q-networkdeep Q-network, n.: A method, made famous by DeepMind in 2013–2015, in which a neural network learned to play dozens of Atari video games from screen pixels and the score alone, many at human level. decayed it linearly from 1.0 to 0.1 over the first million frames — and kept small but nonzero during evaluation. Its weaknesses are that exploration is undirected (a nearly optimal and a disastrous action are equally likely to be tried) and dithering (random single steps rarely add up to purposeful journeys), which makes it poor at sparse rewardsparse reward, n.: A situation in which an AI agent gets feedback only rarely — say, only when it finally wins — so it has almost nothing to learn from until it stumbles on success. problems; Boltzmann exploration, optimism, UCBupper confidence bound, n.: A rule for choosing among uncertain options that gives each one a bonus for how little is known about it, so promising but rarely tried options get a fair chance. and Thompson samplingThompson sampling, n.: A way to choose among uncertain options by picking each one about as often as it is likely to be the best, based on everything learned so far. are more targeted alternatives.
We decay epsilon from 1.0 to 0.05 over the first 10 percent of training.
Origin
Randomized near-greedy action selection was in use in RL by the early 1990s, and the name 'ε-greedy' was standardized by Sutton and Barto's textbook (1998). The Greek letter follows the mathematical convention of ε for a small quantity.
Related
- exploration–exploitation trade-offexploration–exploitation trade-off, n.: The choice between trying something new that might turn out better and sticking with what already works — like picking a familiar restaurant versus testing a new one.
- Q-learningQ-learning, n.: A trial-and-error method in which an agent keeps a score for every move in every situation and nudges each score toward the reward it got plus the best score available next.
- deep Q-networkdeep Q-network, n.: A method, made famous by DeepMind in 2013–2015, in which a neural network learned to play dozens of Atari video games from screen pixels and the score alone, many at human level.
- multi-armed banditmulti-armed bandit, n.: A puzzle named after a gambler choosing between slot machines: you must keep picking among options whose payoffs are unknown, learning which is best while wasting as few tries as possible on the others.
- upper confidence boundupper confidence bound, n.: A rule for choosing among uncertain options that gives each one a bonus for how little is known about it, so promising but rarely tried options get a fair chance.
- entropy regularizationentropy regularization, n.: Rewarding an AI agent for keeping some randomness in its choices, so it keeps exploring alternatives instead of locking in on one behavior too early.
- Thompson samplingThompson sampling, n.: A way to choose among uncertain options by picking each one about as often as it is likely to be the best, based on everything learned so far.
Mentioned in
exploration–exploitation trade-offexploration–exploitation trade-off, n.: The choice between trying something new that might turn out better and sticking with what already works — like picking a familiar restaurant versus testing a new one., multi-armed banditmulti-armed bandit, n.: A puzzle named after a gambler choosing between slot machines: you must keep picking among options whose payoffs are unknown, learning which is best while wasting as few tries as possible on the others., Q-learningQ-learning, n.: A trial-and-error method in which an agent keeps a score for every move in every situation and nudges each score toward the reward it got plus the best score available next., SARSASARSA, n.: A learning method in which an agent updates the score of its last move using the reward it got and the score of the move it actually picks next, so it learns the value of its own habits., Thompson samplingThompson sampling, n.: A way to choose among uncertain options by picking each one about as often as it is likely to be the best, based on everything learned so far., upper confidence boundupper confidence bound, n.: A rule for choosing among uncertain options that gives each one a bonus for how little is known about it, so promising but rarely tried options get a fair chance.