MDPs: a state, an action, a reward and the value of what follows

The previous post drew the loop: an agent sees a state, picks an action, receives a reward and a new state, and tries to collect as much reward as it can over the long run. That is the picture. The Markov decision process, MDP for short, is the picture made precise enough to compute with, and almost every idea in the rest of this series, the Q-table, the update rule, the model, is defined on top of it. This post goes through its parts one at a time, with the same ten days of SPY from January 2023 as the worked example, and ends with the one equation that the whole field leans on.

The state has to carry the past

Sutton and Barto write the loop as a sequence: state, action, reward, state, action, reward. In a finite MDP the next state and the reward depend only on the current state and action. The probability of landing in a given next state with a given reward is a function of four things, where you are, what you did, where you land, what you got, and nothing earlier in the history enters it. That is the Markov property.

The book is careful about where this restriction bites: “this is best viewed a restriction not on the decision process, but on the state. The state must include information about all aspects of the past agent–environment interaction that make a difference for the future.” So the property is not something a market has or lacks. It is something a state representation has or lacks. If the state is “today’s five-day return”, then two mornings with the same five-day return are the same state, and if the agent is long on one and in cash on the other, its best action differs but the state cannot say so. The fix is to put the holding in the state. If what matters for the future is a trend that five days cannot see, the fix is a longer window. A state that leaves out something the future depends on breaks the assumption every later method rests on, and the methods will still run; they will simply learn the wrong thing. Murphy’s name for the honest version of this situation is a partially observed MDP: the agent sees an observation, not the state, and has to decide from history.

The Markov property is a demand on your state, not a fact about the world. Ask of each state label: if two mornings share this label, do they really call for the same action?

Transitions can be random

The same action in the same state does not have to lead to the same place. Sutton and Barto’s dynamics function gives a probability for each possible next state and reward, and only in the special deterministic case is one of those probabilities 1. The trading case is firmly in the random camp: “move to long” in a given state is followed by a gain on some days and a loss on others, and nothing in the state could have told you which. This matters for how the learner treats one experience. A single transition is one draw from a distribution, not the truth about the action, which is why every method in this series moves its estimates a fraction of the way towards new evidence rather than all the way.

Reward is the goal; return is the score

The reward is one number per step. Sutton and Barto’s reward hypothesis is that everything we mean by a goal can be written as “maximise the expected sum of a received scalar signal”, and their warning is the one from the previous post: the reward says what you want, not how to get it. Reward a chess agent for capturing pieces and it will capture pieces while losing games.

The return is what the agent actually maximises: the rewards still to come, added up. For an episode that ends at step T it is the plain sum (their equation 3.7). For a task that never ends the plain sum can be infinite, so each later reward is multiplied by a discount factor $\key{\gamma}$ between 0 and 1, raised to the power of how many steps away it is (equation 3.8):

G, the return; γ, the discount factorR, the rewards observed after time t

A reward k steps ahead is worth $\key{\gamma}^k$ of what it would be worth today. With $\key{\gamma} = \key{0.9}$ a reward seven days away counts for less than half; with $\key{\gamma} = \key{0.99}$ that takes 69 days. At $\key{\gamma} = 0$ the agent is myopic and cares only about the next reward; as $\key{\gamma}$ approaches 1 it becomes farsighted. And the sum stays finite: a reward of +1 forever, discounted at 0.9, adds up to exactly 10, because the weights 1, 0.9, 0.81, 0.729 and so on sum to 1 over 1 minus 0.9.

Here are the ten rewards of the January 2023 episode (long SPY from 2023-01-03) with the return from each day computed three ways:

The day-1 decision to buy is worth $\key{3.98\%}$ if every later day counts in full, $\key{2.34\%}$ at a discount of 0.9, and $\key{0.01\%}$ at 0.5, where the rewards beyond the first few days barely register. Same ten numbers, three verdicts. The discount factor is a statement about horizon: how far ahead the agent is asked to look when it judges today’s choice. A trading agent discounted at 0.5 is being told to care about this week; one at 0.99 is being told to care about this quarter.

The table has a pattern that is the key to everything later. Read it from the bottom. The return from day 10 is day 10’s reward alone. The return from day 9 is day 9’s reward plus γ times the return from day 10. Each row is the reward now plus the discounted row below (equation 3.9):

G, the return; γ, the discount factorR, the reward observed next

Check it on the top row at $\key{\gamma} = \key{0.9}$: $-0.42\% + 0.9 \times 3.07\% = 2.34\%$. A return can be computed without ever writing out the whole sum, one step at a time from the end.

Value: the return you expect, not the one you got

The ten returns above are what happened once. An agent choosing on the morning of 2023-01-03 did not know them. What it can hope to know is what usually follows a state like this one, and that is a value.

Sutton and Barto define the state value under a policy, written $\key{v_\pi(s)}$, as the expected return when starting in state s and following policy π from then on (equation 3.12). It answers “how good is it to be here, given how I behave?”. The action value, written $\key{q_\pi(s, a)}$, is the expected return when starting in s, taking action a first, and then following π (equation 3.13). It answers “how good is it to do this here?”, and it is the quantity a Q-table stores. Both are averages over everything the random transitions and the policy’s own randomness might produce, which is why a single observed return like the +3.98% above is one sample of a value, not the value.

The book also says how such values can be estimated with nothing but experience: follow the policy, and for each state keep a running average of the actual returns that followed it. As the state is visited more and more, the average converges to the state’s value. That is the whole idea behind the next three posts, with one refinement, which the recursion above makes possible.

Bellman: value now equals reward now plus value next

Because a return obeys $\key{G_t} = \good{R_{t+1}} + \key{\gamma}\,\key{G_{t+1}}$, the expected return does too. The value of a state is the expected reward for leaving it plus the discounted value of wherever you land, averaged over the actions the policy might take and the places the environment might send you. That is the Bellman equation for $\key{v_\pi}$ (Sutton and Barto’s equation 3.14), and in words it is the sentence in this section’s heading. Its power is that it ties every state’s value to its neighbours’ values, so an estimate of one can be improved from estimates of the others without waiting for an episode to finish.

An optimal policy is one whose value is at least as high as every other policy’s in every state (section 3.6); there is always at least one, and all of them share the same optimal value functions, $\key{v_*}$ and $\key{q_*}$. For these the Bellman equation takes a special form with no policy in it: the value of a state under the best policy is the best action’s reward plus the discounted value of the state it leads to, where “best” means the action with the highest value (equations 3.19 and 3.20). The recipe for acting is then one line long. In each state, look up the action values and take the largest. The hard part, and the subject of Q-learning: one update rule, repeated, is filling in those values from experience.

Traps

The code

The snippet reproduces the three return columns of the table from the end backwards. Variables:

import numpy as np
import pandas as pd

url = "https://raw.githubusercontent.com/ankurtrapasiya/examples/main/data/prices.csv"
px = pd.read_csv(url, index_col="date", parse_dates=True)["SPY"]
r = (px / px.shift(1) - 1).dropna()
start = r.index.get_loc(pd.Timestamp("2023-01-03"))
rewards = r.iloc[start:start + 10].values

def to_go(gamma):
    g = np.zeros(len(rewards) + 1)               # g[10] = 0: nothing comes after the last day
    for t in range(len(rewards) - 1, -1, -1):    # walk backwards from the last day
        g[t] = rewards[t] + gamma * g[t + 1]      # return now = reward now + gamma * return next
    return g[:-1]

for gamma in (1.0, 0.9, 0.5):
    print(gamma, " ".join(f"{100*x:+.2f}" for x in to_go(gamma)))

It prints three rows of ten numbers: the γ = 1 row starts +3.98, the γ = 0.9 row +2.34, the γ = 0.5 row +0.01, matching the table. range(9, -1, -1) is Python’s way to count down from 9 to 0; the loop is the recursion from the text, run once.

Summary

References

• Sutton and Barto, Reinforcement Learning: An Introduction, 2nd edition (MIT Press, 2018). Section 3.1 for the agent–environment interface, the dynamics function and the Markov property as a restriction on the state; section 3.2 for the reward hypothesis; section 3.3 for episodic and continuing tasks, the return (equations 3.7 and 3.8), the discount rate and the recursion (equation 3.9); section 3.5 for state and action values (equations 3.12 to 3.14) and estimating them by averaging returns; section 3.6 for optimal policies and the Bellman optimality equations (3.19 and 3.20).
• Kevin P. Murphy, Probabilistic Machine Learning: Advanced Topics (MIT Press, 2023). Section 34.5.1 for the MDP as a tuple and the transition notation; section 34.5.2 for partially observed MDPs; section 35.1 for the trajectory and the discounted cumulative reward.
• Tom M. Mitchell, Machine Learning (McGraw-Hill, 1997). Section 13.2 for the learning task as an MDP with transition and reward functions unknown to the agent.