Our objective in solving and MDP is to maximize the expected value of what is called the discounted future return.
$$\begin{flalign} G_t & \doteq \sum_{k=0}^\infty \gamma^k R_{t+k+1} \text{ or } \sum_{k = t+1} ^ T \gamma^{k-t-1}R_k \tag{3.8/3.11} \\ &= R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots \\ &= R_{t+1} + \gamma \left [ R_{t+2} + \gamma R_{t+3} + \cdots \right ] \\ &= R_{t+1} + \gamma G_{t+1} \tag{3.9} \end{flalign}$$
where $0 \lt \gamma \le 1$ in general and $0 \lt \gamma \lt 1$ for continuing tasks that do not have a terminal state.
The recursive expression for $G_t$ is important to defining our approach to solving the problem. Given a specific policy $\pi$ and an environment with a state space $\mathcal{S}$, we can define the value function for a policy as follows:
$$\begin{flalign} v_\pi(s) &\doteq \mathbb{E}_\pi [G_t \mid S_t = s] \tag{3.12}\\ &= \sum_a \pi(a \vert s) \mathbb{E}_\pi [G_{t} \mid S_t = s, A_t = a] \tag{exp value def} \\ &= \sum_a \pi(a \vert s) q_\pi(s, a) \tag{by definition of q (1)} \\ &= \sum_a \pi(a \vert s) \sum_{s^\prime, r} p(s^\prime, r \vert s, a) [r + \gamma v_\pi(s^\prime)] \tag{by (4.6) (3.14)}\\ q_\pi(s, a) &\doteq \mathbb{E}_\pi[G_t \mid S_t=s,A_t=a] \tag{3.13} \\ & = \mathbb{E}_\pi \left [ R_{t+1} + \gamma G_{t+1} \mid S_t = s, A_t = a \right ] \tag{by (3.9)} \\ & = \sum_{s^\prime, r} p(s^\prime, r \vert s, a) \mathbb{E}_\pi \left [ r + \gamma G_{t+1} \mid S_{t+1} = s^\prime \right ] \tag{exp value def}\\ & = \sum_{s^\prime, r} p(s^\prime, r \vert s, a) \left [ r + \gamma \mathbb{E}_\pi [G_{t+1} \mid S_{t+1} = s^\prime] \right ] \\ & = \sum_{s^\prime, r} p(s^\prime, r \vert s, a) [r + \gamma v_\pi(s^\prime)] \tag{by definition of v (4.6)} \\ & = \sum_{s^\prime, r} p(s^\prime, r \vert s, a) [r + \gamma\sum_{a^\prime} \pi(a^\prime \vert s^\prime) q_\pi(s^\prime, a^\prime)] \tag{by (1)} \\ \end{flalign}$$
Since we can enumerate all of the states and actions, it is convenient to refer to states and actions with a numerical index. The following functions create a lookup table from a list of states or actions. For tabular problems all references to states and actions will use these indices.
Selected Action
Select reward for secondary goal:
Select Discount Rate for State Policy Iteration:
Use Wind:
Use Stochastic Wind:
Continuing Task:
An agent is often defined by a specific policy $\pi(a\vert s) = \text{Pr} \{A_t = a \mid S_t = s \}$ which defines the probabilities of taking an action given a state. If there are multiple actions with non-zero probability for a given state, then this is a stochastic policy. To handle stochastic policies in general, a generic policy can be defined as matrix of probabilities where each column represents the action distribution for the state represented by the column index. Defining a policy like this takes advantage of the fact that we can enumerate all the state action pairs and thus represent them with a numerical index. An agent following such a stochastic policy will sample from the action distribution every time it encounters a state.
Code implementing the concepts as well as examples executing that code is interspersed throughout the document. Any section containing code and examples will be italicized to distinguish it from other notes.
Often times, we visualize these trajectories with diagrams where open circles represent states, closed circles represent actions, and squares represent terminal states if they exist. Even if an environment is stochastic a trajectory will have a single path as shown below. For a deterministic environment, this path will represent the only possible trajectory given those actions.
The following code implements policy iteration in the tabular case where the full probability transition function is available. In this case, state values are sufficient, but one can also use state-action values with policy iteration.
So far we presented two extreme cases of generalized policy iteration. In the first case, policy iteration, we accurately compute a policy value function, and then update the policy to be greedy with respect to it. In value iteration, we skip defining a policy altogether and just use the Bellman optimality operator to iteratively compute the optimal value function. In general, we can use the Bellman operator to compute a value function for a policy that is not yet optimal and stop before that value function has converged. Then our policy improvement step is not basing the new policy on an accurate version of the current value function, but we can continue to apply policy evaluation to the updated policy. In this procedure, the policy evaluation is constantly playing catchup to the ever changing policy by chasing a moving target, but that target will stop moving once we reach the optimal policy. It turns out that proceding with partial value function updates will still eventually converge to the optimal policy, and we can choose to wait until the value function is fully converged, dispense with it altogether, or anything in between. This family of procedures all follow the same pattern and are known as generalized policy iteration.
Analogous to the previous Bellman equations, (3.19) and (3.20) are known as the Bellman optimality equations for the state and state-action value functions. Every optimal policy will share the value function that has this property. We can verify if a particular value function is optimal by checking whether it satisfies the Bellman optimality equation, but we also want methods to compute this function just like we did for a given policy. In fact, our ability to compute the value function for a set policy can be used to derive the optimal value function. This process is known as policy improvement.
mimetext/htmlrootassigneelast_run_timestampA6^persist_js_state·has_pluto_hook_features§cell_id$4f0f052d-b461-4040-b5ff-46aac74a24dedepends_on_disabled_cells§runtime kpublished_object_keysdepends_on_skipped_cellsçerrored$1188e680-cfbe-417c-ad61-83e145c39220queued¤logsrunning¦outputbodyDeterministic Gridworld Converged after 1080 iterations
We seek to find the optimum behavior for an agent interacting with an environment. To properly define an environment we must first define the state space $s \in \mathcal{S}$ and the action space $a \in \mathcal{A}$. An agent is something which can, at discrete time steps $t$, take actions in the environment. Once an action has been taken, the environement will produce a step transition consisting of a numerical reward as well as an updated state.
An environment is defined by a probability transition function
$$\begin{flalign} p(s^\prime, r \vert s, a) &\doteq \Pr \{ S_{t+1} = s^\prime, R_{t+1} = r \mid S_t = s, A_t = a \} \end{flalign}$$
which specifies the probability of every step transition given a state-action pair. By interacting with an environment repeatedly, an agent will produce a trajectory which consists of a sequence of as follows:
$$S_0,A_0,R_1,S_1,A_1,R_2,S_2,A_2,R_3, \dots$$
This sequence can continue indefinitely in the case of continuing tasks or terminate at some special state $S_T$. If an environment has such a terminal state it is charaterized by the following property: $p(s^\prime, r \vert S_T, a) = \cases{1; \; r = 0, s^\prime = S_T \\ 0; \; \text{else}} \:\: \forall a$
in other words, the only possible transitions from the terminal state remain there with 0 reward.
For some environments, only one transition state $s^\prime$ can be reached from any state-action pair $s, a$. These environments are called deterministic (the reward may or may not follow some distribution of values). All other environments are stochastic.
Just as TD policy prediction uses the Bellman equations as an update target, Sarsa uses the Bellman optimality equations as the update target and performs something closer to value iteration where the value function is updated every step.
As more samples are collected, the monte carlo estimates converge to the true value
The following code implements value iteration in the tabular case where the value function can be represented as a vector of values for each state. Given the probability transition function, state values are sufficient to perform value iteration, but it can also be done with state-action values.
The following code shows how one can use the Bellman Operator to iteratively calculate the value function for a given policy. The policy must be defined in terms of a probability distribution over actions for each state in the environment. This implementation is an extension of the prior code in which every state action pair can be enumerated in advance.
A policy defines action selection probabilities over states. For a tabular problem, a policy can be represented as a matrix just like the state action value function where the columns represent probabilities over actions for each state. A trajectory can be simulated by choosing an initial state, using a policy to sample action selection, and using the transition function to sample transitions and rewards. For an episodic problem with terminal states, the trajectory can terminate after a finite number of transitions (a policy that never reaches a terminal state could always produce an infinite trajectory even in an episodic problem). The following functions provide the facilities to generate trajectories for mdp's by generating samples from both policies and ptf's.
Policy iteration converged after 5 steps
Q-learning is implemented as a version of expected sarsa where the target policy is updated with to be greedy while the behavior policy is updated to be $\epsilon$-greedy
Select Discount Rate:
A model is anything that an agent can use to predict the environment. If the model provides a full description of all possible transitions it is called a distribution model vs a sample model that can only generate one of those possibilities according to the correct probability distribution. In dynamic programming, we used a distribution model while for certain example problems such as blackjack we only had a sample model.
A model can be used the create a simulated experience of the environment such as a trajectory. The common thread across all the techniques is the computation of the value function to improve a policy and using some update process to compute the value function for example from the data collected in simulated experience. For the learning methods considered so far, we have assumed that the data collected from trajectories is generated by the environment itself while in planning methods this experience would come instead from a model. However the learning techniques largely still apply to planning techniques as well since the nature of the data is the same. Consider a planning method analogous to Q-learning called random-sample one-step tabular Q-planning. This technique applies the Q-learning update to a transition sampled from a model. Instead of interacting with the environment in an episode or continuing task, this technique simply selects a state action pair at random and observes the transition. Just like with Q-learning, this method converges to the optimal policy under the assumption that all state-action pairs are visited an infinite number of times but the policy will only be optimal for the model of the environment.
Performing updates on single transitions highlights another theme of planning methods which don't necessarily involve exaustive solutions to the whole environment. We can direct the method to specific states of interest which may be important for problems with very large state spaces.
For a policy $\pi$, $v_\pi(s)$ is called the state value function and $q_\pi(s, a)$ is called the state-action value function. Notice that both expressions have a recursive form that defines values in terms of successor states. Those recursive equations are known as the Bellman Equations for each value function.
Since we have a finite and countable number of state action pairs, each value function can be represented as a vector or matrix whose indices represent the states and actions corresponding to that value estimate. Given a value function and a policy, we can verify whether or not it satisfies the Bellman Equation everywhere. If it does, then we have the correct value function for that policy. In other words, the correct value function is a fixed point of the Bellman Operator where the Bellman Operator is the act of updating the value function with the right hand side of the Bellman Equation.
Verifying that a value function is correct is simple, but what is less obvious is that we can use the Bellman Operator to compute the correct value function without knowing it in advance. It can be proven that if we initialize our value function arbitrarily and update those values with the Bellman Operator, that process will converge to the true value function. This iterative approach is one method of computing the value functions when we have a well defined policy and the probability transition function for an environment.
Select Discount Rate:
Recalling generalized policy iteration, we can use the episode as the point at which we update the policy with respect to whatever the value estimates are at that time. Since we cannot apply Monte Carlo prediction before an episode is completed, this is the fastest we could possible update the policy. We could always update our prediction of the value function over more episodes to make it more accurate, but we plan on updating the policy anyway so there is not need to have converged values until we have reached the optimal policy. In order to guarantee convergence, however, we must visit have a non zero probability of visiting every state action pair an infinite number of times in the limit of conducting infinite episodes. There are two main methods of achieving this property. The first is to begin episodes with random state-action pairs sampled such that each pair has a non-zero probability of being selected. The second method is to update the policy to be $\epsilon$-greedy with respect to the value function. $\epsilon$-greedy policies have a non-zero probability $\epsilon$ of taking random actions and behave as the greedy policy otherwise. Because of the random chance, such a policy is also guaranteed to visit all the state action pairs, but then our policy improvement is restricted to the case of the best $\epsilon$-greedy policy. We could lower $\epsilon$ to zero during the learning process to converge to the optimal policy.
After applying MC state-action value prediction for a single episode, we have ${q_\pi}_k$ where $k$ is the current episode count. To apply policy improvement just update $\pi_k(s) = \mathrm{argmax}_a {q_\pi}_k(s, a)$. We estimate state-action values instead of state values because it makes the policy improvement step trivial. The previous method required the probability transition function to compute $q(s, a)$ from $v(s)$. Using state-action values instead frees us from needing the probability transition function at the cost of needing to store more estimates.
State values for the random policy. Notice that at a discount rate of $\gamma=1$ all of the state values will be identical with a value of 1. If the sole reward is for reaching the goal, a discount factor must be used to favor reaching the goal as fast as possible. Otherwise any policy that eventually reaches the goal will be considered equally good.
Select x value to view state estimate:
Even with a non-tabular problem, it is possible that the transition function yields a distribution over transition states and rewards. In this case, we can do better than the typical MCTS algorithm by getting expected updates from the tree rather than sample updates. Given a policy which also produces a distribution over actions, we can use the prior distribution and only update the tree when we find actions that beat the greedy ones according to the policy. Each MCTS simulation we spawn in this case will generate a branching set of simulations that need to be tracked as well, but each state value will always be the maximum obtained for any action observed and the policy greedy action will always be attempted.
sample_action(v::AbstractVector{T}) where T<:AbstractFloatSamples an action index from a probability distribution represented by a vector.
sample_action(π::Matrix{T}, i_s::Integer) where T<:AbstractFloatSamples an action index from a probability distribution represented by a matrix.
π::Matrix{T}: A matrix representing the probability distribution over actions for each state. Each column π[:, i_s] represents the probability distribution over actions in state i_s.
i_s::Integer: The index of the current state.
Int: The sampled action index.
This function samples an action index from a probability distribution represented by a matrix π. The matrix π represents the probability distribution over actions for each state. The distribution for the current state i_s is given by the column π[:, i_s]. The sampling is performed using the sample_action function, which samples from a probability distribution represented by a vector using the Gumbel-max trick.
Select Discount Rate for State Policy Evaluation:
For tabular problems these functions can be represented as lookup tables themselves. The function will specify everything that could occur from a given state action pair. In a deterministic environment this transition could be represented by a single pair of values for the state and reward. For a stochastic environment, the probability for every possible transition needs to be specified. Since typically only a small subset of states are reachable from any given state, this distribution over states is very sparse, so a sparse vector is used to represent the distribution. Most of the values are zero matching the fact that most states are inaccessible. In general a transition function could only provide a sample transition, but for these functions they provide a full distribution of outcomes so they are subtypes of AbstractTabularMDPTransitionDistribution. Later on we can define transitions that only provide samples and these functions will not have Distribution in the name.
For some MDPs certain actions may be illegal to take from a given state. When this happens, the probability transition will not have any probability for any transition and will be an invalid distribution. For a deterministic problem, this would appear as a 0 index in the state transition distribution.
Number of Policy Iterations:
Windy Gridworld Converged after 34786 iterations
make_stochastic_gridworld(; kwargs...) -> NamedTuple{(:mdp, :isterm, :init_state), Tuple{FiniteStochasticMDP, Function, Integer}}Create a stochastic Gridworld MDP with the given parameters.
Keyword Arguments:
actions: The actions available in the environment (rook_actions)
start: The starting state (GridworldState(1, 4))
sterm: The terminal state (GridworldState(8, 4))
xmax: The maximum x-coordinate (10)
ymax: The maximum y-coordinate (7)
stepreward: The reward for each step (0.0f0)
termreward: The reward for reaching the terminal state (1.0f0)
iscliff: A function to check if a state is a cliff (s -> false)
iswall: A function to check if a state is a wall (s -> false)
cliffreward: The reward for falling off a cliff (-100f0)
goal2: The second goal state (GridworldState(start.x, ymax))
goal2reward: The reward for reaching the second goal state (0.0f0)
usegoal2: Whether to use the second goal state (false)
wind: The wind direction (zeros(Int64, xmax))
continuing: Whether the environment is continuing (false)
Returns:
A named tuple containing:
mdp: A FiniteStochasticMDP instance
isterm: A function to check if a state is terminal
init_state: The initial state index
Below is code implementing Monte Carlo prediction via importance sampling with the option of using ordinary or weighted importance sampling. The MDPs are the same sampling types defined earlier and the weighted method is used by default. Unlike on-policy Monte Carlo prediction, these algorithms require a behavior policy to be defined which is distinct from the target policy. By default the random policy is used, but any other soft policy is suitable. An error check will prevent prediction if the behavior policy is not soft.
Every MDP has a unique optimal value function whose values are greater than or equal to every other value function at every state or state-action pair: $v_*(s) \geq v_\pi(s) \: \forall s, \pi$ and $q_*(s, a) \geq q_\pi(s, a) \: \forall s, a, \pi$. This property can be used to derive a recursive relationship for both optimal value functions as shown below.
Unlike Monte Carlo methods, TD(0) using the Bellman style update does not need an entire trajectory to a terminal state in order to perform a value update. For the state value function, we only need to sample the reward and the next state. For the state-action value function, we also need the action taken from the transition state. Below is an example of the portion of the trajectory needed to perform the update. For state value prediction we do not immediately need $A_{t+1}$ but if we evaluate it as part of the step we can use it on the next step.
$$S_t \overset{\pi}{\rightarrow} A_t \rightarrow R_{t+1}, S_{t+1} \overset{\pi}{\rightarrow} A_{t+1}$$
The sequence shown of state, action, reward, state, action is where the name Sarsa comes from since these are the necessary components for updating state-action value function $q_\pi(s, a)$
If we apply policy iteration using the state value function, we can compute the optimal policy and value function for an arbitrary MDP. This example applies the technique to a gridworld similar to the previous example but with a secondary goal in the upper left hand corner with half the reward. The optimal solution changes depending on the discount rate since there are states for which the lower reward secondary goal is favorable due to the closer distance. One can select the iteration to view both the policy and the corresponding value function as well as the discount rate and secondary goal reward to use for solving the MDP.
To learn the optimal policy through sampling experience, it is important to visit all state-action pairs. Otherwise, we cannot compute all of the estimated values needed to update the value function. So far, we have considered methods that sample the environment using a single policy who's behavior is updated to converge towards the optimal policy. The optimal policy in general will not visit all the state action pairs, so it is possible that learned policies which are converging to the optimal policy will not visit all of the state-action pairs and therefore prevent us from collecting the experience necessary to continue generalized policy iteration. We have considered two methods to avoid this problem: 1) exploring starts and 2) $\epsilon$-greedy action selection. Now we consider a new type of solution that relies on off-policy learning in which the policy generating episodes in an environment is not the policy being optimized.
Such off-policy learning methods define a target policy and a behavior policy. The target policy is the policy for which we are computing the value function and possibly updating though policy improvement. The behavior policy is our source for episode samples. The returns generated by the behavior policy will not have expected values that match the target policy value function, so the sampled values must be modified. Recall that we are interested in calculating $\mathbb{E}_{\pi_{target}} [G_t \mid S_t = s, A_t = a]$ but we only have access to samples generated by $\pi_{behavior}$. Our approach to estimating the expected value is just to average the returns observed for each state-action pair. For off-policy prediction to work, we must compute a weighted sum of the sample returns that corrects for the difference in which trajectories you would observe for the target policy vs the behavior policy. When such correction weights are applied to the sample average, that is called importance sampling. The weight for each sample should be $\rho_{t:T-1} = \prod_{k=t}^{T-1}\frac{\pi_{target}(A_k \vert S_k)}{\pi_{behavior}(A_k \vert S_k)}$ which is equal to the probability of the trajectory beyond the current state for the target policy divided by that same probability under the behavior policy. In other words, if a given trajectory would never be seen by the target policy, then do not include that term in the average. If a trajectory is observed that is 10 times as likely under the target policy than the behavior policy, then weight it 10 times higher then trajectories that are equally expected under both policies.
Once we compute the weighted sum of returns, the value estimate can be computed by dividing this sum by either the number of terms or the sum of weights. The latter is called weighted importance sampling and both methods converge to the correct expected value in the limit of infinite samples. The difference between the methods is that weighted importance sampling always has finite variance for the estimate as long as the returns themselves have finite variance. Normal importance sampling can have infinite variance as long as the terms in the sum have infinite variance which is often the case with behavior policies that can generate long trajectories. For weighted importance sampling, there is a bias towards the behavior policy, but that bias converges to zero with more samplies so it isn't usually a concern. Therefore the more stable convergence properties of weighted importance sampling make it more favorable for Mpnte Carlo prediction and control.
mimetext/htmlrootassigneelast_run_timestampA6apersist_js_state·has_pluto_hook_features§cell_id$d7037f99-d3b8-4986-95c8-58f4f043e916depends_on_disabled_cells§runtime ӫpublished_object_keysdepends_on_skipped_cellsçerrored$bf12d9c9-c79d-4398-9f15-27cbde1ed476queued¤logsrunning¦outputbodySelect discount rate for value iteration:
The following code implements Monte Carlo control for estimating the optimal policy of a Tabular MDP from which we can only take samples. If we update the target policy to be greedy with respect to the value function, then exploring starts are required to ensure that we could visit all the state action pairs an unlimited number of times over the course of multiple episodes. The exploring starts method is defined by initializing each episode with a random state action pair and performing the greedy policy update after each episode.
The following code implements Monte Carlo control without exploring starts. In order to guarantee visits to all state-action pairs, we must force the policy to take random actions some percentage of the time. Any policy that has non-zero probability for every state-action pair is called a soft policy. For this algorithm we will select a value $\epsilon$ which controls the probability with which random actions are taken. Such a policy is soft and thus this family of policies are called $\epsilon$-soft policies. Once we set $\epsilon$, the behavior for the remaining probability can be arbitrary. If we evenly divide it, then that would be the uniformly random policy which is also $\epsilon$-soft for any value of $\epsilon$. If, instead, we select the greedy action for that probability, then such a policy is called $\epsilon$-greedy in addition to being an $\epsilon$-soft policy. For any finite $\epsilon$, the learned policy will not necessarily be optimal since it is restricted to sometimes taking random actions, but as $\epsilon$ approaches zero, the learned policy can become arbitrarily close to the optimal policy. Also, we are free to update the policy to be greedy with respect to the value function when we have completed the learning process.
A planning agent can use real experience in at least two ways: 1) it can be used to improve the model to make it a better match for the real environment (model-learning) and 2) it can be used directly to improve the value function using the previous learning methods (direct reinforcement learning). If a better model is then used to improve the value function this is also called indirect reinforcement learning.
Indirect methods can make better use of a limited amount of experience, but direct methods are much simpler and are not affected by the biases in the design of the model. Dyna-Q includes all the processes of planning, acting, model-learning, and direct RL. The planning method is the random-sample one-step tabular Q-planning described above. The direct RL method is one-step tabular Q-learning. The model-learning method is also table-based and assumes the environment is deterministic. After each transition $S_t,A_t \longrightarrow R_{t+1},S_{t+1}$, the model records in its table entry for $S_t,A_t$ the prediction that $R_{t+1},S_{t+1}$ will deterministically follow. Thus if the model is queried with a state-action pair that has been experienced before, it simply returns the last-observed next state and next reward as its prediction.
During planning, the Q-planning algorithm randomly samples only from state-action pairs that have previously been experienced, so the model is never queried with a pair about which it has no information. The learning and planning portions of the algorithm are connected in that they use the same type of update. The only difference is the source of the experience used.
The collection of real experience and planning could occur simultaneously in these agents, but for a serial implementation it is assumed that the acting, model-learning, and direct RL processes are very fast while the planning process is the model computation-intensive. Let us assume that after each step of acting, model-learning, and direct RL there is time for $n$ iterations of the Q-planning algorithm. Without the model update and the $n$ loop planning step, this algorithm is identical to one-step tabular Q-learning. An example implementation is below along with an example applying it to a maze environment.
Visual representation of a random policy
If we know in advance the entire probability transition function, then we can define an environment using those probabilities. Below are datatypes and functions that implement such an environment. Note that to implement such an environment, a complete list of all the states and actions must be known ahead of time meaning the problem is tabular.
When we have a distribution transition, the terminal states can be determined automatically by identifying states that produce 0 reward and stay in the same state.
The preceeding solution methods require the probability transition function to calculate value functions by using the Bellman equations. It is also possible to compute value functions from experience with the environment. Typically this experience is in the form of observed transitions in the environment: $(s, a) \rightarrow (s^\prime, r)$. For a deterministic environment, only one state transition is possible, so even after one observation we may already have information equivalent to the probability transition function. In general stochastic environments, we can only learn accurate value functions by observing many transitions from a single state action pair (usually an infinite number to guarantee convergence). Our approach to computing the optimal value function will follow the same pattern of generalized policy iteration where we use the value function as a stepping stone for policy improvement.
Let's first consider the problem of prediction problem for afterstates and see how to compute the afterstate value function and how it could be used for policy improvement. We will use the terminology $W(y)$ to represent the value of afterstate $y$ while $V(s)$ still means the value of state $s$. From the earlier definitions, we can show the relationship between the state and afterstate value functions.
Recall that:
$$\begin{flalign} G_t &\doteq R_t + \gamma R_{t+1} + \cdots \\ V_\pi(s) &\doteq \mathbb{E}_\pi[G_t \mid S_t = s] \\ & = \mathbb{E}_\pi[R_t + \gamma V_\pi(S_{t+1}) \mid S_t = s] \\ &= \sum_a \pi(a \vert s) \sum_{r, s^\prime} p(r, s^\prime \vert s, a) \left ( r + \gamma V(s^\prime) \right ) \end{flalign}$$
Representing the trajectory with afterstates and only considering the reward following an afterstate, we also know that:
$$\begin{flalign} G_t &\doteq R_t + \gamma(P_{t+1} + R_{t+1} + \gamma(P_{t+2} + R_{t+1} + \cdots))\\ W_\pi(y) &\doteq \mathbb{E}_\pi[G_t \mid Y_t = y] \\ & = \mathbb{E}_\pi[R_t + \gamma \left (P_{t+1} + W_\pi(Y_{t+1}) \right ) \mid Y_t = y] \\ &= \sum_{r, s^\prime} p(r, s^\prime \vert y) \left [r + \gamma \sum_{a^\prime} \left [ \pi(a \vert s^\prime) \left ( f_2(s^\prime, a^\prime) + W_\pi(f_1(s^\prime, a^\prime) \right ) \right ] \right ] \end{flalign}$$
Notice that compared to the value function, the policy only matters for this expected value when we consider the action taken from the transition state. The initial transition from the afterstate to $s^\prime$ only depends on our new transition function which only conditioned on the afterstate.
Recall that to improve a policy $\pi$ for which we have a value function $V_\pi$, we must select the greedy policy with respect to $V_\pi$ meaning $\pi^{\prime} (s) = \mathrm{argmax}_a \sum_{r, s^\prime} p(r, s^\prime \vert s, a)(r + \gamma V(s^\prime))$. If we do have access to the full probability transition function, we cannot compute this explicitely. Furthermore, we cannot estimate this either from a single trajectory because from each state we would just have a single transition based on the behavior policy at the time. That's why for MDPs that do not provide the full transition function, we prefer to estimate the state action value function $Q(s, a)$ because using that function policy improvement is much more trivial: $\pi^{\prime} (s) = \mathrm{argmax}_a Q(s, a)$.
Both Monte Carlo and Temporal Difference methods use sampling from experience to learn value estimates and optimal policies. With Monte Carlo methods we returned to the definition of the value function in terms of the expected value of the discounted future return:
$$\begin{flalign} v_\pi(s) &= \mathbb{E}_\pi \left [G_t \mid S_t = s \right] = \mathbb{E}_\pi \left [R_t + \gamma R_{t+1} + \cdots \mid S_t = s \right] \\ q_\pi(s, a) &= \mathbb{E}_\pi \left [G_t \mid S_t = s, A_t = a \right] = \mathbb{E}_\pi \left [R_t + \gamma R_{t+1} + \cdots \mid S_t = s, A_t = a \right]\\ \end{flalign}$$
Using this form of the expression, we could sample an entire trajectory to a terminal state under a policy and then calculate a single unbiased sample of the value estimate. Those samples can then be averaged in some way to compute the estimate. For Temporal Difference Learning, we will instead use the Bellman Equations as inspiration for computing the value estimates from samples. In particular recall that:
$$\begin{flalign} v_\pi(s) &= \mathbb{E}_\pi \left [G_t \mid S_t = s \right] \\ &= \sum_a \pi(a \vert s) \sum_{s^\prime, r} p(s^\prime, r \vert s, a) [r + \gamma v_\pi(s^\prime)] \\ &= \mathbb{E}_\pi [R_{t+1} + \gamma v_\pi(S_{t+1}) \mid S_t = s] \\ q_\pi(s, a) &= \mathbb{E}_\pi \left [G_t \mid S_t = s, A_t = a \right] \\ &= \sum_{s^\prime, r} p(s^\prime, r \vert s, a) [r + \gamma\sum_{a^\prime} \pi(a^\prime \vert s^\prime) q_\pi(s^\prime, a^\prime)] \\ &= \mathbb{E}_\pi[R_{t+1} + \gamma q_\pi(S_{t+1}, A_{t+1}) \mid S_t = s, A_t = a]\\ \end{flalign}$$
Since both of these expressions are expected values under the policy, we can again simply take samples from a trajectory collected under the policy $\pi$ and average those samples to compute the value estimates.
Expected Sarsa test. Q-learning is a variation of expected sarsa where the target policy update is ϵ-greedy. Both methods mostly converge to the optimal policy, but the value function for Q-learning should converge to the optimal greedy value function rather than ϵ-greedy so the values will be higher.
mimetext/htmlrootassigneelast_run_timestampA6c(persist_js_state·has_pluto_hook_features§cell_id$1e87f7c6-ed56-4e3d-9ae1-c170210849dadepends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cells§errored$3d6f3002-13d4-4c00-b5f8-e16da43be54bqueued¤logsrunning¦outputbodyTo use afterstates with generalized policy iteration, we need to modify our MDP framework by considering the following trajectory:
$$(S, A) \longrightarrow (Y, P) \longrightarrow (S^\prime, R) \longrightarrow \cdots \longrightarrow (S_T, R_T)$$
where $(S, A, R)$ are the usual state, action, and reward. We introduce $(Y, P)$ to indicate the afterstate and any intermediate reward that is received from the afterstate transition.
The probability transition function for a normal MDP is written as $p(s^\prime, r \vert s, a)$ and represents the probability of transitioning to state $s$ with reward $r$ under the condition that an agent takes action $a$ from state $s$.
When using afterstates, transitions can be represented with two functions:
$$p(y, \rho \vert s, a) \tag{a}$$
is the probability of transitioning to afterstate $y$ with intermediate reward $\rho$ given an agent takes action $a$ from state $s$
$$p(s^\prime, r \vert y) \tag{b}$$
is the probability of transitioning to state $s^\prime$ with reward $r$ given an agent starts in afterstate $y$.
Moreover, when an environment is modified to use afterstates, usually there are known deterministic dynamics that follow actions followed by some stochastic behavior after that. A good example is tic-tac-toe where we fully know the dynamics after making a move, but there could be some unknown behavior from the opponent. In this situation, the afterstate probability transition (a) is deterministic, so it could instead be represented by a mapping function that returns an afterstate and an intermediate reward given a state action pair.
$$f_1(s, a) = y \tag{b1′}$$
$$f_2(s, a) = \rho \tag{b2′}$$
where $y$ and $\rho$ are the afterstate and reward respectively after taking action $a$ in state $s$. Now all of the stochastic dynamics of the environment are captured in (b) and the function only has 3 arguments instead of the usual 4. We can now apply all of the previous techniques to the afterstate example and even combine dynamic programming and trajectory sampling.
If we apply value iteration using the state value function, we can compute the optimal value function for an arbitrary MDP. The optimal policy will just be the greedy policy with respect to that value function. The MDP shown is the same example as that used for the policy iteration example. Even though value iteration requires more steps to converge, each step is much faster than those of policy iteration.
Select Discount Rate:
Experience can be used to do policy evaluation. When we use experience instead of the probability transition function, this procedure is known as Monte Carlo Prediction and the environment will be used to sample experience that follows the probability transition function. This method is the easiest to understand because it only relies upon the original definition of the value functions.
$$\begin{flalign} v_\pi(s) &= \mathbb{E}_\pi \left [G_t \mid S_t = s \right] = \mathbb{E}_\pi \left [R_{t+1} + \gamma R_{t+2} + \cdots \mid S_t = s \right] \\ q_\pi(s, a) &= \mathbb{E}_\pi \left [G_t \mid S_t = s, A_t = a \right] = \mathbb{E}_\pi \left [R_{t+1} + \gamma R_{t+2} + \cdots \mid S_t = s, A_t = a \right]\\ \end{flalign}$$
Instead of expanding the definition of $G_t$, we will directly sample it from episodes through the environment. As such this method is only suitable for environments that are episodic and for policies that produce finite episodes. Given such a policy, we can select a starting state either randomly or given naturally by the environment and then use the policy to generate transitions through the environment until termination. Such an episode will look like:
$$S_0 \overset{\pi}{\rightarrow} A_0 \rightarrow R_1, S_1 \overset{\pi}{\rightarrow} A_1 \rightarrow R_2, S_2 \overset{\pi}{\rightarrow} A_2 \rightarrow \cdots\rightarrow R_T, S_T$$
From this episode, at each state $s = S_t$, we can estimate $G_t = \mathbb{E}_\pi \left [ R_t + R_{t+1} + \cdots + R_T \right ]$ by taking a single sample who's expected value matches the expected value in the definition of $G_t$. A weighted average of these samples will produce an estimate of $G_t$ who's variance will shrink to 0 in the limit of infinite samples (this depends on the averaging method as some methods may not have variance that converges to 0 and also on the environment in the case of the reward distribution for a particular state having infinite variance). If we instead wish to estimate state-action values, we can perform the same averaging but maintain a different estimate for each state action pair observed.
Consider instead policy improvement with afterstate value estimates $W_\pi(y)$ where we seek to choose a policy that is greedy with respect to the afterstate values:
$$\pi^\prime(s) = \mathrm{argmax}_a (f_2(s, a) + W_\pi(f_1(s, a))$$
where $f_1$ and $f_2$ are the deterministic functions defined above that determine which afterstate is reached from $(s, a)$ and whether any intermediate reward is received. This looks much closer to the policy improvement that occurs with $Q(s, a)$ and that is because $Q_\pi(s, a) = f_2(s, a) + W_\pi(f_1(s, a))$. So, if we use afterstates, we can have the benefits of learning the state action value function while only saving values for the afterstates. The functions $f_1$ and $f_2$ provide all the extra information needed to recover those values.
Continuing the comparison to value iteration, recall that we adapted the Bellman optimality equation for the state value function to have a single update rule to estimate $V^*(s)$:
$$V^*(s) = \max_a Q^*(s, a) = \max_a \sum_{r, s^\prime} p(r, s^\prime \vert s, a) (r + \gamma V^*(s^\prime))$$
We can only apply this update rule if we have $p(r, s^\prime \vert s, a)$ or if we instead estimate $Q^*$ and sample the transitions from the environment. To estimate $W^*(y)$, we need to represent the Bellman optimality equation for the afterstate value function instead of the state value function:
$$\begin{flalign} W^*(y) &= \sum_{r, s^\prime} p(r, s^\prime \vert y)(r + \gamma \max_a(f_2(s^\prime, a) + W^*(f_1(s^\prime, a)))) \\ &= \sum_{r, s^\prime} p(r, s^\prime \vert y)r + \gamma \sum_{s^\prime} p(s^\prime \vert y) \max_a(f_2(s^\prime, a) + W^*(f_1(s^\prime, a))) \end{flalign}$$
where $p(s^\prime \vert y) = \sum_r p(r, s^\prime \vert y)$
The outer sum is just represents an expected value based on the transition out of $y$, so if we don't have access to $p(r, s^\prime \vert y)$, we could sample the transitions from the environment. The $\max_a$ term can now be calculated explicitely and will involve finding the maximum index of a vector for each transition state and does not depend on the reward. Using state values, the maximization step involves evaluating a double sum every time, so each update with afterstates is less costly. Also, the afterstates themselves might be more informative in the sense that they all have distinct values. If many of the actions from a given state, lead to the same afterstate, this method will immediately treat them all as equal, whereas with usual value iterationthat equivalence would have to be calculated with the probability transition function. The benefits of using an afterstate value function depend entirely on how effectively the environment transitions can be separated into informative deterministic steps and limited stochastic dynamics.
Matrix representation of a random policy
Typically for TD methods, we update the value estimates with constant step size averaging instead of sample averaging. This requires selecting a step size $\alpha$ for the algorithm. If $\alpha = \frac{1}{N}$ where $N$ is the number of observed samples, then this is equivalent to sample averaging. Using a constant step size has the advantage that it is suitable for non-stationary problems.
Select Algorithm:
make_deterministic_gridworld(; kwargs...) -> NamedTuple{(:mdp, :isterm, :init_state), Tuple{FiniteDeterministicMDP, Function, Integer}}Create a deterministic Gridworld MDP with the given parameters.
Keyword Arguments:
actions: The actions available in the environment (rook_actions)
start: The starting state (GridworldState(1, 4))
sterm: The terminal state (GridworldState(8, 4))
xmax: The maximum x-coordinate (10)
ymax: The maximum y-coordinate (7)
stepreward: The reward for each step (0.0f0)
termreward: The reward for reaching the terminal state (1.0f0)
iscliff: A function to check if a state is a cliff (s -> false)
iswall: A function to check if a state is a wall (s -> false)
cliffreward: The reward for falling off a cliff (-100f0)
goal2: The second goal state (GridworldState(start.x, ymax))
goal2reward: The reward for reaching the second goal state (0.0f0)
usegoal2: Whether to use the second goal state (false)
wind: The wind direction (zeros(Int64, xmax))
continuing: Whether the environment is continuing (false)
Returns:
A named tuple containing:
mdp: A FiniteDeterministicMDP instance
isterm: A function to check if a state is terminal
init_state: The initial state index
makelookup(v::AbstractVector)Creates a lookup dictionary from elements to their indices.
v::AbstractVector: A vector whose elements will be used to create the lookup dictionary.
Dict{T, Int64}: A dictionary mapping each element of the vector v to its index.
This function generates a dictionary where each key is an element from the vector v and the corresponding value is the index of that element in the vector. This is useful for quickly finding the index of an element in the vector.
julia> v = ["a", "b", "c"]
julia> lookup = makelookup(v)
Dict{String, Int64} with 3 entries:
"a" => 1
"b" => 2
"c" => 3Random policy episode returns the trajectory as a list of states visited, actions taken, and rewards received. The final state of the episode is also shown.
When the probability transition function is unavailable, we can use an MDP that only provides sample transitions given a state action pair. Below is code implementing such a SampleTabularMDP{T<:Real, S, A, F, G, H} where we can fully enumerate all the states and actions. In addition to a list of states and actions, such an MDP must also have three functions:
step(i_s::Integer, i_a::Integer) returns a tuple of $(r, i_s^\prime)$ where $r$ is of type T
state_init() produces an initial state index to start an episode
isterm(i_s::Integer) returns a Boolean indicating whether an episode is a terminal state
Once these functions are defined, one can construct the mdp with SampleTabularMDP(states, actions, step, state_init, isterm). Alternatively, one can use an existing FiniteDeterministicMDP or FiniteStochasticMDP to construct one by providing it and a state_init function: SampleTabularMDP(mdp::FiniteDeterministicMDP, state_init::Function)
Since we can improve an arbitrary policy, one method to computing the optimal policy is to just repeat this process over an over until it converges. Once the process converges, our policy is guaranteed to be optimal. The procedure called policy iteration starts with an arbitrary policy $\pi_0$, computes its value function $v_{\pi_0}$, and then performs the greedy updateat every state to achieve an improved policy $\pi_1$. Upon repetition this procedure will produce a sequence of policies and value functions until the update results in no change to the policy. Since we are also computing the value functions at each step, we can also halt the process when the state values do not change at all or within some tolerance.
In the tic-tac-toe example we considered learning a value function for a state after the player's move but before the opponent's response. This type of state is called an afterstate, and it is useful in situations when we know a portion of the dynamics in an environment, but then a portion of it is stochastic or unknown. For example, we typically know the immediate effect of our moves, but not necessarily what happens after that.
It can be more efficient to learn based on afterstates because there are fewer values to represent than if we need to learn the full action value function. Any state-action pair that maps to the same afterstate would be represented by a single value. These afterstate value functions can also be learned with generalized policy iteration.
All tabular MDPs are characterized by having a complete list of states and actions. Eventually, we may want to simulate trajectories through these environments and for such simulations we would like to know how to begin. A state initialization function serves this purpose, and if nothing is specified one could simply pick a random state. In general we also must know which, if any, states are terminal. Such terminal states only exist in episodic problems and can be determined automatically by a distribution transition. Otherwise it needs to be provided upon construction. Finally to create an MDP the dynamics must be defined by the transition function, so these Tabular MDPs can contain one of the transitions defined above or other transitions that only provide samples.
$$\begin{flalign} v_*(s) &\doteq \max_\pi v_\pi(s) \: \forall \: s \in \mathcal{S} \tag{3.15} \\ &= \max_{a \in \mathcal{A}(s)} q_{*}(s, a) \: \forall \: s \in \mathcal{S} \tag{meaning of optimal}\\ &= \max_{a \in \mathcal{A}(s)} \sum_{s^\prime, r} p(s^\prime, r \vert s, a) \left [ r + γ v_* (s^\prime) \right ] \quad \forall s \in \mathcal{S} \tag{by (3.21) (3.19)}\\ q_*(s, a) &\doteq \max_\pi q_\pi(s, a) \: \forall \: s \in \mathcal{S} \text{ and } a \in \mathcal{A}(s) \tag{3.16} \\ &=\mathbb{E} \left [ R_{t+1} + \gamma v_* (S_{t+1}) \mid S_t = s, A_t = a \right ] \tag{3.17} \\ &= \sum_{s^\prime, r} p(s^\prime, r \vert s, a) \left [ r + γ v_* (s^\prime) \right ] \tag{exp value def (3.21)} \\ &= \sum_{s^\prime, r} p(s^\prime, r \vert s, a) \left [ r + γ \max_{a^\prime} q_*(s^\prime, a^\prime) \right ] \tag{3.20} \\ \end{flalign}$$
When we introduced the Bellman optimality equations, it was noted that those equations can be used to verify if a policy is optimal. It turns out that, just like with policy evaluation, we can use turn the Bellman optimality equations into an operator and use the operator directly to compute the optimal value function. This procedure is called value iteration and proceeds by first initializing an arbitrary value function $v_0$. Then that value function is updated with the Bellman optimality operator as follows:
$$\begin{flalign} v_{k+1}(s) = \max_a \sum_{s^\prime, r}p(s^\prime, r \vert s, a) \left [ r + \gamma v_k (s^\prime) \right ] \end{flalign}$$
This update can be performed at every state and repeated until the process converges. It can be proven that starting with an arbitrary $v_0$, this procedure does converge to $v_*$ in the same manner that policy evaluation can compute $v_\pi$. Here, the expected value under the policy is replaced with the maximization over actions. This approach dispenses entirely with defining a policy as required by policy iteration and may converge faster than that process. We can halt the process when the value function update becomes small within some tolerance.
Stochastic Gridworld Converged after 21233 iterations
Suppose we have a policy $\pi$ and the corresponding value functions $v_\pi, q_\pi$. Recall that the optimal value functions $v_*, q_*$ have the property that their values are at least as good as the values for any other policy. So, if we can find a modified policy whose value function is improved, we have moved our policy closer to the optimal one. The approach in policy improvement will be to repeatedly improve a set policy until it is optimal.
As a starting point, consider a state $s$ and the corresponding value function at that state $v_\pi(s)$. We can also consider $q_\pi(s, a)$ for all of the available actions. Let's say we find an action $a$ such that $q_\pi(s, a) \geq v_\pi(s)$. If we define a new policy $\pi^\prime$ which takes this action from state $s$ and otherwise follows $\pi$, then we know that $q_\pi(s, \pi^\prime(s)) \geq v_\pi(s)$. This expression is using the value function for the original policy $\pi$ and assumes that our choice of action at state $s$ is a one time event. If we encounter $s$ in the future, this expression is only correct if we revert to following $\pi$. What we would like to know is whether $v_{\pi^\prime}(s) \geq v_\pi(s)$ for the state in question and every other state in the problem.
The policy improvement theorem states that such a policy $\pi^\prime$ as we have defined it does in fact have that property. In other words:
$$q_\pi(s, \pi^\prime(s)) \geq v_\pi(s) \implies v_{\pi^\prime}(s) \geq v_\pi(s) \: \forall \: s \in \mathcal{S}$$
The $\pi^\prime$ defined above meets this property and uses $q_\pi$ to select a new action. If we have access to the probability transition function, we can use $v_\pi$ to update the policy as follows:
$$\begin{flalign} \pi^\prime(s) &\doteq \mathrm{argmax}_a q_\pi(s, a) \\ & = \mathrm{argmax}_a \mathbb{E} [R_{t+1} + \gamma v_\pi(S_{t+1}) \mid S_t = s, A_t = a] \\ & = \mathrm{argmax}_a \sum_{s^\prime, r} p(s^\prime, r \vert s, a) [r + \gamma v_\pi(s^\prime)] \\ \end{flalign}$$
This policy is known as the greedy policy with respect to the value function. We can apply this update at every state to improve the policy everywhere. Let's say that $\pi^\prime = \pi$. That would mean that the $v_{\pi^\prime} = v_\pi$, and $v_{\pi^\prime}(s) = \max_a q_{\pi^\prime}(s, a)$. In other words, $\pi^\prime$ satisfies the Bellman optimaliy equation and we have found the optimal policy.
For some MDP's, the state space may be too large to enumerate. We could still sample from the environment and know ahead of time examples of states and actions, but in these problems we can never compute a complete solution. Monte Carlo Tree Search (MCTS) allows us to update state-action value estimates but only for selected states that we encounter during interactions with the environment. The data we collect can be used to build a partial model of the environment that we use to improve the value estimates and policy without having a full solution. All of the previous MDP types we defined contain a complete state list. This technique can apply to any MDP, even those for which we do not know all of the states.
For these problems, we still consider the action space to be finite and enumerated. So actions will still be represented by indices and policies can be represented by vectors of length equal to the action space for a given state. Like the previous tabular MDP's, different types of transition functions are possible for non-tabular problems. The state now must always be represented as its original type, but we can still have transition functions that produce samples or a full distribution over transition states.