Action Chains & Rewards

Nobody tells this agent where the goal is. It starts with a policy that is pure noise — every direction equally likely — and the only feedback it ever gets is a number after each step. Press Run and watch it teach itself:

What it models. A tabular REINFORCE learner (chapter 4) with a value baseline (chapter 5’s critic, in miniature) on a 4×4 gridworld: step −1, trap −5, goal +10. Blue arrows are the policy π(a|s); the cell tint is the learned value V(s); the green curve is the return per episode climbing toward the dashed optimal line.

Knobs. Speed trades watchability for wall-clock learning; the learning rate α controls how hard each episode’s outcome yanks the policy.

Try this. Let it converge at the default α ≈ 0.1 (about 10 seconds at 5×; 28 of 30 calibration runs reach the optimal route), then reset and retry with α pushed to 2 or beyond. Now most runs lock onto a bad route: the entropy readout falls to 0 bits, the arrows freeze, and the curve flatlines below the optimal line — oversized updates destroy a policy irreversibly. Every later chapter exists to explain, and then prevent, what you just watched.

Reinforcement learning is built on the idea of an agent interacting with an environment over time. At each step, the agent observes a state, takes an action, and receives a reward. This loop — the action chain — is the core abstraction. The rest of this page builds the vocabulary to describe precisely what the demo above is doing.

The Markov Decision Process (MDP)

An MDP is defined by the tuple $(S, A, P, R, \gamma)$:

Symbol	Meaning
$S$	Set of states
$A$	Set of actions
$P(s' \mid s, a)$	Transition probability
$R(s, a)$	Reward function
$\gamma \in [0, 1)$	Discount factor

The Markov property means the future depends only on the current state, not on the history:

$$P(s_{t+1} \mid s_t, a_t, s_{t-1}, a_{t-1}, \ldots) = P(s_{t+1} \mid s_t, a_t)$$

The Action Chain

A trajectory (or episode) is a sequence of states, actions, and rewards:

$$\tau = (s_0, a_0, r_0, s_1, a_1, r_1, \ldots, s_T)$$

The agent’s behavior is governed by a policy $\pi(a \mid s)$ — a distribution over actions given a state. The goal of RL is to find the policy that maximizes the expected cumulative reward.

The Chain Rule of Probability for Trajectories

The probability of a trajectory $\tau$ under policy $\pi$ decomposes by the chain rule:

$$P(\tau \mid \pi) = P(s_0) \prod_{t=0}^{T-1} \pi(a_t \mid s_t) \cdot P(s_{t+1} \mid s_t, a_t)$$

Breaking this apart:

• $P(s_0)$ — the initial state distribution (given by the environment)
• $\pi(a_t \mid s_t)$ — the policy’s action probability (what we control)
• $P(s_{t+1} \mid s_t, a_t)$ — the environment’s transition dynamics (not in our control)

This factorization is fundamental. When we later derive the policy gradient, we’ll differentiate $\log P(\tau \mid \pi)$ with respect to the policy parameters $\theta$. The chain rule gives us:

$$\log P(\tau \mid \pi_\theta) = \log P(s_0) + \sum_{t=0}^{T-1} \left[ \log \pi_\theta(a_t \mid s_t) + \log P(s_{t+1} \mid s_t, a_t) \right]$$

When we take the gradient $\nabla_\theta$, the environment terms vanish (they don’t depend on $\theta$), leaving only:

$$\nabla_\theta \log P(\tau \mid \pi_\theta) = \sum_{t=0}^{T-1} \nabla_\theta \log \pi_\theta(a_t \mid s_t)$$

This is why policy gradient methods work without knowing the environment dynamics — we only need the gradient of our own policy.

Interactive Demo: Build a Trajectory

This is the same world the learner at the top of the page is solving — but now you are the policy. Navigate the agent to the goal, and watch the trajectory $\tau$ and the discounted return $G_0$ get constructed step by step — the exact quantities the learner uses to update itself after every episode:

(0,0)

(0,1)

(0,2)

Goal +10

(1,0)

(1,1)

Trap −5

(1,3)

(2,0)

(2,1)

(2,2)

(2,3)

🤖

(3,1)

(3,2)

(3,3)

↑

←↓→

Reset

Trajectory τ = (s, a, r, s', ...)

Navigate to ⭐ to build a trajectory...

Try different paths

The step cost is $-1$, the trap gives $-5$, and the goal gives $+10$. A shorter path gives a higher return — can you find the optimal trajectory?

Common misconception: “The Markov property requires forgetting the past.”

The Markov property does not mean the agent must lose its history — it means the state representation must summarize everything from the past that matters for predicting the future. In an Atari game, a single screen frame is not Markov (you can’t tell if the ball is moving up or down). The fix isn’t to “remember the past”; the fix is to redefine the state as a stack of 4 recent frames, which is Markov. This is the difference between MDP (state itself is Markov) and POMDP (you must build belief state, e.g. via an RNN). Identifying what to put into $s_t$ is half of solving an RL problem.

What’s Next

In the following pages, we’ll look at:

• States and Actions — how to think about the state and action spaces
• Rewards and Return — how rewards accumulate over time, and why discounting matters

References

• Sutton & Barto. Reinforcement Learning: An Introduction (2nd ed., 2018), ch. 3 — the canonical treatment of MDPs, returns, and the agent–environment loop. Free official PDF
• Bellman. Dynamic Programming. Princeton University Press, 1957 — where the recursive structure of sequential decision problems began.