SARSA
In plain wordsA 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.
An on-policyon-policy, adj.: Describes learning that uses only experience produced by the strategy currently being trained, so old data must be thrown away each time the strategy changes. 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. control algorithm that learns the 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. of the policy it is following. Its name lists the quintuple used in each update — State, Action, Reward, next State, next Action: after moving from (s, a) to s′ with reward r and choosing a′ by the current policy, it moves Q(s, a) toward r + γQ(s′, a′). Because the target uses the action actually taken rather than the greedy one, SARSA accounts for the cost of exploration: on the textbook cliff-walking gridworld with an ε-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. policy it learns a safer route away from the edge, whereas 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. learns the shorter edge path and falls off more often while exploring. It converges to an optimal policy if exploration decays appropriately. Expected SARSA replaces Q(s′, a′) with its average under the policy, reducing variance.
SARSA kept the robot away from the stairs because its own random exploration made the edge risky.
Origin
Proposed by Gavin Rummery and Mahesan Niranjan in a 1994 Cambridge University Engineering Department technical report, 'On-line Q-learning using connectionist systems', under the name 'modified connectionist Q-learning'. The acronym SARSA was suggested by Richard Sutton, noted in a footnote, and became standard through his textbook with Andrew Barto.
Related
- 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.
- on-policyon-policy, adj.: Describes learning that uses only experience produced by the strategy currently being trained, so old data must be thrown away each time the strategy changes.
- 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.
- 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.
- 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.
- eligibility traceeligibility trace, n.: A fading short-term memory of which situations and actions an agent recently experienced, so that when a reward arrives the credit can be shared among the steps that led to it.
- 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.
Sources
- Rummery, G. A. & Niranjan, M. (1994). On-line Q-learning using connectionist systems. Technical report CUED/F-INFENG/TR 166, Cambridge University Engineering Department.
Mentioned in
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., 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., on-policyon-policy, adj.: Describes learning that uses only experience produced by the strategy currently being trained, so old data must be thrown away each time the strategy changes., 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., 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., 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., eligibility traceeligibility trace, n.: A fading short-term memory of which situations and actions an agent recently experienced, so that when a reward arrives the credit can be shared among the steps that led to it., policy iterationpolicy iteration, n.: A method for finding the best strategy in a fully known problem by alternating two steps: work out how good the current strategy is, then switch to better choices wherever possible, until nothing improves., 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.