Reinforcement Learning: AI That Plays Games

An agent that is never shown the answer key

In Grade 10 you trained models on labelled data: an image tagged "cat," a house price tagged with its true value. The model learned a mapping from input to a known correct output. In 2015, a team at DeepMind published a system that learned to play 49 different Atari 2600 games — Breakout, Space Invaders, Pong, Seaquest — from raw pixels and a joystick, with no labelled dataset of "correct moves" at all. The only feedback was the on-screen score, and the same network architecture and hyperparameters were used unchanged across all 49 games (Mnih et al., "Human-level control through deep reinforcement learning," Nature 518, 2015, pp. 529–533). The system matched or beat the level of a professional human games tester on the majority of the titles it was tested on.

Think about what makes this hard. Nobody told the agent that in Breakout the paddle should track the ball, or that in Pong hitting the ball late loses a point. It had to discover, purely from trial and error, which sequences of joystick movements eventually raise the score, and it had to do this even though the consequence of a single action (say, moving the paddle left at frame 400) might not show up as a reward until hundreds of frames later, when the ball finally returns. This is the central problem reinforcement learning (RL) solves: learning a good strategy from a scalar reward signal that arrives late, arrives sparsely, and gives no direct hint about which of the many actions taken since the last reward were actually responsible for it. This chapter builds the formal machinery — states, actions, rewards, policies, and value functions — that makes "which actions were responsible" a question you can actually answer with arithmetic, not guesswork.

Formalizing the problem: the Markov Decision Process

Every RL problem, from Atari to a warehouse-routing robot to a game of chess, is formalized as a Markov Decision Process (MDP): a tuple (S, A, P, R, γ).

S is the set of states — everything the agent can observe about the situation it is in (a screen of pixels, a chessboard configuration, a robot's grid position). A is the set of actions available to the agent in a given state. P(s′ | s, a) is the transition function: the probability of landing in state s′ given that the agent took action a in state s. R(s, a, s′) is the reward function: the scalar payoff received for that particular transition. γ (gamma), 0 ≤ γ < 1, is the discount factor, which controls how much the agent prefers a reward now over the same reward later.

The "Markov" in Markov Decision Process names a specific assumption: P(s′ | s, a) depends only on the current state s and action a, never on how the agent arrived at s. A chessboard position captures everything relevant to what happens next regardless of the sequence of moves that produced it — that is the Markov property, and it is why the state representation matters so much in practice: if your state description throws away information the future genuinely depends on (a poker agent's state that omits the betting history, for instance), the Markov assumption breaks and the whole framework's guarantees go with it.

A policy π is the agent's strategy: a mapping from states to actions. It can be deterministic, π(s) = a, or stochastic, π(a | s), giving a probability distribution over actions in each state. This chapter works mostly with deterministic policies because they are easier to compute by hand; the stochastic form π(a | s) is the one you will see parameterized directly by a neural network and trained by gradient ascent in the sibling chapter on policy gradient methods. Here, the policy falls out as a side effect of computing something more fundamental first: how much each state and action is actually worth.

Value functions: separating "reward" from "worth"

The reward r you get on a single step is not the same thing as how good your situation is. A state can have a low or even negative immediate reward attached to leaving it, yet be extremely valuable, because it is one step away from a big future payoff. The quantity that captures this is the value function.

The state-value function under policy π is the expected discounted sum of all future rewards, starting from state s and following π thereafter:

V^π(s) = E_π[ r_t+1 + γ r_t+2 + γ² r_t+3 + … | s_t = s ]

The action-value function Q^π(s, a) is the same expectation, but conditioned on taking a specific action a first and following π after that. Both satisfy a recursive identity called the Bellman equation, which is what makes them computable at all: the value of a state equals the immediate reward plus the discounted value of wherever you land next.

V^π(s) = Σ_s′ P(s′|s,π(s)) [ R(s,π(s),s′) + γ V^π(s′) ]

Swap "follow policy π" for "act optimally from here on," and you get the Bellman optimality equation, which defines the optimal value function V*:

V*(s) = max_a Σ_s′ P(s′|s,a) [ R(s,a,s′) + γ V*(s′) ]

This single equation is the engine behind everything that follows. It says the best you can do from state s is: try every available action, and for each one, add its immediate reward to the discounted optimal value of whatever state it leads to, then take the best of those totals. γ matters here because without a discount, a reward earned in step 1,000,000 would count exactly as much as one earned in step 1, and in an environment where episodes can run indefinitely, the sum of future rewards could diverge to infinity, making "the value of a state" . γ < 1 keeps the sum finite and encodes a real preference: an agent with γ = 0.99 is patient and will happily wait for a large delayed reward; an agent with γ = 0.5 is impatient and will trade a chunk of the eventual payoff for reward sooner.

Worked example: a robot on a five-cell charging track

Consider a simple deterministic MDP: a robot sits on one of five cells in a line, S0 through S4. Actions are Left and Right. Moving off the left end of the track (from S0) or off the right end (past S4, which does not happen here since S4 is terminal) leaves the robot where it was — the wall stops it. Every move that does not reach S4 costs a reward of −1 (battery drain). The move that enters S4 pays a reward of +10 and ends the episode; because the episode ends there, no further actions are ever taken from S4, so by convention V*(S4) = 0 — the +10 is credited entirely to the transition into S4, not to occupying it. We set γ = 0.9.

We solve for V* using value iteration: start with a guess V₀(s) = 0 for every state, then repeatedly apply the Bellman optimality equation as an update rule across all states simultaneously, V_k+1(s) = max_a [R(s,a,s′) + γV_k(s′)], until the values stop changing.

Trace sweep 1: from S3, moving Right earns +10 immediately and lands in the terminal state, so V₁(S3) = 10 + 0.9 × 0 = 10; every other state's best action still only sees zero-valued neighbours, so V₁ = −1 there. Sweep 2: now S2's Right action sees S3's freshly-updated value, V₂(S2) = −1 + 0.9 × 10 = 8. Sweep 3: S1's Right action picks up S2's new value, V₃(S1) = −1 + 0.9 × 8 = 6.2. Sweep 4: S0's Right action finally picks up S1's value, V₄(S0) = −1 + 0.9 × 6.2 = 4.58. Notice the pattern: the +10 reward at the far end propagates exactly one cell per sweep, because a Bellman backup only lets a state see one step further into the future than it could see before. A state three cells from the reward needs three sweeps before its value reflects that reward at all — this is precisely why value iteration on a large state space (a real game board, not five cells) needs many passes to converge, and why the "distance" from reward-bearing states, not just the size of the state space, governs how long convergence takes.

The converged values are V*(S0)=4.58, V*(S1)=6.2, V*(S2)=8, V*(S3)=10, V*(S4)=0, and the optimal policy recovered from them (always take the action whose Bellman backup gives the larger number) is: move Right in every state.

Common misconception: reward is not value

A very natural mistake is to evaluate an action by its immediate reward alone — "which action gives the best payoff right now?" Look again at state S2 in the worked example. Moving Left from S2 gives a reward of −1. Moving Right from S2 also gives a reward of −1. By immediate reward, the two actions are indistinguishable — a naive greedy-on-reward agent has no way to tell them apart, and might as well flip a coin. But Right is strictly correct: it is the first step on the only path to the goal, and its value is V*(S2) = 8, one of the highest in the whole environment.

Only at S3 — one step from the goal — does the immediate reward itself become informative. Everywhere else, the reward you're offered this instant is identical no matter which way you go, and the only thing that distinguishes a good action from a bad one is the discounted value of where it leads. This is precisely why value functions exist as a separate mathematical object from the reward function: reward tells you what happens on one transition, value tells you what a state or action is worth once every future transition it makes possible is accounted for. Any RL system — Q-learning, policy gradients, or the reward model inside RLHF — is, underneath, a machine for estimating value from reward, never a machine that reads value directly off reward.

From planning to learning: why exploration is unavoidable

Value iteration, above, is a planning algorithm: it requires the transition function P and reward function R to be fully known in advance, so the Bellman backup can be computed exactly. This is unrealistic for anything as complex as an Atari game — the agent doesn't have a formula for "what pixels appear next given this joystick input." What it has instead is the ability to act and observe what happens. Q-learning is the model-free counterpart: it learns Q(s,a) directly from sampled transitions (s, a, r, s′), with no knowledge of P or R at all, using the temporal-difference update rule

Q(s,a) ← Q(s,a) + α [ r + γ · max_a′ Q(s′,a′) − Q(s,a) ]

where α is a learning rate and the bracketed term is the TD error — the gap between what the agent's current estimate says Q(s,a) should be and what one fresh sample just suggested. Trace one update by hand, on the same track:

import random

# States 0..4; state 4 is terminal (the charging dock)
n_states = 5
actions = ["L", "R"]
gamma = 0.9
alpha = 0.5
epsilon = 0.2

Q = {(s, a): 0.0 for s in range(n_states) for a in actions}

def step(s, a):
    # deterministic grid-world transition + reward
    if a == "R":
        s_next = min(s + 1, 4)
    else:
        s_next = max(s - 1, 0)
    reward = 10.0 if s_next == 4 and s != 4 else -1.0
    return s_next, reward

def choose_action(s, Q, epsilon):
    # epsilon-greedy: normal action-selection rule (not used
    # below, where we force "R" to make the trace deterministic)
    if random.random() < epsilon:
        return random.choice(actions)
    q_l, q_r = Q[(s, "L")], Q[(s, "R")]
    return "R" if q_r >= q_l else "L"

# One manual Q-learning update, starting from state 2, forcing action "R"
s = 2
a = "R"
s_next, r = step(s, a)                              # s_next = 3, r = -1.0
best_next = max(Q[(s_next, "L")], Q[(s_next, "R")])  # both 0.0, untrained
td_target = r + gamma * best_next                    # -1.0 + 0.9*0.0 = -1.0
Q[(s, a)] += alpha * (td_target - Q[(s, a)])          # 0.0 + 0.5*(-1.0-0.0)

print(round(Q[(2, "R")], 3))

This prints -0.5. Compare that to the true optimal value we computed with full knowledge of the environment: V*(S2) = 8. A single sample, starting from an untrained (all-zero) Q-table, gives an estimate that is not just wrong but wrong in sign — it looks like a bad move. Only after Q(S3, Right) itself gets updated toward its true value of 10 (which requires actually visiting S3 and taking Right) does the backed-up estimate for Q(S2, Right) start climbing toward 8. Q-learning needs many repeated visits to every state-action pair before its estimates converge, and each visit requires the agent to actually take that action — which is the entire reason exploration is not optional.

If the agent always exploited its current (initially wrong) estimates — always picking the action with the highest known Q-value — it could get permanently stuck never trying the action that would have revealed the true payoff. The standard fix is ε-greedy action selection: with probability 1−ε, take the currently best-known action (exploit); with probability ε, take a uniformly random action (explore) instead. The choose_action function above implements exactly this. With ε = 0.2 and two available actions, the probability of taking the greedy action on any given step is (1−ε) + ε/|A| = 0.8 + 0.2/2 = 0.9 — the greedy action is favoured, but the other action still gets sampled 10% of the time, which is what lets its Q-value eventually correct itself. In practice ε is usually annealed rather than fixed: DQN's original Atari agents linearly decayed ε from 1.0 (pure exploration, useful when Q-estimates are all untrustworthy) down to 0.1 over the first million training frames, then held it fixed, so exploration is heaviest early and tapers off as the value estimates become reliable. The two other engineering pieces that made DQN work at Atari scale — a replay buffer that stores past transitions and samples them in random order to break the correlation between consecutive frames, and a separate, slowly-updated target network used to compute the max_a′Q(s′,a′) term so the learning target does not chase a constantly-shifting estimate — are what let this same tabular update rule scale from a five-cell track to a convolutional network reading raw game pixels.

Active recall

Attempt each question before reading its answer.

Q1. Write out the five-tuple that formally defines an MDP, and state in one sentence what the Markov property assumes.

Q2. Using V*(S2) = 8 and γ = 0.9, compute Q(S1, Right) directly from the Bellman equation (the reward for moving from S1 to S2 is −1).

Q3. With ε = 0.2 and two available actions, what is the probability the agent picks the non-greedy action on a given step?

Q4. A classmate says: "Since moving Right from S2 only gives a reward of −1, it must be a bad move." Explain what is wrong with this reasoning using the actual numbers from the worked example.

Q5. Name one concrete reason value iteration (as run in this chapter) could not be applied directly to an Atari game, and name the algorithm family that addresses it.

Q6. Suppose the discount factor for the charging-track MDP is changed from γ = 0.9 to γ = 0.5, with the reward structure unchanged. Recompute V*(S0), V*(S1), V*(S2), and V*(S3), and state whether the optimal policy (always move Right) still holds.

Worked answers

A1. (S, A, P, R, γ): the state set, action set, transition function P(s′|s,a), reward function R(s,a,s′), and discount factor. The Markov property assumes the transition probabilities depend only on the current state and action, never on the history of states that preceded them.

A2. Q(S1, Right) = R(S1, Right, S2) + γV*(S2) = −1 + 0.9 × 8 = −1 + 7.2 = 6.2. (This matches V*(S1) = 6.2 computed earlier, since Right is in fact the optimal action from S1.)

A3. P(exploit) = (1−ε) + ε/|A| = 0.8 + 0.2/2 = 0.9, so P(explore, i.e. take the non-greedy action) = 1 − 0.9 = 0.1, or equivalently ε/|A| = 0.1 directly, since with two actions "explore" has a 50% chance of landing on the greedy action anyway and only a 50% chance of landing on the actual alternative.

A4. The immediate reward for Right from S2 is indeed −1, but so is the immediate reward for Left from S2 — the two actions are tied on immediate reward and give no information about which is better. What separates them is value, not reward: V*(S2) = 8 because Right is one step closer, via S3, to the +10 terminal reward, discounted once (by γ = 0.9, since S3 — where the +10 becomes available — lies exactly one step away from S2), while Left leads back toward states with lower value. Judging an action by its one-step reward alone throws away exactly the information — the expected discounted future — that value functions exist to capture.

A5. Value iteration requires the transition function P(s′|s,a) and reward function R(s,a,s′) to be fully known in advance so the Bellman backup can be computed exactly; in an Atari game the agent has no such formula relating a joystick input to the next screen of pixels. Model-free methods such as Q-learning address this by learning Q(s,a) from sampled (s,a,r,s′) transitions gathered through actual interaction with the environment, with no model of P or R required.

A6. Recomputing via the same recursion V*(s) = −1 + γV*(s+1), with base case V*(S3) = 10 + γ×0 = 10 (unchanged, because this term does not depend on γ at all — S3's optimal value is fixed by the immediate +10 regardless of discounting): V*(S2) = −1 + 0.5×10 = 4; V*(S1) = −1 + 0.5×4 = 1; V*(S0) = −1 + 0.5×1 = −0.5. Every value downstream of S3 shrinks substantially, and V*(S0) actually flips sign, from +4.58 to −0.5 — with heavier discounting, the eventual +10 is worth so little by the time its discounted value reaches S0 that the accumulated −1 step costs outweigh it. Despite that, the optimal policy is unchanged: Right is still better than Left at every state, because Left's alternative is even worse (a robot that only ever moves Left settles into a fixed point of −1/(1−γ) = −2 at S0, worse than −0.5). The ripple from a single changed parameter reached every state's value, including a sign flip, without changing which actions are optimal.

Key Takeaways — Summary and Recap

Let us recap what we covered: the core ideas behind reinforcement learning: ai that plays games, how they connect to real-world applications, and why they matter for your journey in computer science. Remember these key points as you move forward. For competitive exam preparation (CBSE, JEE, BITSAT), focus on understanding the WHY behind each concept, not just the WHAT.