Chapter Core Objectives

This chapter establishes the concepts that will be used repeatedly in all subsequent chapters of reinforcement learning:

  • state
  • action
  • state transition
  • policy
  • reward
  • trajectory, ==return==, episode
  • Markov decision process, MDP
  • Markov property

In one sentence:
Reinforcement learning studies the problem of an agent learning a "good policy" ==from reward feedback== through trial-and-error interaction with an environment; this chapter uniformly describes this process using an MDP.

1.1 Grid World Example

This book uses a grid world example from beginning to end.

  • The robot is called an agent.
  • The robot moves in a grid, and at each time step it can occupy only one cell.
  • White cells can be entered.
  • Orange cells are forbidden.
  • There is a target cell.
  • The agent's goal: find a "good" policy that can reach the target from any initial cell while avoiding entering forbidden cells, hitting boundaries, and taking meaningless detours.

If the agent knows the map in advance, then finding a path is easy;
but reinforcement learning usually assumes that the agent does not know the environment model and must learn through interaction with the environment by trial and error.
Therefore, concepts such as state, action, transition, policy, and reward need to be defined.

1.2 States and Actions

State

The state describes the state of the agent relative to the environment.
In the grid world, the state is the agent's position.

Figure 1.3(a) has 9 cells, so there are 9 states:

\mathcal{S}=\{s_1,s_2,\ldots,s_9\}

\mathcal{S} is called the state space.

Action

In each state, the agent can take 5 actions:

  • a_1: up
  • a_2: right
  • a_3: down
  • a_4: left
  • a_5: stay still

The set of actions is called the action space:

\mathcal{A}=\{a_1,a_2,a_3,a_4,a_5\}

Different states can have different action spaces. For example, in s_1, moving up or left would hit the boundary, so we can set:

\mathcal{A}(s_1)=\{a_2,a_3,a_5\}

But for simplicity, this book usually takes:

\mathcal{A}(s_i)=\mathcal{A}=\{a_1,\ldots,a_5\}

which holds for all states.

1.3 State Transition

Definition

After the agent takes action a in state s, it may transition to another state s'; this process is called state transition.

For example:

s_1 \xrightarrow{a_2} s_2

means moving right in s_1 and arriving at s_2.

Two Important Examples

  1. Hitting the boundary
    In s_1, execute a_1, attempting to go up out of bounds.
    Since it cannot leave the state space, the agent is bounced back:

    s_1 \xrightarrow{a_1} s_1

  2. Entering a forbidden area
    For example, in s_5, execute a_2, attempting to enter s_6.
    There are two possibilities:

    • The forbidden area, although forbidden, can still be entered, but a penalty is incurred;
    • The forbidden area cannot be entered, and the agent is bounced back.

    This book chooses the first: the forbidden area can be entered, but entering it yields a negative reward.
    Therefore:

    s_5 \xrightarrow{a_2} s_6

Tabular Representation

Table 1.1 is a tabular representation of state transitions:

  • Each row corresponds to a state;
  • Each column corresponds to an action;
  • The cell indicates the next state transitioned to after taking that action.

This kind of table can only describe deterministic state transitions.

Probabilistic Representation

More generally, state transitions are stochastic and are represented by conditional probabilities:

p(s'|s,a)

denotes the probability of transitioning to s' after taking action a in state s.
It must satisfy:

\sum_{s'\in \mathcal{S}} p(s'|s,a)=1

For example:

p(s_2|s_1,a_2)=1
p(s_1|s_1,a_2)=0,\quad p(s_3|s_1,a_2)=0,\ldots

This shows that moving right in s_1 definitely leads to s_2.

If there is random wind, etc., then it may happen that:

p(s_5|s_1,a_2)>0

For simplicity, the grid world in this book mainly considers deterministic transitions.

1.4 Policy

Definition

A policy tells the agent what action should be taken in each state.

A policy can be represented by arrows, as shown in Figure 1.4(a).

Mathematical Representation

A policy is a conditional probability distribution:

\pi(a|s)

denotes the probability of choosing action a in state s.
It must satisfy:

\sum_{a\in \mathcal{A}(s)} \pi(a|s)=1

Deterministic Policy

For example, the policy in Figure 1.4 definitely moves right in s_1:

\pi(a_2|s_1)=1

The probabilities of other actions are 0:

\pi(a_1|s_1)=0,\quad \pi(a_3|s_1)=0,\quad \pi(a_4|s_1)=0,\quad \pi(a_5|s_1)=0

Stochastic Policy

Figure 1.5 is a stochastic policy.
In s_1, the agent may move right or down, each with probability 0.5:

\pi(a_2|s_1)=0.5,\quad \pi(a_3|s_1)=0.5

The probabilities of other actions are 0.

Tabular Representation

Table 1.2 is a tabular representation of the policy:

  • Each row is a state;
  • Each column is an action;
  • The cell is the probability of taking that action.

Later, Chapter 8 will ==generalize policies from tabular representations to parameterized function representations==.

1.5 Reward

Definition

After the agent executes action a in state s, it receives a reward from the environment, denoted by r.
The reward is a function of state and action:

r(s,a)

Rewards can be positive, negative, or zero.

  • Positive reward: encourages the agent to take that action;
  • Negative reward: discourages the agent from taking that action.

Reward Settings for the Grid World in This Book

  • Attempting to go out of bounds: r_{\text{boundary}}=-1
  • Attempting to enter a forbidden area: r_{\text{forbidden}}=-1
  • Reaching the target: r_{\text{target}}=+1
  • Other cases: r_{\text{other}}=0

Special Handling of the Target State s_9

The reward process does not necessarily terminate after reaching s_9.

  • If a_5 is executed in s_9 to stay, the next state is still s_9, and the reward is +1;
  • If a_2 is executed in s_9 to move right, the next state is still s_9, but the reward is -1, because it is equivalent to hitting the boundary.

Tabular Representation

Table 1.3 is a tabular representation of rewards:

  • Each row is a state;
  • Each column is an action;
  • The cell is the reward obtained after taking that action.

Key Reminder

One cannot choose actions based only on immediate rewards.
Because a large immediate reward for an action does not necessarily mean a large long-term total return.
Reinforcement learning focuses on the long-term cumulative reward, i.e., return.

Stochastic Rewards

More generally, rewards can also be stochastic, described by:

p(r|s,a)

and satisfy:

\sum_{r\in \mathcal{R}(s,a)} p(r|s,a)=1

In the grid world of this book, the reward process is deterministic.

Significance of Reward Design

Reward can be viewed as a kind of human-machine interface.
By designing rewards, we can ==guide the agent to exhibit the behavior we expect==.
But reward design itself is usually not simple, especially for complex tasks.

1.6 Trajectories, Returns, and Episodes

Trajectory

A trajectory is a state-action-reward chain.

For example, in Figure 1.6(a), the policy generates the trajectory:

s_1 \to s_2 \to s_5 \to s_8 \to s_9

The corresponding rewards are:

0,0,0,1

Return

The return is ==the sum of all rewards along the trajectory==.

For a finite trajectory:

\text{return}=0+0+0+1=1

Another trajectory in Figure 1.6(b):

s_1 \to s_4 \to s_7 \to s_8 \to s_9

The rewards are:

0,-1,0,1

The return is:

0-1+0+1=0

Therefore, the left policy has return 1, and the right policy has return 0, so the left policy is better.
This is consistent with intuition: the right policy passed through the forbidden area.

Immediate Rewards and Future Rewards

==Return = immediate reward + future reward==.
Sometimes the immediate reward is negative, but the future reward is larger, so one cannot be short-sighted.
Actions must be decided based on return, not immediate reward.

Infinitely Long Trajectories and Discounted Return

If after reaching s_9 the agent keeps staying, and each time gets +1, then:

1+1+1+\cdots=\infty

Direct summation diverges.
Therefore, the discounted return is introduced:

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

where \gamma\in(0,1) is the discount rate.

For example:

0+\gamma 0+\gamma^2 0+\gamma^3 1+\gamma^4 1+\cdots = \gamma^3(1+\gamma+\gamma^2+\cdots) = \frac{\gamma^3}{1-\gamma}

Role of the Discount Rate

  1. Remove the restriction that the process must terminate, allowing infinitely long trajectories;
  2. Adjust the emphasis on near-term rewards versus long-term rewards:
    • When \gamma is close to 0: emphasis on near-term rewards, and the policy is short-sighted;
    • When \gamma is close to 1: emphasis on long-term rewards, and the policy is far-sighted and willing to take risks.

Episode

The agent interacts with the environment according to the policy and may stop at some terminal state.
The trajectory obtained in this way is called an episode or trial.

  • episodic tasks: tasks with terminal states;
  • continuing tasks: no terminal state, and interaction never ends.

How to Convert Episodic to Continuing

There are two ways:

  1. Treat the terminal state as an absorbing state, where the agent stays forever after reaching it;
  2. Treat the terminal state as an ordinary state, and the agent can leave and return.

This book adopts the second:
The target state s_9 is treated as an ordinary state, and the action space remains:

\mathcal{A}(s_9)=\{a_1,\ldots,a_5\}

Because reaching s_9 can repeatedly yield positive rewards, a discount rate must be used to prevent the return from diverging.

1.7 Markov Decision Process MDP

The previous sections introduced concepts through examples; this section formalizes them using an MDP.

An MDP is a general framework for ==describing stochastic dynamical systems==.

Components of an MDP

1. Sets

  • State space: \mathcal{S}
  • Action space: \mathcal{A}(s), associated with each state s
  • Reward set: \mathcal{R}(s,a), associated with each state-action pair (s,a)

2. Model / dynamics

  • State transition probability:
p(s'|s,a)

satisfying:

\sum_{s'\in \mathcal{S}} p(s'|s,a)=1
  • Reward probability:
p(r|s,a)

satisfying:

\sum_{r\in \mathcal{R}(s,a)} p(r|s,a)=1

3. Policy

\pi(a|s)

denotes the probability of choosing action a in state s, satisfying:

\sum_{a\in \mathcal{A}(s)} \pi(a|s)=1

4. Markov Property

The Markov property is "memorylessness":

p(s_{t+1}|s_t,a_t,s_{t-1},a_{t-1},\ldots,s_0,a_0) = p(s_{t+1}|s_t,a_t)
p(r_{t+1}|s_t,a_t,s_{t-1},a_{t-1},\ldots,s_0,a_0) = p(r_{t+1}|s_t,a_t)

That is, the next state and reward depend only on the current state and action, ==and are unrelated to earlier history==.

The Markov property is the basis for deriving the Bellman equation.

Is the Model Stationary or Nonstationary?

  • stationary model: the model does not change over time;
  • nonstationary model: the model changes over time.

This book only considers stationary models.

Relationship Between MDP and Markov Process

Once the policy is fixed, the MDP degenerates into a Markov process, MP.
If the state is finite or countable, the MP is also called a Markov chain.

This book mainly considers finite MDPs: both the number of states and the number of actions are finite.

Agent-Environment Interaction

  • agent: the decision-maker, able to perceive states, maintain a policy, and execute actions;
  • environment: everything outside the agent;
  • after the agent executes an action, the environment returns a new state and reward;
  • forming a closed loop.

1.8 Chapter Summary

This chapter used the grid world example to introduce basic concepts of reinforcement learning, and then formalized them using an MDP.

Core concepts include:

  • state, action, state transition
  • policy
  • reward
  • trajectory, return, episode
  • discounted return
  • MDP, Markov property
  • agent-environment interaction

These concepts are the foundation of subsequent chapters.
Subsequently, starting from these concepts, we will introduce state value, Bellman equation, optimal policy, value iteration, policy iteration, Monte Carlo, temporal difference, value function approximation, policy gradient, and Actor-Critic.

1.9 Selected Q&A

Q1: Can rewards all be negative or all be positive?

Yes.
What determines encouragement or discouragement is the relative reward value, not the absolute reward value.

For example, add -2 to all original rewards:

  • r_{\text{boundary}}=-3
  • r_{\text{forbidden}}=-3
  • r_{\text{target}}=-1
  • r_{\text{other}}=-2

Although all are negative, the optimal policy remains unchanged.
The reason is that the optimal policy is invariant to affine transformations of rewards.
This will be proved in detail in Section 3.5.

Q2: Is the reward a function of the next state?

The reward actually depends on s,a,s'.
But s' is determined by s,a, so it can be written as:

p(r|s,a)=\sum_{s'} p(r|s,a,s')p(s'|s,a)

The advantage of writing it this way is that it facilitates establishing the Bellman equation.

Quick Reference of Key Formulas in This Chapter

State space:

\mathcal{S}=\{s_1,\ldots,s_9\}

Action space:

\mathcal{A}=\{a_1,\ldots,a_5\}

State transition probability:

p(s'|s,a),\quad \sum_{s'}p(s'|s,a)=1

Reward probability:

p(r|s,a),\quad \sum_r p(r|s,a)=1

Policy:

\pi(a|s),\quad \sum_a \pi(a|s)=1

Markov property:

p(s_{t+1}|s_t,a_t,\ldots)=p(s_{t+1}|s_t,a_t)

Discounted return:

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

Common Pitfalls in This Chapter

  1. Immediate reward is not equal to long-term return.
    Do not look only at one-step reward; look at cumulative discounted return.

  2. A policy is a conditional probability, not the action itself.
    A deterministic policy is only a special case of a stochastic policy.

  3. Tabular representations can only describe deterministic transitions and rewards.
    The general case requires conditional probabilities.

  4. The target state does not necessarily terminate.
    This book treats the target state as an ordinary state, where rewards can be obtained repeatedly, so a discount rate is needed.

  5. After fixing the policy, the MDP degenerates into an MP.
    This is the relationship between an MDP and a Markov process.

  6. Affine transformations of rewards do not change the optimal policy, but they do change state values.
    This will be rigorously proved later.

[file content end]