Reinforcement Learning · One focused lesson
First follow probability through a world. Then add choices and count the rewards of a journey.
Reading tips and color key
Start with the explanation and experiment. Open the symbol cards when you want the details. Teal: probabilities; blue: states; orange: actions; green: rewards; purple: values; gray: parameters and settings; crimson: losses and errors. Written labels give every symbol its role.
Before actions · Follow the probabilities
Markov chains: where can the next step lead?
Imagine many weather worlds with the same simple rule. A sunny world stays sunny with probability 0.8. A rainy world becomes sunny with probability 0.3. In this toy model, today’s weather contains all the information needed to predict tomorrow’s chances: that is the Markov property.
If every world starts sunny, the next day’s distribution is 80% sunny and 20% rainy. To advance another day, split each group according to its transition rule, then collect the contributions arriving at each destination.
Tomorrow: sunny
Sunny → sunny: 0.8 × 0.8 = 0.64
Rainy → sunny: 0.2 × 0.3 = 0.06
0.64 + 0.06 = 0.70
Tomorrow: rainy
Sunny → rainy: 0.8 × 0.2 = 0.16
Rainy → rainy: 0.2 × 0.7 = 0.14
0.16 + 0.14 = 0.30
Multiply along each arrow; add arrows arriving together. These are exact probability calculations for the model, not observed counts from a finite sample.
Equation anatomy · probability arriving at one destination · show / hide
| Symbols and jobs | Type and range | Example |
|---|---|---|
| \({\color{#006e78}{d}}_{\color{#525968}{t}}({\color{#1d4ed8}{i}})\): chance of state i at time t | Deterministic probability, 0–1; the distribution sums to 1 | Today’s sunny probability is 0.8 |
| \({\color{#006e78}{P}}_{{\color{#1d4ed8}{i}}{\color{#1d4ed8}{j}}}\): chance of moving from i to j | Fixed matrix entry, 0–1; each origin’s row sums to 1 | Rainy → sunny has probability 0.3 |
| \({\color{#1d4ed8}{i}},{\color{#1d4ed8}{j}},{\color{#525968}{t}},\sum\): origin, destination, time, add | State labels; nonnegative integer time; sum over all origins | For sunny tomorrow, add both incoming contributions |
One world’s next state is random; its distribution is a list of chances. The transition rule does not yet include choices. An MDP adds actions, so the chosen action helps determine which transition chances apply.
04 · Actions change what comes next
MDPs: from buttons to a world
In a maze, pressing right does more than earn a point. It changes where you stand, which changes your next choices. A shortcut might lead close to the flag but also close to a trap. Now we need to think about sequences of decisions.
A Markov decision process (MDP) describes situations, available actions, transition chances, rewards, and how we count the future. Markov means the current state and action contain all the information needed to predict the distribution of the next state and reward. It does not mean the next result is certain.
Tile (1, 1)
Move right →
Tile (1, 2)
Reward r = −1In this clear passage the move succeeds with P = 1. On slippery ground, the same state and action could branch to several next tiles. List those branches and their chances to build P(s′ | s, a). Add the allowed tiles, moves, reward rule, and discount to describe the world.
Equation anatomy · the environment description · show / hide
| Symbol | Meaning and kind | Form | Random? | Possible values | In code |
|---|---|---|---|---|---|
| \({\color{#172337}{\color{#1d4ed8}{\mathcal{S}}},{\color{#1d4ed8}{S}}_{\color{#525968}{t}},{\color{#1d4ed8}{S}}_{{\color{#525968}{t}}+1},{\color{#1d4ed8}{s}},{\color{#1d4ed8}{s}}’}\) | State set; current/next state variables; particular states | Set; scalar IDs or state vectors | State variables may vary by trajectory; specified states are fixed | Accessible tiles, including terminal states | state = row*width + col |
| \({\color{#172337}{\color{#9a4700}{\mathcal{A}}},{\color{#9a4700}{A}}_{\color{#525968}{t}},{\color{#9a4700}{a}}}\) | Action set; chosen action; candidate action | Set; discrete label here | Chosen action can be random; label fixed | Up, right, down, left | action = 1 |
| \({\color{#172337}{\color{#006e78}{P}},{\color{#006e78}{\Pr}}}\) | Transition function; probability operator | \({\color{#172337}{\color{#006e78}{P}}}\) returns one scalar chance | Fixed model describing random outcomes | 0–1; next-state probabilities sum to 1 | P[state][action][next] |
| \({\color{#172337}{\color{#087444}{r}}}\) | Expected reward given state, action, next state | Function with real scalar output | Deterministic for fixed model | Real reward units | expectedReward(s,a,next) |
| \({\color{#172337}{\color{#525968}{\gamma}},{\color{#525968}{t}}}\); \({\color{#172337}{\mid}}\) | Discount setting; time index; “given” | Scalar; integer; notation | Fixed | \({\color{#172337}{0\le{\color{#525968}{\gamma}}\lt 1}}\) here; \({\color{#172337}{\color{#525968}{t}}\ge0}\) | gamma = 0.9 |
State is not always observation. A robot’s camera image is an observation. The full state might include motion hidden from one picture. If yesterday’s wind affects tomorrow’s movement, tile position alone may be insufficient; add the relevant wind information to the state. A fully observed, fixed grid can use the tile ID as its state. A partially observed problem may require memory or a belief over states.
The transition model can be stored as a three-axis tensor: state × action × next state. Fix one action and you have a matrix. Pick one current and next state and you have one probability. A policy is the agent’s strategy: for each state, it supplies a distribution over actions. A transition model describes the world; a policy describes the chooser.
05 · A reward is one point; a return is the journey
Return and discounting
A move earns −1 now but helps you reach a flag worth 10 later. Judging only this instant misses the useful move. We need a score for the rewards still to come.
The return adds future rewards. A discount factor determines how much later rewards count relative to earlier ones. It is part of the objective we choose, not a probability that the next reward will happen.
Equation anatomy · a terminating episode · show / hide
| Symbol | Meaning and kind | Form | Random? | Possible values | In code |
|---|---|---|---|---|---|
| \({\color{#172337}{\color{#087444}{G}}_{\color{#525968}{t}},{\color{#087444}{G}}_{{\color{#525968}{t}}+1},{\color{#087444}{G}}_{\color{#525968}{T}}}\) | Return now, return next, terminal return | Scalar random variables; terminal zero | Generally random before the journey is known | Real reward units; terminal 0 | G = reward + gamma*G backward through episode |
| \({\color{#172337}{\color{#087444}{R}}_{{\color{#525968}{t}}+{\color{#525968}{k}}+1},{\color{#087444}{R}}_{{\color{#525968}{t}}+1}}\) | Future and next reward | Scalar random variables | May be stochastic or determined by a transition | Real numbers | rewards[t+1] |
| \({\color{#172337}{\color{#525968}{t}},{\color{#525968}{k}},{\color{#525968}{T}},{\color{#525968}{\gamma}}}\) | Current time, offset, terminal time, discount | Integer indices; scalar setting | Episode end can vary; discount fixed | \({\color{#172337}{0\le {\color{#525968}{t}}\lt {\color{#525968}{T}};\ {\color{#525968}{k}}\ge0;\ 0\le{\color{#525968}{\gamma}}\le1}}\) | gamma = 0.9 |
| \({\color{#172337}{\sum,{\color{#525968}{\gamma}}^{\color{#525968}{k}}}}\) | Add rewards; repeated discount multiplication | Operator; scalar weight | Deterministic for fixed indices | Weight 0–1; first weight 1 | weight *= gamma |
Try the numbers. Rewards 2 then 10 with discount 0.9 give return 2 + 0.9 × 10 = 11. The recursive version says “first reward plus discounted rest.” This simple regrouping is the seed of Bellman’s equation.
For a continuing task, the sum extends indefinitely. Bounded rewards and a discount below 1 keep it finite. A discount of 1 is useful for suitable terminating tasks, but needs conditions ensuring a finite expected return. An experiment stopped by a time limit is not automatically a true terminal state.
Be First to Comment