EasyCompilers

Vocabulary for this course

The terms the chapters assume, in plain words. You can open this from any chapter.

action
One choice the agent can make at a given moment, from a fixed set available to it.
agent
The learner: it sees a state, chooses an action and receives a reward.
discount factor
A number between zero and one that scales down later rewards, so a reward now is worth more than the same reward later.
environment
Everything outside the agent that responds to its actions and hands back a reward and a new state.
episode
One complete run from a starting state until the task ends, after which the agent starts again.
exploitation
Choosing the action that looks best right now, using only what has been learned so far.
exploration
Trying an action that may not be best, in order to learn whether something better exists.
Markov decision process
A task described by states, actions, rewards and the chances of moving between them, where the current state is enough to decide from.
policy
A rule that picks an action for each state; learning changes this rule, not the world.
Q-value
How good an action is in a given state: the average return from taking it and then following a fixed rule.
return
The total reward collected from this point onward, with later rewards scaled down by the discount factor.
reward
A number the environment sends after an action, saying how good that step was.
state
What the agent uses to decide; it must be complete enough that two situations needing different actions look different.
value
How good a state is: the average return from being there and then following a fixed rule.

Reinforcement learning from the ground up

Markov decision processes

Add states and transitions to a bandit and you get the standard model of sequential decisions: a table of consequences, a policy, and one equation that ties them together.

Part 3 of 10

Advanced16 min readBack to Courses

The world gets a memory

A Markov decision process is the bandit plus consequences. It is a set of states, a set of actions, a rule for what happens when you act, a reward for each transition, and a discount. The agent chooses; the world moves; the next choice starts from wherever the world landed. The word process is doing work: the sequence matters, not just the final state. It is the standard language for sequential decisions, and most of the vocabulary in this course is defined in it.

The Markov property is the assumption that makes this tractable: the next state and reward depend on the current state and action, and on nothing earlier. History matters only through the present. When that is false, the state is missing something, and no amount of learning will recover it. It is a claim about the representation, not about the world; a good state makes it true.

The transition table

For a finite problem the dynamics are a table: for each state and action, a list of possible next states with a probability and a reward. The probabilities in each row sum to one; the reward may be fixed or may itself be a distribution, but its expected value is what the equations use. The table is the model, and having it is what separates planning from learning. If you cannot write the row, you do not yet understand the action.

Writing the table is a useful discipline even when you will never have it. It forces you to say what the actions do, what is random, and where the reward is attached. Most bugs in a learned agent are bugs in this description, discovered late. A row that sums to 0.9 is a row that will quietly distort every value downstream. Check the rows before you trust the answer; the equations will happily propagate a broken model.

Reading the table from an environment

import gymnasium as gym

env = gym.make("FrozenLake-v1", is_slippery=True)
transitions = env.unwrapped.P

for next_state, probability, reward, done in transitions[0][2]:
    print(next_state, round(probability, 3), reward, done)

One row of the transition table

Run the calculation, then change the slip probability to 0.4 and confirm the expected reward and the distribution both move.

Output
Click "Run" to execute your code

A policy is a rule for choosing

A policy maps a state to an action, or to a distribution over actions. A deterministic policy is a lookup table; a stochastic one keeps probabilities so that it can remain uncertain, or so that it can explore without abandoning what it knows. The policy is the only object the agent truly controls. Everything else in the algorithm is a way of scoring or improving that mapping.

The policy is the thing being learned, and it is also the thing being evaluated. Value iteration and policy gradients differ mainly in how they represent it and how they improve it. Both are trying to find the policy whose expected return from every state is largest. A policy can be optimal from one state and terrible from another, which is why value is a function, not a number. Two policies can share a value function and still behave differently in states that are never reached.

Draw the states as circles and the transitions as arrows before writing any code. A diagram catches a missing action or a reward attached to the wrong edge faster than a debugger.

One equation holds it together

The value of a state under a policy is the reward you expect now, plus the discounted value of wherever you land. That is the Bellman expectation equation, and it is recursive: the value of each state is written in terms of the values of its successors. One line per state, all coupled, which is exactly a linear system. Solving it is policy evaluation, the subroutine inside almost every control method.

For a fixed policy the equation is linear, one line per state, and it has a unique solution whenever the discount is below one. You can solve it directly with linear algebra or approach it by repeated substitution. The second method is the one that scales, and it is the seed of everything in the next chapter. The first is useful for small problems and for checking the second.

Policy evaluation by substitution

Run fifty sweeps and watch the two values settle. Then change the discount to 0.5 and see how much closer to the immediate rewards they land.

Output
Click "Run" to execute your code

Check what you learned

One question at a time. A wrong answer explains itself — take another go.

Part 1 of 5

What does the Markov property assume?