RL fundamentals and MDPs

The big idea

In supervised learning every example comes with the right answer. Nobody gives a chess player the right move for every position, a thermostat controller the right valve setting for every minute, or a robot the right motor torque for every millisecond. What they get is feedback on how things went: a win or a loss at the end of the game, an energy bill and a comfort complaint, a fall or a successful step. Reinforcement learningLearning to act by trial and error: an agent interacts with an environment, receives rewards, and improves its policy to maximize total reward over time. RL for short. (RL) learns to act from that kind of feedback.

Think of training a dog. You cannot explain what you want; you can only reward the behaviour when it happens, and the dog has to work out which of the things it just did earned the treat. Two things make this hard. Rewards are often delayed, so the learner must assign credit to actions taken long before. And the learner's own actions decide what it gets to see next, so it must choose between doing what has worked so far and trying something that might work better.

How it works

Step 1: The agent-environment loop

At each time step $t$ the agent observes a stateEverything the agent uses to choose an action at one moment: a board position, sensor readings, the user's recent history. $s_t$, picks an actionA choice the agent makes at one step, from a discrete set (move left) or a continuous range (apply 0.3 newtons). $a_t$, and the environment returns a rewardA single number the environment returns after each action, saying how good the immediate outcome was. The agent's goal is to maximize the total over time. $r_{t+1}$ and the next state $s_{t+1}$. The loop repeats until the episode ends (a game finishes, a robot falls) or forever, for a continuing task such as cooling a building.

The reward is the only goal signal. Everything you want the agent to do must be expressed as reward, which is both the strength of RL and its main trap: an agent will maximize exactly what you reward, including loopholes you did not foresee.

Step 2: Return and discounting

The agent does not maximize the next reward; it maximizes the returnThe total of future rewards from a time step on, usually discounted: G_t = r_t+1 + gamma r_t+2 + gamma^2 r_t+3 + ..., the sum of rewards from now on. With a discount factorA number gamma between 0 and 1 that multiplies each later reward once more, so a reward k steps away counts gamma^k as much as one now. $\gamma$ between 0 and 1:

A worked example with $\gamma =0.9$: rewards of 0, 0, 0, then 10 give $G=0.9^3\times 10=7.29$. A reward of 1 right now gives $G=1$. So the agent should take the long route to the 10. With $\gamma =0.5$, the same route is worth $0.5^3\times 10=1.25$, still slightly better than 1, and one more step of delay would flip the choice. Discounting keeps returns finite for continuing tasks, and since ${\sum }_k{\gamma }^k=1/(1-\gamma )$, it acts like a horizon of about $1/(1-\gamma )$ steps: 10 steps at 0.9, 100 at 0.99.

Step 3: Policies and value functions

A policyThe agent's rule for choosing actions: a mapping from states to actions, or to probabilities over actions, written pi(a | s). $\pi (a\mid s)$ says what the agent does in each state, deterministically or as probabilities. Two functions measure how good a policy is:

• The state value $V^{\pi }(s)$: the expected return starting in $s$ and following $\pi$.
• The action valueThe expected return from taking action a in state s and following the policy afterwards, written Q(s, a). Choosing the action with the highest Q gives a greedy policy. $Q^{\pi }(s,a)$: the expected return from taking action $a$ in $s$, then following $\pi$.

$Q$ is the more useful one when you do not know the environment's dynamics: with $Q$ in hand, acting well is just picking $\arg {\max }_{a}Q(s,a)$, with no need to predict where actions lead. Both satisfy a Bellman equation that links a state to its successors:

Replace the average over the policy's actions with a max and you get the optimality equation from Sequential decisions: MDPs (bridge to RL) , whose solution $V^{\ast }$ gives the best possible policy.

Step 4: The Markov decision process

A Markov decision processA model of sequential decision making: states, actions, transition probabilities P(s' | s, a), rewards, and a discount factor. (MDP) packages all of this: states $S$, actions $A$, transition probabilities $P(s^{\prime }\mid s,a)$, rewards and the discount $\gamma$. "Markov" means the next state depends only on the current state and action, not on how you got there. If your observation leaves out something that matters (a single video frame does not show which way the ball is moving), stack recent observations or keep a memory until the state is Markov enough.

What makes RL different from the planning of Sequential decisions: MDPs (bridge to RL) is that the agent does not know $P$ or the rewards. It has to learn from samples of experience. Methods split into:

• Value-based: learn $Q$, act greedily on it (Q-learning and deep Q-networks, later in this module).
• Policy-based: adjust the policy's parameters directly toward higher return (policy gradients, PPO).
• Actor-critic: both at once, a policy that acts and a value function that judges.
• Model-based: learn $P$ and the rewards, then plan with the learned model.

Going deeper

Code: evaluate policies, check by simulation, find the best one

import numpy as np

# A corridor MDP: cells 0..6, start in cell 2. Cell 0 is an exit worth +1, cell 6 an exit worth +10.
# Actions: 0 = left, 1 = right. A move goes the wrong way with probability 0.1. Other steps pay 0.
N, START, SLIP = 7, 2, 0.1
EXIT = {0: 1.0, 6: 10.0}

def outcomes(s, a):                          # list of (probability, next state, reward)
    step = -1 if a == 0 else 1
    out = []
    for p, d in [(1 - SLIP, step), (SLIP, -step)]:
        s2 = s + d
        out.append((p, s2, EXIT.get(s2, 0.0)))
    return out

def evaluate(policy, gamma):                 # Bellman expectation: V(s) = sum_a pi(a|s) sum p [r + gamma V(s')]
    V = np.zeros(N)
    for _ in range(500):
        V = np.array([0.0 if s in EXIT else
                      sum(pa * sum(p * (r + gamma * V[s2]) for p, s2, r in outcomes(s, a)) for a, pa in enumerate(policy[s]))
                      for s in range(N)])
    return V

def monte_carlo(policy, gamma, episodes=4000, seed=0):   # average discounted return of real episodes
    rng, total = np.random.default_rng(seed), 0.0
    for _ in range(episodes):
        s, G, k = START, 0.0, 0
        while s not in EXIT:
            a = rng.choice(2, p=policy[s])
            p, s, r = outcomes(s, a)[0 if rng.random() < 1 - SLIP else 1]
            G += gamma ** k * r; k += 1
        total += G
    return total / episodes

policies = {"always left": [[1, 0]] * N, "always right": [[0, 1]] * N, "random": [[0.5, 0.5]] * N}
for gamma in [0.5, 0.9]:
    print(f"gamma {gamma}: value of the start cell")
    for name, pi in policies.items():
        print(f"  {name:13s} V = {evaluate(pi, gamma)[START]:6.3f}   Monte Carlo {monte_carlo(pi, gamma):6.3f}")
    Q = lambda s, a, V: sum(p * (r + gamma * V[s2]) for p, s2, r in outcomes(s, a))
    V = np.zeros(N)
    for _ in range(500):                     # value iteration: V(s) = max_a Q(s, a)
        V = np.array([0.0 if s in EXIT else max(Q(s, 0, V), Q(s, 1, V)) for s in range(N)])
    best = "".join("." if s in EXIT else "<>"[int(Q(s, 1, V) > Q(s, 0, V))] for s in range(N))
    print(f"  optimal policy {best}, V(start) = {V[START]:.3f}")

gamma 0.5: value of the start cell
  always left   V =  0.424   Monte Carlo  0.427
  always right  V =  0.905   Monte Carlo  0.920
  random        V =  0.246   Monte Carlo  0.237
  optimal policy .<>>>>., V(start) = 0.927
gamma 0.9: value of the start cell
  always left   V =  0.861   Monte Carlo  0.861
  always right  V =  6.614   Monte Carlo  6.657
  random        V =  1.883   Monte Carlo  1.847
  optimal policy .>>>>>., V(start) = 6.614

A corridor of 7 cells. The agent starts in cell 2; cell 0 is an exit worth +1 and cell 6 an exit worth +10; each move goes the wrong way with probability 0.1. The code evaluates three fixed policies with the Bellman expectation equation, checks each with a Monte Carlo average over 4,000 simulated episodes, and finds the optimal policy with value iteration.

• The Bellman equation and simulation agree to within sampling noise: always right is worth 0.905 by the equation and 0.920 by simulation at $\gamma =0.5$, and 6.614 and 6.657 at $\gamma =0.9$. That is what value means: an expected return.
• The random policy is poor (0.246 and 1.883): wandering wastes discount.
• The discount changes the optimal policy. At $\gamma =0.9$ every cell heads right, for the 10. At $\gamma =0.5$, cell 1 heads left for the nearby 1, because the 10 is five risky steps away, and the optimal start value 0.927 beats always-right's 0.905 because a slip into cell 1 is followed by grabbing the +1.

Designing rewards

A reward function is a specification, and agents exploit specifications. Reward a cleaning robot for picking up dirt and it may learn to dump dirt in order to pick it up again. Common defences: reward the outcome you want rather than a proxy for it, keep rewards simple, add small costs for time or energy, and watch the learned behaviour, not just the reward curve. Shaping rewards (extra rewards for progress) can speed learning but can also change the optimal policy if done carelessly.

Exploration

An agent that only does what currently looks best never learns whether anything else is better. Every RL method needs some exploration: random actions some of the time, optimism toward untried actions, or noise in a stochastic policy. The next lesson studies this trade-off in its simplest form.

Trade-offs

Common mistakes

• Rewarding a proxy (points scored, dirt collected) and being surprised when the agent games it.
• Confusing reward (one step) with return (the discounted sum) and value (the expected return).
• Using a state that is not Markov, such as a single frame, so the agent cannot tell situations apart.
• Picking $\gamma$ by habit. It sets the effective horizon; match it to how far ahead consequences matter.
• Forgetting exploration, so the agent settles on the first thing that worked.

Where you will see this

The same loop describes a game-playing program choosing moves, a robot arm choosing torques, a data-centre controller choosing cooling settings and a recommender choosing what to show over a user's many visits. Language model fine-tuning with human feedback treats the model as the policy and a learned preference score as the reward ( RLHF ). The standard reference for everything in this module is the textbook Reinforcement Learning: An Introduction by Sutton and Barto, whose second edition (2018) is free to read online.

Check yourself

Recap