Q-learning
In plain wordsA 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.
An off-policyoff-policy, adj.: Describes learning that can use experience produced by some other strategy — an older version, a human, a different program — while improving the current one., model-freemodel-free reinforcement learning, n.: Learning to act well purely from trial and error, without ever building an internal picture of how the world works — like learning a game by habit rather than by thinking moves ahead. temporal-differencetemporal difference learning, n.: A way of learning predictions by adjusting each guess toward the next, slightly better-informed guess instead of waiting for the final outcome — like revising a weather forecast every day as the date approaches. algorithm that learns the optimal action-value functionQ-function, n.: A score for each possible move in each situation, estimating how well things will turn out, in rewards, if the AI agent makes that move now and sticks to its usual strategy afterward. Q* directly from experience. After taking 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. a in statestate, n.: A snapshot of the situation an AI agent is in — for a chess program, the arrangement of pieces and whose turn it is — containing what it needs to decide what to do next. s and observing reward r and next state s′, it moves Q(s, a) toward r + γ max Q(s′, a′) — the value of acting optimally from then on — whatever action the agent actually takes next. Because this target does not depend on the behavior policy, the agent can explore freely (for example ε-greedilyepsilon-greedy, adj.: A 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.) or learn from old or someone else's data while still estimating the greedy policy's values. Christopher Watkins and Peter Dayan proved that tabular Q-learning converges given sufficient exploration and suitably decaying step sizes. The max operator causes overestimation bias, which double Q-learning corrects; with neural networks the method becomes 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..
Plain Q-learning solved the gridworld, but the Atari version needed replay and a target network.
Origin
Introduced by Christopher Watkins in his 1989 University of Cambridge PhD thesis, 'Learning from Delayed Rewards'; the convergence proof appeared with Peter Dayan in 'Q-learning' (Machine Learning, 1992). Stevo Bozinovski's crossbar adaptive array (1981) is sometimes cited as a forerunner. Hado van Hasselt introduced double Q-learning at NIPS 2010.
Related
- Q-functionQ-function, n.: A score for each possible move in each situation, estimating how well things will turn out, in rewards, if the AI agent makes that move now and sticks to its usual strategy afterward.
- 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.
- 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.
- temporal difference learningtemporal difference learning, n.: A way of learning predictions by adjusting each guess toward the next, slightly better-informed guess instead of waiting for the final outcome — like revising a weather forecast every day as the date approaches.
- off-policyoff-policy, adj.: Describes learning that can use experience produced by some other strategy — an older version, a human, a different program — while improving the current one.
- epsilon-greedyepsilon-greedy, adj.: A 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.
- experience replayexperience replay, n.: Storing an AI agent's past experiences in a memory bank and repeatedly learning from random samples of them, rather than only from what just happened.
- 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.
Sources
- Watkins, C. J. C. H. (1989). Learning from Delayed Rewards. PhD thesis, University of Cambridge.
- Watkins, C. J. C. H. & Dayan, P. (1992). Q-learning. Machine Learning 8, 279–292.
- van Hasselt, H. (2010). Double Q-learning. Advances in Neural Information Processing Systems 23.
Mentioned in
reinforcement learningreinforcement learning, n.: A way of teaching a computer program by trial and error: it tries actions, earns points for good results and penalties for bad ones, and gradually learns which choices pay off over time., action spaceaction space, n.: The full menu of moves an AI agent is allowed to make — a handful of buttons in a video game, or any combination of motor forces for a robot arm., actor–criticactor–critic, n.: A way of training an AI agent in which one part, the 'actor', makes the moves while another, the 'critic', learns to predict how well they will work out, and the actor improves by heeding the critic., Bellman equationBellman equation, n.: A rule saying that how good a situation is equals the reward you get now plus how good the next situation is, slightly discounted — so long-term planning can be solved one step at a time., bootstrapbootstrap, n.: Estimating how much a result might vary by repeatedly re-drawing samples, with replacement, from the data you already have — like re-running a study many times without collecting new data., 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., dynamic programmingdynamic programming, n.: A problem-solving method that breaks a big problem into smaller overlapping pieces, solves each piece once and reuses the answers — the basis for computing the best long-term strategy step by step., epsilon-greedyepsilon-greedy, adj.: A 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., experience replayexperience replay, n.: Storing an AI agent's past experiences in a memory bank and repeatedly learning from random samples of them, rather than only from what just happened., model-free reinforcement learningmodel-free reinforcement learning, n.: Learning to act well purely from trial and error, without ever building an internal picture of how the world works — like learning a game by habit rather than by thinking moves ahead., off-policyoff-policy, adj.: Describes learning that can use experience produced by some other strategy — an older version, a human, a different program — while improving the current one., policy gradientpolicy gradient, n.: A family of methods that improve an AI's strategy directly: make actions that led to good results a bit more likely, and actions that led to bad results a bit less likely., Q-functionQ-function, n.: A score for each possible move in each situation, estimating how well things will turn out, in rewards, if the AI agent makes that move now and sticks to its usual strategy afterward., Richard BellmanRichard Bellman, prop. n.: An American mathematician who invented dynamic programming, a way of solving long chains of decisions step by step, which became the mathematical core of reinforcement learning., temporal difference learningtemporal difference learning, n.: A way of learning predictions by adjusting each guess toward the next, slightly better-informed guess instead of waiting for the final outcome — like revising a weather forecast every day as the date approaches., value functionvalue function, n.: An estimate of how promising a situation is for an AI agent, judged by the rewards it is likely to collect from that point on, the way a chess player sizes up a board., Chris WatkinsChris Watkins, prop. n.: A British computer scientist who invented Q-learning in 1989, a simple way for an agent to learn which action is best in each situation purely from trial and error., deep deterministic policy gradientdeep deterministic policy gradient, n.: A method for teaching AI agents smooth, precise movements, such as controlling a robot arm, by learning a scoring network for actions and steering a decision network toward higher scores., DynaDyna, prop. n.: An early design in which a learning agent builds a model of its world from real experience, then also practices on imagined experience from that model, squeezing more learning out of each real step., Q*Q*, prop. n.: The code name of an internal OpenAI research project, reported in late 2023, said to let AI solve math problems it had never seen. Later reports linked it to OpenAI's first reasoning model, o1., safe interruptibilitysafe interruptibility, n.: A property of a learning AI meaning that people can halt or redirect it as often as needed without those stops shaping what it learns, so it learns neither to dodge them nor to invite them., 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., target networktarget network, n.: A slowly updated copy of an AI agent's learning network, used to compute the goals it learns toward, so those goals do not shift every time the network changes., value iterationvalue iteration, n.: A step-by-step method for finding the best strategy when all the rules and rewards of a problem are known: repeatedly re-score every situation from the scores of the situations it can lead to, until the scores stop changing.