policy iteration

A 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. algorithm for a known Markov decision processMarkov decision process, n.: A mathematical description of a step-by-step decision problem: each step you pick an action, receive a reward and then land in a new situation, drawn at random from odds that depend only on the current situation and your choice. that alternates policy evaluation — computing the 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. of the current policypolicy, n.: An AI agent's strategy: the rule it follows to pick an action in each situation. Training in reinforcement learning means improving this rule until it earns high rewards., by solving a linear system or iterating the Bellman expectation equation — with policy improvement, which makes the policy greedy with respect to those values. The policy improvement theorem guarantees that each new policy is at least as good as the last, and because a finite MDP has finitely many deterministic policies, the process reaches an optimal one, usually in very few iterations. Its abstract pattern, which Richard Sutton and Andrew Barto call generalized policy iteration (any interleaving of approximate evaluation and improvement), describes much of 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.: 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. methods, 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. and the search-then-train loop of AlphaZeroAlphaZero, prop. n.: A 2017 DeepMind program that taught itself chess, shogi and Go from nothing but the rules by playing against itself, and within hours of training beat the strongest existing programs. are all instances.

Policy iteration needed only five improvement steps, though each evaluation solved a 10,000-variable linear system.