Reinforcement Learning Introduction

Why RL exists (motivation)

Many problems are not “predict the right label once.” They are “make a sequence of choices where today’s choice changes tomorrow’s situation.”

Examples:

• •A robot chooses torques now; that changes its position later.
• •A recommender chooses what to show; that changes user behavior and future data.
• •A game-playing agent moves a piece; that changes the board and future options.

The core difficulty: you do not get direct labels for the best action. Instead, you get rewards that may be delayed and may depend on long-term consequences.

RL in one sentence

Reinforcement learning is the study of how an agent can learn a behavior (a policy) that maximizes expected long-run reward by interacting with an environment.

The minimal loop

At each time step t:

1. 1)The agent observes a state sₜ.
2. 2)The agent picks an action aₜ (possibly randomly).
3. 3)The environment transitions to a new state sₜ₊₁.
4. 4)The agent receives a reward rₜ₊₁.

Over time, the agent should choose actions that lead to higher total reward.

Key ingredients (conceptual vocabulary)

• •State (s): A summary of “what matters now.” In a clean formulation, it contains enough information to predict the future (in distribution) given an action.
• •Action (a): A choice available to the agent.
• •Reward (r): A scalar feedback signal indicating immediate desirability.
• •Policy (π): A rule for choosing actions; often written π(a | s).
• •Return (G): The total reward accumulated into the future (often discounted).

What makes RL distinct

RL combines:

• •Uncertainty (transitions and rewards may be stochastic)
• •Control (your actions influence what data you see)
• •Long horizons (credit assignment across time)

A helpful comparison:

Relationship to prerequisites

You already know Markov chains: P(s′ | s). RL generalizes this by adding actions: P(s′ | s, a). The agent’s policy π(a | s) effectively induces a Markov chain over states (because actions are chosen as a function of the current state).

You also know expected value. RL objectives are expectations over random trajectories:

• •randomness from the environment transitions
• •randomness from stochastic policies

So the core RL question becomes: Which policy π maximizes expected return?

Why we need a formal model

If you want to reason about long-term consequences, you need a framework that says:

• •what information you have now (state)
• •what choices you can make (actions)
• •how the world responds (transition probabilities)
• •how success is measured (rewards)

That framework is the Markov Decision Process (MDP).

The MDP components

An MDP is commonly specified by (S, A, P, R, γ):

• •S: set of states
• •A: set of actions
• •P(s′ | s, a): probability of next state s′ given current state s and action a
• •R: reward signal (often R(s, a, s′) or expected reward r(s, a))
• •γ ∈ [0, 1): discount factor

Even if the environment is deterministic, P(s′ | s, a) can encode that by putting probability 1 on the deterministic next state.

The Markov property (what “state” really means)

The Markov property says that the future depends on the past only through the present state:

P(sₜ₊₁ | s₀, a₀, …, sₜ, aₜ) = P(sₜ₊₁ | sₜ, aₜ)

Intuition: sₜ must contain all decision-relevant information from history.

This is not always true for raw observations (e.g., pixels). In practice, RL often deals with partial observability, but this intro node focuses on the MDP setting.

Rewards vs. goals

Rewards are a design choice (or a measurement) that encodes what we want. A reward is not the same as a goal:

• •A goal might be “win the game.”
• •A reward might be +1 for winning, 0 otherwise.

Reward shaping can make learning easier but can also change the optimal behavior if done carelessly.

Return: what RL actually maximizes

Immediate reward is not enough because actions can have long-term effects. We define the return from time t:

Gₜ = rₜ₊₁ + γ rₜ₊₂ + γ² rₜ₊₃ + … = ∑_{k=0}^{∞} γ^k rₜ₊₁₊k

• •γ close to 0 emphasizes immediate rewards.
• •γ close to 1 emphasizes long-term rewards.

Why discounting helps:

• •mathematically: makes infinite sums finite under mild conditions
• •practically: encodes preference for sooner rewards and reduces variance

Trajectories and expectations

A trajectory is a random sequence:

s₀, a₀, r₁, s₁, a₁, r₂, s₂, …

Given a policy π(a | s) and dynamics P(s′ | s, a), the return Gₜ becomes a random variable. RL optimizes an expected return:

J(π) = Eπ[ G₀ ]

The expectation Eπ[·] is taken over:

• •actions drawn from π(a | s)
• •next states drawn from P(s′ | s, a)
• •rewards drawn from the reward distribution (if stochastic)

From policy to induced Markov chain

With a fixed policy π, the probability of transitioning from state s to s′ becomes:

Pπ(s′ | s) = ∑_{a∈A} π(a | s) P(s′ | s, a)

This is exactly a Markov chain transition rule—so your Markov chain knowledge applies.

Deterministic vs stochastic policies

A policy can be:

• •Deterministic: a = μ(s) (always choose the same action in s)
• •Stochastic: π(a | s) gives probabilities

Stochastic policies matter because:

• •exploration: you sometimes need randomness to discover better outcomes
• •optimality: in some MDPs (especially with partial observability or certain constraints), stochasticity can be beneficial

A concrete mini-example: “two routes”

Imagine a commute with two actions:

• •a = Safe: always get reward 1
• •a = Risky: get reward 3 with probability 0.5, else reward 0

If this were a one-step problem, you’d compare expected reward:

E[Risky] = 0.5·3 + 0.5·0 = 1.5, so Risky is better.

But with state transitions and long horizons, the best choice depends on how today’s action changes tomorrow’s state distribution. That’s the RL leap from bandits to MDPs.

What you should internalize

MDP thinking is a discipline:

• •Clearly separate what you control (actions via π)
• •From what you don’t (P and reward stochasticity)
• •And define success as expected return over time

Why value functions are the central tool

The agent’s goal is global: maximize expected return over a long horizon.

But decision-making is local: at state s, you must pick an action now.

A value function bridges this gap by summarizing the long-term consequences of being in a state or taking an action.

State-value and action-value

Given a policy π:

State-value function (how good is state s under π?):

Vπ(s) = Eπ[ Gₜ | sₜ = s ]

Action-value function (how good is taking action a in s under π?):

Qπ(s, a) = Eπ[ Gₜ | sₜ = s, aₜ = a ]

These expectations are over future actions from π and transitions from P.

The “one-step lookahead” idea

Start from the definition of return:

Gₜ = rₜ₊₁ + γ Gₜ₊₁

Now take expectations to relate values across time.

Deriving the Bellman expectation equation for Vπ

By definition:

Vπ(s) = Eπ[ Gₜ | sₜ = s ]

Substitute Gₜ = rₜ₊₁ + γ Gₜ₊₁:

Vπ(s)

= Eπ[ rₜ₊₁ + γ Gₜ₊₁ | sₜ = s ]

= Eπ[ rₜ₊₁ | sₜ = s ] + γ Eπ[ Gₜ₊₁ | sₜ = s ]

But Gₜ₊₁ depends on sₜ₊₁, and future actions follow π, so:

Eπ[ Gₜ₊₁ | sₜ = s ] = Eπ[ Vπ(sₜ₊₁) | sₜ = s ]

So:

Vπ(s) = Eπ[ rₜ₊₁ + γ Vπ(sₜ₊₁) | sₜ = s ]

Write the expectation explicitly over actions and next states:

Vπ(s) = ∑_{a∈A} π(a | s) ∑_{s′∈S} P(s′ | s, a) [ r(s, a, s′) + γ Vπ(s′) ]

This is a Bellman expectation equation: a self-consistency condition.

Bellman expectation equation for Qπ

Similarly:

Qπ(s, a) = ∑_{s′} P(s′ | s, a) [ r(s, a, s′) + γ ∑_{a′} π(a′ | s′) Qπ(s′, a′) ]

Interpretation:

• •choose a
• •environment moves to s′ and gives reward
• •then you continue following π

Advantage: comparing actions in the same state

Often you care about which action is better than the policy’s average behavior.

Define the advantage:

Aπ(s, a) = Qπ(s, a) − Vπ(s)

• •Aπ(s, a) > 0: better than average under π
• •Aπ(s, a) < 0: worse than average under π

This will matter later when learning policies.

Optimal value functions (preview)

RL is usually about finding an optimal policy π*.

Define optimal state value:

V*(s) = maxπ Vπ(s)

and optimal action value:

Q*(s, a) = maxπ Qπ(s, a)

These satisfy Bellman optimality equations (you’ll go deeper in the MDP node you unlock):

V(s) = max_{a} ∑_{s′} P(s′ | s, a) [ r(s, a, s′) + γ V(s′) ]

and

Q(s, a) = ∑_{s′} P(s′ | s, a) [ r(s, a, s′) + γ max_{a′} Q(s′, a′) ]

Important pacing point: you do not need to solve these yet; you need to recognize what they mean:

• •V answers “How good is this state?”
• •Q answers “How good is this action here?”
• •Bellman equations formalize “reward now + value later.”

Value functions as fixed points

A subtle but powerful view: Bellman equations define a mapping (an operator) whose fixed point is Vπ.

Why that matters later:

• •We can compute values by repeated updates (dynamic programming)
• •Or estimate them from samples (TD learning)

On-policy vs off-policy (terminology you’ll meet)

• •On-policy: evaluate/improve the same policy you use to collect data
• •Off-policy: learn about a target policy while behaving differently (e.g., exploratory behavior)

You can already see the need: if π is deterministic and suboptimal, you might never see better actions. Stochasticity and off-policy ideas help address that.

Two big families: planning vs learning

Once you have MDP + value functions, there are two broad approaches.

This node is an intro, so focus on the shape of the problems.

Exploration vs exploitation (the unavoidable tension)

If you always take the best-known action, you may miss a better one.

If you explore too much, you waste reward.

This tension is sharper in MDPs because:

• •exploration changes which states you visit
• •some rewards are only reachable after sequences of correct actions

A policy π(a | s) that is stochastic can encode exploration directly.

Credit assignment (why delayed reward is hard)

Suppose reward arrives only at the end of an episode (e.g., win/loss). Which earlier actions deserve credit?

Value functions address this by propagating reward information backward through the Bellman structure:

• •if s′ is valuable, then actions leading to s′ become valuable
• •states leading to those actions become valuable, etc.

Episodes, continuing tasks, and termination

Some environments have terminal states (games), others run forever (control systems).

• •Episodic: return is finite sum until termination
• •Continuing: often use discounting γ < 1, or average-reward formulations

In episodic tasks with terminal state s_T, it’s common to define V(s_T) = 0 (no future reward after terminal).

Where vectors show up (a preview of function approximation)

In small MDPs, you can store V(s) in a table.

But real problems have huge state spaces. Then we approximate:

• •V(s) ≈ V(s; w) where w is a parameter vector
• •π(a | s) ≈ π(a | s; θ)

Even though this node is conceptual, it helps to see why vectors matter:

• •learning becomes optimization over w or θ
• •generalization becomes crucial

Connection to the next node: Markov Decision Processes

This intro has emphasized what the objects are:

• •MDP components (S, A, P, R, γ)
• •policies π(a | s)
• •values Vπ and Qπ

The next node will go deeper on:

• •Bellman equations as linear systems / fixed points
• •how to solve for Vπ given π and P
• •how to compute optimal policies

Think of this node as learning the language and the “units of thought” you’ll use later.