These are the notes that I took while reading Sutton’s “Reinforcement Learning: An Introduction 2nd Ed” book  and it contains most of the introductory terminologies in reinforcement learning domain. Definitions and equations are taken mostly from the book. Equations are numbered using the same number as in the book too to make it easier to find.
In RL, a learner (or is called an agent in RL terminology) is placed in a poorly understood, possibly stochastic and nonstationary environment. The learner interacts with the environment at discrete time steps. At every time step, the learner can observe and change the environment’s state through its actions. In addition to state changes, the environment responds to the learner’s actions with a reward, a scalar quantity that represents the immediate utility of taking a given action in a given state. The learner’s objective is to develop a policy (a mapping from states to actions) that maximizes its long-term return. (from )
- The learner/decision maker being trained.
- The world outside in agent.
- policy (π)
- The agent’s way of behaving at a given time. Roughly speaking, a policy is a mapping from perceived states of the environment to actions to be taken when in those states.
- Notation for policy.
- Action, decision that the agent makes.
- State St is the representation of environment at time t as captured by agent. This state captures all relevant information from the history.
- Sample sequences of states, actions, and rewards from actual or simulated interaction with an environment.
- Scalar reward Rt+1 that the agent receives from the environment after taking an action. Whereas the reward signal indicates what is good in an immediate sense, a value function specifies what is good in the long run
- reward function
- Reward function is a function r(s,a) that produces the expected reward when taking action a in state s:
- The return Gt is the total discounted expected reward that the agent receives from time-step t until the terminated state T:
Relating to return at successive time:
- discount rate (γ)
- Discount rate, represented by γ, 0 <= γ <= 1, determines how much future return is worth now. The concept is reward that is received in future time steps is worth less than the same reward that is received now.
- value functions
- Functions of states (or of state–action pairs) that estimate how good it is for the agent to be in a given state (or how good it is to perform a given action in a given state), in terms of future rewards that can be expected (i.e. the expected return). Whereas the reward signal indicates what is good in an immediate sense, a value function specifies what is good in the long run.
There are two kinds of value functions:
- state value function (v(s))
- This is one of value functions that is a function of states (v(s)) that estimates how good it is for the agent to be in a given state, in terms of future return that can be expected.
Advanced: see vπ (the state-value function for policy π)
- action value function (q(s,a))
- This is one of value functions that is is a function over state and action (q(s,a)) that estimates how good it is for the agent to perform an action in a given state, in terms of future return that can be expected.
Advanced: see qπ (the action-value function for policy π)
- Model of the environment is something that mimics the behavior of the environment, or more generally, that allows inferences to be made about how the environment will behave. For example, given a state and action, the model might predict the resultant next state and next reward.
Models are used for planning. Methods for solving reinforcement learning problems that use models and planning are called model-based methods, as opposed to simpler model-free methods that are explicitly trial-and- error learners.
- distribution model
- A model that knows the probability of all possible actions from any states. The other kind of model is sample model.
- sample model
- A model where instead of knowing all actions and states (like distribution model), it just returns a sample action every time it is asked what to do in a state.
- model-based learning
- Methods for solving reinforcement learning problems that use models and planning.
- model-free learning
- Learning without knowing the model, by trial and error. This is done by directly performing the action according to some policy and see what happens (i.e. what state the environment moves to and what reward the agent receives from the environment).
- A process to use a model of the environment to produce or improve the policy. The process can be diagrammed as follows:
- greedy (policy)
- A policy to always select action with the highest estimated action value.
This simple policy, however, suffers from exploitation-exploitation dilemma. The ε-greedy and ε-soft policies attempt to rectify this problem by allocating small probability ε to explore less optimal actions.
- exploration-exploitation dilemma
- This is one classic dilemma where an agent must choose between acting greedily by exploiting the most optimal actions to maximize the immediate rewards, and exploring less optimal actions in search for possible better future rewards.
- ε-greedy (policies)
- A policy on which the agent usually acts greedily, but there is ε chance that it acts non-greedily to explore other actions. The ε-greedy policy is an example of ε-soft policy, and is one of the solutions to the exploration-exploitation dilemma in RL.
- soft policy
- Policy that selects all actions in all states with nonzero probability. One example of soft policy is ε-soft policy.
- ε-soft (policies)
- A kind of soft policies for which for all states and actions, for some ε > 0, i.e. given a probability ε > 0, then all actions from all states have at least ε chance of being selected. The ε-greedy policy is an example of ε-soft policy.
Finite Markov Decision Processes
- Finite MDP (Markov Decision Process)
- MDP is formalization of how the agent interacts with the environment in reinforcement learning. The interaction is depicted by the following diagram:
MDP is represented by <S, A, P, R, γ> tuples, where:
- S: finite set of states
- A: finite set of actions, represents all the action that the agent can take
- P: state transition probability matrix, which maps all possible states after state S, along with their probability
- R: reward function, r(s,a), that represents the expected reward when taking action a in state s
- γ: discount factor, . Future rewards can be worth less than the reward that we receive now, so they are discounted.
If we have the MDP, then we know all the states in the environment, and the probability of all possible actions in each of these states, along with the reward and the probability of all possible next states after taking those actions (hint: we usually don’t).
- transition probability matrix
- State transition probability matrix maps all possible states after state S, along with their probability. It is defined as:
- List of steps (the <S, A, R, S’> tuple) from start state (e.g. start of one game session) until terminal state (e.g. end of one game session) in an episodic task.
- A type of interaction between agent and environment that has a clear start state (e.g. the start of a game session) and end state (e.g. end of one game session). The end state is also called terminal state. The list of steps between start and terminal states is called an episode.
Contrast this with continuing type of problems.
- continuing (problem)
- A type of interaction between agent and environment where the interaction is just going on and on without start state and terminal state, unlike episodic interaction.
- The state value function vπ (v pi) is the value of a state s under a policy π, is the expected return when starting in s and following π thereafter:
- The qπ(s, a) function is action-value function for policy π, is the expected return starting from state s, taking action a, and then following policy π thereafter.
- optimal-policy (π∗)
- The optimal-policy, denoted by π∗, is one or more policies that gives return better than or equal to all other policies
- See optimal action-value function
- optimal action-value function (q*)
- One or more action-value functions that are better than all others.
- See optimal state-value function
- optimal state-value function (v*)
- One or more state-value function that is better than all others.
- Bellman expectation equations
- For vπ:
- Bellman optimality equations
- (1) For v*, the value is simply the action-value if we take the optimal action:
(1) For q*, the value is the immediate reward plus discounted proportionally averaged value of all posible states we can land on after taking the action:
(2) And for q*:
- dynamic programming (DP)
- A collection of algorithms that can be used to compute optimal policies given a perfect model of the environment as a Markov decision process (MDP). With dynamic programming (DP), the agent has to visit all states and perform all possible actions on each of these states in order to calculate each and all of the state values and action values and find the optimal policy.
DP is almost never used because they need a perfect model and because they require great computational expense. They are presented here because they provide an essential foundation theories.
- policy evaluation (=prediction problem)
- Iteratively compute vπ, the state-value function for policy π, for all states, until their values converge according to the policy.
- policy improvement
- Establishing new policy that selects new action which yields higher return than previous policy.
- policy iteration
- Doing the following tasks in a loop:
- Perform policy evaluation to calculate value functions for all states based on current policy.
- Perform policy improvement based on the new values to refine the policy.
When policy evaluation is stopped after just one sweep (one update of each state), this algorithm is called value iteration.
- value iteration
- A type of policy iteration where policy improvement is performed after just one sweep of policy evaluation (one update of each state).
- asynchronous dynamic programming
- A kind of dynamic programming where instead of sweeping through all possible transitions, the algorithms update the values of states in any order whatsoever, using whatever values of other states happen to be available. The values of some states may be updated several times before the values of others are updated once. To converge correctly, however, an asynchronous algorithm must continue to update the values of all the states: it can’t ignore any state after some point in the computation.
Example of an asynchronous DP algorithm is real-time dynamic programming.
- generalized policy iteration (GPI)
- A general idea of having an approximate value function and an approximate policy, and continually try to improve each on the basis of the other by means of iterations.
- online (method of calculation)
- The calculation of value functions can be performed at each timestep, i.e. doesn’t have to wait until the end of an episode. As opposed to offline.
- offline (method of calculation)
- The calculation of value functions can only be performed once an episode completes. As opposed to online.
- Operation to shift the value function at particular state (or state-action) toward a “backed-up value” or update target for that state (or state-action). The general form of update rule is:
NewEstimate ← OldEstimate + StepSize [ Target − OldEstimate ] (Eq. 2.4)
Advanced: a notation s → u is also used, where s is the state updated and u is the update target that s’s estimated value is shifted toward. The following are updates for common RL methods:
- expected update
- In a one-step update, all possible next events (states/actions) are considered when calculating current state/action value. The values of next events are weighted according to their probability of occuring. Expected update thus requires a distribution model. Contrast this with sample update.
- sample update
- In a one-step update, only one next state/action value (taken from experience) is considered for calculating current state/action value. Contrast this with expected update.
- Estimate the values of states based on estimates of the values of successor states.
- backward view
- The agent only needs to look at current and prior states/values in order to perform update. Opposite of forward view.
- forward view
- The agent needs to look at few states after current state St in order to perform calculation on St. In practical term, the agent needs to wait until St+n before it can calculate St. See also backward view above.
- credit assignment problem
- If we get a final reward R after doing actions a1, a2, a3 and visiting states s1, s2, s3, which actions/states should we attribute the reward to. (Note: the eligibility trace attempts to solve this)
- Monte Carlo (MC)
- Monte-Carlo is a model free, sample based methods to solve the RL problem based on averaging sample returns. The experience is divided into episodes, where each episode contains time steps/actions. When an episode completes (therefore MC is an offline learning method), value estimates and policies are updated by averaging the sampled returns and the previous average return:
where V(St) is the average return of state St. The equation above is for every-visit Monte Carlo method.
The value function for policy π is the expected return on the state:
- sample based
- Taking actual action in an environment and see what happens, instead of sweeping/knowing all possible actions and rewards.
- on-policy (learning)
- “Learn on the job”. The agent is following the same policy as the policy it is evaluating. Learn about policy π from experience sampled from π.
See also off-policy learning.
- off-policy (learning)
- The agent is following a policy (called behavior policy) that is different than the policy it is evaluating (called target policy). It learns about policy π from experience sampled from μ. It is learning by “looking over someone’s shoulder”.
Off-policy methods are more powerful and general, but are often of greater variance and are slower to converge. See also on-policy learning.
- behavior policy
- The policy that is used by an agent to choose what action to do in a particular state. Contrast this with target policy. If the behavior and target policies are the same then it is called on-policy learning, and if they are different it is called off-policy learning.
- target policy
- The policy that is being evaluated, i.e. its value functions are being calculated, and improved during learning. Contrast this with behavior policy. If the behavior and target policies are the same then it is called on-policy learning, and if they are different it is called off-policy learning.
- temporal difference (TD) learning
- Like Monte-Carlo, it is a model free, sample based methods to solve the RL problem based on averaging sample returns, but using bootstrapping to estimate the value. The experience is divided into episodes, where each episode contains time steps/actions. Unlike MC, TD does not have to wait until the episode completes before making an update (therefore TD is an online algorithm).
On every time step, the algorithm updates the previous state/state action with the reward just received and whatever estimation of state/action value function of current state. If the state updated is the exact previous state, the algorithm is called TD(0), while if the state updated is nth steps before, the algorithm is called n-step TD (advanced).
- TD(0) [one-step TD]
- A kind of TD learning that updates the exact previous state at every time step with the following update:
As a side note, the part inside the square bracket above is called TD-error.
The value function for policy π is:
See also n-step TD (advanced).
- TD-error, represented by δt, is the error in the estimation at a given timestep, i.e. the difference between current estimation and the actual reward and discounted estimation value of next state. Because of this, TD-error is only available one step later.
- Sarsa is an on-policy TD control. It’s named after sequence of S, A, R, S’, A’.
The update rule for one-step Sarsa is:
This update is done after every transition from a nonterminal state St. If St+1 is terminal, then Q(St+1 , At+1 ) is defined as zero.
Algorithm for Sarsa:
Initialize Q(s,a) arbitrarily, Ɐs ϵS, aϵA(s), and Q(terminal state,·)=0 Repeat (for each episode): Initialize S Choose A from S using policy derived from Q (e.g. ϵ-greedy) Repeat (for each step in episode): Take action A, observe R, S' Choose A' from S' using policy derived from Q (e.g. ϵ-greedy)) Q(S,A) <-- Q(S,A) + α[ R + γ Q(S',A') - Q(S,A) ] S <-- S'; A <-- A' until S is terminal
- Q-learning is an off-policy TD control algorithm, defined by:
In this case, the learned action-value function, Q, directly approximates q*, the optimal action-value function, independent of the policy being followed. This dramatically simplifies the analysis of the algorithm and enabled early convergence proofs.
Initialize Q(s,a) arbitrarily, Ɐs ϵS, aϵA(s), and Q(terminal state,·)=0 Repeat (for each episode): Initialize S Repeat (for each step in episode): Choose A from S using policy derived from Q (e.g. ϵ-greedy) Take action A, observe R, S' Q(S,A) <-- Q(S,A) + α[ R + γ maxa Q(S',a) - Q(S,A) ] S <-- S' until S is terminal
- expected Sarsa
- Just like Sarsa, except that instead of the maximum over next state–action pairs it uses the expected value, taking into account how likely each action is under the current policy:
- maximization bias
- Tendency (bias) to select the maximum of the estimated value. For example, given two possible actions, action right which always gives zero, and action left with reward drawn from normal distribution with mean -0.1 and variance 1.0, the agent will choose left because of maximization bias.
The double learning method below can be used to eliminate this.
- double learning
- A learning method to remove maximization bias by dividing the experience in two sets and use them to learn two independent estimates, call them Q1(a) and Q2(a), and use them separately for estimation and control.
- n-step TD
- A kind of TD learning that updates the previous nth state at every time step:
where Gt:t+n is the n-step return as explained below.
When n is 0, the algorithm is called TD(0) which has been explained above.
- n-step return
- The sum of the first n rewards plus the estimated value of the state reached in n steps, each appropriately discounted.
- n-step Sarsa
- n-step method for Sarsa:
- n-step off-policy TD with importance sampling
- Applying off-policy learning to n-step TD (including n=1). This is accomplished by scaling the update with importance sampling or by using tree-backup algorithm (performing expected update to nodes in the episode).
where is called importance sampling and is explained below.
- importance sampling
- A general technique for estimating expected values under one distribution given samples from another, as in off-policy learning methods. When estimating vπ(s) (i.e. state value of s under policy π) from sample of returns taken under behavior policy b, we scale the return with a importance-sampling ratio ρt:T −1:
There are two ways to do importance sampling: ordinary importance sampling and weighted importance sampling. In practice, the weighted importance sampling usually has dramatically lower variance and is strongly preferred.
- Per-decision off-policy methods with control variates
- n-step tree backup algorithm
Planning and Learning with Tabular Methods
- direct reinforcement learning
- Using the experience to find value functions/policy. This is what most RL algorithms do (e.g. Monte Carlo or TD). Contrast this with model learning where the experience is used to learn a model. In Dyna, direct-RL and model-learning is used simultaneously.
- model learning
- Sometimes called indirect reinforcement learning, this is a method to use the experience to learn a model. Contrast this with direct reinforcement learning where the experience is used to learn the value functions/policy. In Dyna, direct-RL and model-learning is used simultaneously.
- indirect reinforcement learning
- See model learning.
- A blend of model-based and model-free learning learning, where the actual experience is used not only to find value or policy (the so called direct RL) but also to learn the model (i.e. model learning), and then using that model to generate more experience to train the agent.
- prioritized sweeping
- Perform updates more effectively in Dyna by generating transitions by focusing on transitions that were most affected (i.e. which values are likely to change the most) by the recent update.
- trajectory sampling
- Distribute updates by sampling from the state (or state–action) space according to some distribution rather than sweeping through the entire state (or state action) as in dynamic programming.
- real-time dynamic programming (RTDP)
- RTDP is an on-policy trajectory-sampling version of DP’s value-iteration algorithm. RTDP is an example of an asynchronous DP algorithm.
- decision-time planning
- Using simulated experience or to consult a model to select an action for the current state. As opposed to background planning where the simulated experience or model is used to improve value functions for all/many states not just current one.
- background planning
- Using simulated experience and feed it to the learning algorithm to gradually improve a policy or value function for all/many states, just just current one.As opposed to decision-time planning.
- heuristic search
- Decision-time planning methods to pick the best action, for each state encountered, considering all possible continuations.
- rollout algorithms
- Decision-time planning algorithms based on Monte Carlo control that generate simulated episodes that start with each possible actions in current state and estimate the action value by averaging them. An action then is chosen, new state is entered, and the process starts again. An example of rollout algorithm is Monte Carlo Tree Search (MCTS)
- Monte Carlo tree search (MCTS)
- A kind of rollout algorithm.
On-policy Prediction with Approximation
- function approximation
- Since the number of states (or state-action) can be very large, it’s often not feasible to store the value-function directly into each state or state-action (the so called tabular method). Therefore a model to approximate the state value function (or action value function) is needed.
There are two kinds of function approximation:
One popular method to train function approximation is using stochastic gradient descent (SGD).
- state value function approximation
- Value approximation for state value. Several kinds of such model can be used, such as:
- linear value function approximation
- non-linear function such as artificial neural network
- Least-Squares TD (LSTD)
- Memory-based function approximation
- Kernel-based function approximation, such as Gaussian radial basis function (RBF) used in RBF function approximation
Training the model is a similar process as in supervised learning, and in this case the prediction objective (VE) function is often used as the objective function for the training. One most widely used training method is stochastic gradient descent (SGD).
- action-value approximation
- Approximating the action value with parametric approximation function q^(s, a, w) ≈ q*(s, a), where w ∈ Rd is a finite-dimensional weight vector.
One popular method to find action-value approximation is using stochastic gradient descent (SGD) for action value.
- prediction objective (VE)
- The prediction objective (VE) is the objective function for learning the state value approximation. It is a Mean Squared Value Error that represents the difference between predicted value by state value approximation and the actual value. The formula is:
where w is the weight vector for the value-function approximation.
The square root of this measure, the root VE, gives a rough measure of how much the approximate values differ from the true values and is often used in plots.
The µ(s) is the state distribution.
- state distribution µ(s)
- State distribution µ(s) is used in prediction objective (VE) calculation to represent how much we care about the error in each state s. For each state, µ(s) ≥ 0, and the sum of µ(s) for all states: ∑s µ(s) = 1. Often µ(s) is chosen to be the fraction of time spent in s.
Under on-policy training this is called the on-policy distribution. In continuing tasks, the on-policy distribution is the stationary distribution under π. In episodic tasks, the on-policy distribution is calculated as follows.
Let h(s) denote the probability that an episode begins in each state s, and let η(s) denote the number of time steps spent, on average, in state s in a single episode. Time is spent in a state s if episodes start in s, or if transitions are made into s from a preceding state s¯ in which time is spent:
This system of equations can be solved for the expected number of visits η(s). The on-policy distribution is then the fraction of time spent in each state normalized to sum to one:
Note that discounting can also be used.
- SGD – stochastic gradient descent
- SGD methods are among the most widely used methods to find approximation function and are particularly well suited to online reinforcement learning.
In gradient-descent methods, the weight vector is a column vector with a fixed number of real valued components, w = (w1, w2, . . . , wd) (or w ∈ Rd), and the state value approximation v^(s,w) (or action value approximation q^(s,a,w)) is a differentiable function of w for all s ∈ S.
We will be updating w at each of a series of discrete time steps, t = 0, 1, 2, 3, …, so we will need a notation wt for the weight vector at each step.
There are two kinds of SGD methods:
- SGD for action value approximation
- Stochastic gradient descent for finding action value approximation.
On each step, we observe a new example St, At → Ut, where Ut can be any approximation of qπ(St, At) such as Monte Carlo return (Gt) or any of the n-step Sarsa returns (see eq 7.4).
The general SGD update for action value prediction is:
For example, SGD update for one-step Sarsa method is:
The equation above is called episodic semi-gradient one-step Sarsa.
The SGD update for n-step semi-gradient Sarsa:
- SGD for state value approximation
- Stochastic gradient descent for finding state value approximation.
On each step, we observe a new example St → vπ(St) (see update) consisting of a (possibly randomly selected) state St and its true value under the policy.
Assume that states appear in samples with the same distribution, µ, over which we are trying to minimize the prediction objective VE.
The SGD update is then defined as follows:
Since we don’t know the true value vπ(St), we replace it with Ut, the approximation to it, which might be a noise-corrupted version of vπ(St), or it might be one of the bootstrapping targets using v^.
This yields the following general SGD method for state-value prediction:
If Ut is an unbiased estimate (e.g. when Ut = Gt from Monte Carlo target), then SGD is guaranteed to converge to a local optimum for decreasing α.
The same guarantee cannot be made if bootstrapping estimate is used as the target Ut. Bootstrapping methods are not in fact instances of true gradient descent. They are called semi-gradient methods.
- linear value-function approximation
- One of the most important special cases of function approximation in which the approximate function, v^(·,w), is a linear function of the weight vector, w. Corresponding to every state s, there is a real-valued vector x(s) = (x1(s), x2(s), . . . , xd(s)), with the same number of components as w.
The linear function approximation is defined as:
the SGD for linear function approximation is then:
- TD fixed point (WTD)
- TD fixed point, WTD, is a weight vector where semi-gradient state value approximation using TD(0) converges to.
TD fixed point is defined as:
TD fixed point can be found by using iteration or directly using Least-Squares TD (LSTD) method.
- Least-Squares TD (LSTD)
- Method to directly compute TD fixed point by computing the estimates for A and b as follows:
where I is the identity matrix, and εI, for some small ε > 0, ensures that At is always invertible.
LSTD estimates the TD fixed point as:
This algorithm is the most data efficient form of linear TD(0), but it is also more expensive computationally.
- semi gradient methods
- In SGD for finding the weight for state value approximation, bootstrapping methods such as TD are not instances of true gradient descent because their target value Ut depends on the weight vector w which values are being learned by the SGD.
They take into account the effect of changing the weight vector wt on the estimate, but ignore its effect on the target. They include only a part of the gradient and, accordingly, they are called semi-gradient methods.
Although semi-gradient (bootstrapping) methods do not converge as robustly as gradient methods, they do converge reliably in important cases such as the linear case.
Example of semi-gradient method is semi-gradient TD(0).
- semi-gradient TD(0)
- Semi-gradient method using TD(0) target as the target update ().
Plugging into equation 9.7, the formula to update the weight hence becomes:
On-policy Control with Approximation
- SGD for action-value prediction
- The general gradient-descent update for action-value prediction is:
where Ut can be any approximation of qπ(St, At), including the usual backed-up values such as the full Monte Carlo return (Gt) or any of the n-step Sarsa returns (7.4)
For example, next is the update for the one-step Sarsa method.
- one-step semi-gradient Sarsa
- SGD for action-value update for one-step Sarsa method is:
The equation above is called episodic semi-gradient one-step Sarsa.
- n-step semi-gradient Sarsa
- The n-step update equation is:
with the return is defined as:
with Gt:t+n = Gt if t + n ≥ T, as usual.
- An MDP is said to have ergodicity property, if you select actions according to π, it remains in the same distribution. It means that where the MDP starts or any early decision made by the agent can have only a temporary effect; in the long run the expectation of being in a state depends only on the policy and the MDP transition probabilities.
- average reward r(π)
- This is the third classical setting—alongside the episodic and discounted settings—for formulating the goal in Markov decision problems (MDPs). Like the discounted setting, the average reward setting applies to continuing problems, problems for which the interaction between agent and environment goes on and on forever without termination or start states. Unlike that setting, however, there is no discounting—the agent cares just as much about delayed rewards as it does about immediate reward.
- differential return
- In the average-reward setting, returns are defined in terms of dierences between rewards and the average reward:
The corresponding value functions are called differential value functions and have the same notations (e.g. vπ(s) = Eπ[Gt | St=s], qπ(s) = .., and similarly for v* and q*).
For the Bellman equations, simply remove all γ and replace all rewards by the difference between the reward and the true average reward.
- average reward semi-gradient Sarsa
- This is the average-reward version of semi-gradient Sarsa:
The equation above is similar to Eq. 10.2, but the TD-error is updated to use the differential version:
where is an estimate at time t of the average reward r(π).
- n-step differential semi-gradient Sarsa
Off-policy Methods with Approximation
- n-step return with approximation
- The general form of n-step return that uses approximation:
- λ-return (lambda-return)
- λ-return is calculated as the average of all n-step returns:
or if the last element is treated separately:
- offline λ-return algorithm
- A learning algorithm based on λ-return:
- eligibility trace
- The eligibility trace is a vector zt ϵ Rd with the same number of components as the weight vector wt, and is calculated as follows:
The eligibility trace is used to keep track of which components of the weight vector have contributed, positively or negatively, to recent update. It is set to zero at the beginning of an episode (z-1 = 0), then updated by the gradient on each time step, then fades away by γλ.
This eligibility trace is also called accumulating trace, to distinquish it from other kind of eligibility trace such as the dutch trace defined by eq. 12.11.
- An offline TD(λ) algorithm is defined as follows:
In the equation above, the weight vector is updated at each step proportional to the eligibility trace vector and the scalar TD-error below:
- truncated λ-return
- The λ-return above is limited because one needs to wait until the end of episode. On the other hand, the reward gets weaker as the episode gets longer due to γλ. Therefore it seems like a good idea to truncate the reward of this long episode down to certain length.
The truncated λ-return for time t, given data only up to some later horizon, h, is defined as as:
- TTD(λ) – truncated TD(λ)
- The truncated TD(λ) or TTD(λ) is defined as:
- online λ-return
- The online λ-return is currently the best performing temporal-difference algorithm. The idea is that, on each time step as a new increment of data is gathered, you go back and redo all the updates since the beginning of the current episode. The new updates will be better than the ones you previously made because now they can take into account the time step’s new data.
- true online TD(λ)
- The true online TD(λ) for linear case in which :
where δt is defined as in TD(λ) in eq. 12.6 and zt is defined by:
This algorithm has been proven to produce exactly the same sequence of weight vectors as the on-line λ-return algorithm above.
- offline λ-return for action value
- The action-value form of the off-line λ-return algorithm (12.4) simply uses q^ rather than v^:
- Sarsa(λ) has the same update rule as given earlier for TD(λ):
except, naturally, using the action-value form of the TD error:
and the action-value form of the eligibility trace:
- true online Sarsa(λ)
- There is also an action-value version of our ideal TD method, the online λ-return. Just replace the state value function with action-value form of the n-step return. In the case of linear function approximation, the ideal algorithm again has an exact, efficient O(d) implementation, called True Online Sarsa(λ).
Pseudo-code is given in the book.
- Watkins’s Q(λ)
- Watkins’s Q(λ) extends Q-learning to eligibility traces.
- Eligibility trace version of Tree Backup.
- GTD(λ) is the eligibility-trace algorithm analogous to TDC, the better of the two state-value Gradient-TD prediction algorithms.
- GQ(λ) is the Gradient-TD algorithm for action values with eligibility traces.
- HTD(λ) is a hybrid state-value algorithm combining aspects of GTD(λ) and TD(λ).
- emphatic TD(λ)
- Emphatic TD(λ) is is the extension of the one-step Emphatic-TD algorithm to eligibility traces.
Policy Gradient Methods
All the previous methods have learned the values of actions and then selected actions based on their estimated action values. In this chapter, we instead learn a parameterized policy that can select actions without consulting a value function.
We use the notation θ ϵ Rd’ for the policy’s parameter vector. If a method uses a learned value function as well, then the value function’s weight vector is denoted w ϵ Rd as usual, as in vˆ(s,w).
Given J(θ) defined as a performance measure with respect to the policy parameter, the policy gradient methods seek to maximize performance, so their updates approximate gradient ascent in J:
- REINFORCE: Monte Carlo policy gradient
- Reinforce update:
- REINFORCE with baseline
- Generalization of REINFORCE algorithm to include a comparison of the action value to an arbitrary baseline b(s):
The baseline b(s) could be anything, including zero. One natural choice for the baseline is an estimate of the state value, vˆ(St,w), where w ϵ Rm is a weight vector learned by one of the methods presented in previous chapters. It also seems natural to use a Monte Carlo method to learn the state-value weights, w.
- For a one-step actor-critic method, the update is fully online and incremental, yet avoid the complexities of eligibility traces. One-step actor–critic methods replace the full return of REINFORCE (13.9) with the one-step return (and use a learned state-value function as the baseline) as follows:
where δt is:
The natural state-value-function learning method to pair with this is semi-gradient TD(0). The one-step actor critic above can be extended to n-step methods and then to a λ-return algorithm.
- policy gradient for continuing problems
- For continuing problems (without episode boundaries), the performance needs to be defined in terms of the average rate of reward per time step.
- policy parameterization for continuous actions
- This is where we have infinite number of actions.
- Reinforcement Learning: An Introduction, Sutton, Barto, 2018
- Function Approximation via Tile Coding: Automating Parameter Choice, Sherstov, Stone