Introduction

The third article described an MDP as the problem statement of reinforcement learning. By writing down its states, actions, transition probabilities, rewards, and discount factor, we could express the world in which an agent must make decisions.

But writing the problem does not immediately give us the answer. We still need numbers that tell us which of DESK, CAFE, and HOME is a good state, and whether STUDY or LEAVE is the better action at DESK.

Looking only at the immediate reward makes the problem seem simple: choose the state or action with the largest reward. As we saw in the first article, however, the objective of reinforcement learning is not to maximize one reward. It is to maximize the return, the sum of future rewards.

Moving one cell now may give $-1$ but lead to an exit worth $+10$. Conversely, a path that gives $+3$ now may end in $-20$ several steps later. Whether the present is good or bad cannot be determined from the next reward alone.

Reinforcement learning therefore uses value functions. Before calculating values, this article carefully separates three terms.

• Reward: one number just received
• Return: the sum of future rewards that actually accumulated along one path
• Value: the expected average return after experiencing the same situation many times

Distinguishing Reward, Return, and Value with a Receipt

Reward $R_{t+1}$ is the one-step number the environment returns after an action at time $t$.

$$R_{t+1}=+2$$

Return $G_t$ is the discounted sum of every reward actually received from time $t$ onward.

$$G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots$$

If the following rewards are $+2$, $0$, and $+5$, with $\gamma=0.9$, then

$$G_t = 2 + 0.9 \times 0 + 0.9^2 \times 5 = 6.05.$$

This is the outcome of one path actually taken. But even from the same state, the policy may choose another action or the environment may produce another next state. One episode may return $6.05$, another $-2$, and another $10$.

Value expresses the average return we expect across these possible outcomes.

One unusually expensive receipt does not mean that a store is always expensive on average. Value is similar. A high return in one episode is not enough to fix a state's value at a high number. We must also account for how often the different paths occur.

Expectation Is the Average of Futures Not Yet Observed

The state-value function is defined as

$$v_\pi(s) = \mathbb{E}_\pi \left[ G_t \mid S_t=s \right].$$

Rather than reading every symbol at once, let us work from the inside.

• $S_t=s$: the condition that the current state is $s$
• $G_t$: the discounted return that will accumulate from now on
• $\mathbb{E}_\pi$: the average over possible outcomes when policy $\pi$ is followed
• $v_\pi(s)$: that average attached to state $s$

In one sentence:

The expected return when we begin from state $s$ and continue to follow policy $\pi$.

Expectation means more than adding observed reward numbers and dividing by the number of episodes. It averages both the uncertainty in which action the policy will choose and the uncertainty in which next state the environment will produce.

Suppose only two paths are possible from state $s$.

• Return $5$ with probability $0.7$
• Return $-1$ with probability $0.3$

The value is

$$\begin{aligned} v_\pi(s) &= 0.7 \times 5 + 0.3 \times (-1) \\ &= 3.2. \end{aligned}$$

A value of $3.2$ does not mean that an actual episode must return $3.2$. The actual result is either $5$ or $-1$. The number $3.2$ is what we expect on average if the same situation is repeated many times.

The Subscript π Is Not Decoration

We often omit $\pi$ and write $v(s)$ when the policy is already clear from context. But we must not forget that the value depends on the policy.

Suppose DESK has two actions.

• STUDY: expected long-term return $6$
• LEAVE: expected long-term return $2$

Under a policy that always chooses STUDY, the value of DESK is close to $6$. Under a policy that chooses each action half the time, the value is about $4$.

$$0.5 \times 6 + 0.5 \times 2 = 4$$

Even when the state stays the same, changing the policy changes the future paths and therefore the value.

A state value is not the score of a state by itself. It also scores the policy that will be followed from that state onward.

This is why value functions are useful for comparing policies. In the same MDP, comparing Policy A's $v_A(s)$ with Policy B's $v_B(s)$ tells us which policy creates a better future after that state.

Action Value: How Good Is It to Begin with This Action?

If the state value answers “how good is it to be in this state?”, the action value asks a more specific question.

$$q_\pi(s,a) = \mathbb{E}_\pi \left[ G_t \mid S_t=s, A_t=a \right]$$

In words:

The expected return after first taking action $a$ in state $s$, then following policy $\pi$ thereafter.

$v_\pi(s)$ averages over the actions the policy might select in the current state. In contrast, $q_\pi(s,a)$ fixes the first action to $a$ and averages the future that follows.

Suppose the policy at DESK selects STUDY with probability $0.7$ and LEAVE with probability $0.3$, and

$$q_\pi(\text{DESK},\text{STUDY})=6,$$ $$q_\pi(\text{DESK},\text{LEAVE})=2.$$

The state value is the policy-weighted average of the action values.

$$\begin{aligned} v_\pi(\text{DESK}) &= 0.7 \times 6 + 0.3 \times 2 \\ &= 4.8. \end{aligned}$$

In general,

$$v_\pi(s) = \sum_{a \in \mathcal{A}} \pi(a \mid s) q_\pi(s,a).$$

The right side multiplies each action's $q_\pi(s,a)$ by the probability that the policy selects that action, then adds the results.

How to Read Values in a Gridworld

Let every cell of a Gridworld be a state. The exit in the upper right gives $+10$, the pit in the lower right gives $-10$, and the agent moves up, down, left, or right.

A state immediately beside the exit can have a high value even if its current reward is zero, because the next action is likely to reach the exit. A state near the pit may have a low value even if it currently has no penalty.

Suppose the directional action values in one state, as in the right side of the figure, are

• up: $q_\pi(s,\uparrow)=7.2$
• right: $q_\pi(s,\rightarrow)=6.1$
• left: $q_\pi(s,\leftarrow)=2.8$
• down: $q_\pi(s,\downarrow)=1.3$

The value tells us how good the current cell is on average. The Q-values also tell us which direction leads to that good future.

If the environment model is known, we can use $v_\pi(s)$ and the transition probabilities to look one step ahead for every action. When the model is unknown, however, it is far more convenient to learn $q_\pi(s,a)$ directly from experience that records which action was taken. This is why SARSA and Q-Learning later update action values rather than state values.

Optimal Value Is the Best Future Among All Policies

Every value so far has been associated with a particular policy $\pi$. The greatest value achievable among all possible policies is the optimal value.

$$v_*(s) = \max_\pi v_\pi(s)$$ $$q_*(s,a) = \max_\pi q_\pi(s,a)$$

If we knew $q_*(s,a)$ exactly, we could choose the action with the largest Q-value in state $s$.

$$\pi_*(s) = \arg\max_a q_*(s,a)$$

$\max$ returns the largest value itself. $\arg\max$ returns the action that produced that value.

For example, if the Q-values are $6$ for STUDY, $2$ for LEAVE, and $4$ for WORK OUT, then

$$\max_a q_*(s,a)=6,$$

while

$$\arg\max_a q_*(s,a)=\text{STUDY}.$$

This small notational difference separates a value from an action, and it will appear repeatedly later.

Value Is Not Reward

At first, rewards and values are easy to confuse because both are numbers written beside states. The following three checks help keep them separate.

A High Reward Can Still Lead to a Low Value

A state that gives $+5$ now but then leads to $-10$ at every later step has a low long-term value.

A State with No Current Reward Can Have a High Value

The state one cell before the exit may give zero now but have a high probability of receiving $+10$ soon.

Value Is Not One Observed Outcome

The return is an outcome actually obtained in one episode. The value is the expectation over many possible returns.

A reward is data returned by the environment. A value is what the agent wants to know, or must estimate, to judge the future.

What to Remember

The central idea of this article is

Value is the expected return when we begin from a particular state or state-action pair and follow a policy.

More specifically:

1. A reward is a one-step number.
2. A return is the discounted sum of rewards that actually accumulated along one path.
3. $v_\pi(s)$ is the expected return when policy $\pi$ is followed from state $s$.
4. $q_\pi(s,a)$ is the expected return after taking action $a$ first in state $s$.
5. The same state has a different value under a different policy.
6. $\max$ denotes the largest value, while $\arg\max$ denotes the action that produces it.

We now know the definition of value, but still need to calculate it. If the future extends for ten or a hundred steps, must we expand every possible return all the way to the end every time?

The next article introduces the Bellman equation, which folds a long future into “the next reward and the value after the next state.” We will also see how this one line leads to policy evaluation, policy iteration, and value iteration.

References

• David Silver, UCL Reinforcement Learning Course
• David Silver, Lecture 2: Markov Decision Processes
• Seoul National University DSBA Lab, Introduction of Reinforcement Learning
• Sutton & Barto, Reinforcement Learning: An Introduction, 2nd Edition