The mathematical foundation of RL — a 5-tuple that describes how states, actions, probabilities, rewards, and discounting combine to define the problem every RL algorithm solves.
Adjust γ to see how value function changes. Low γ = myopic; high γ = far-sighted.
The 5-tuple that every RL problem reduces to.
An environment has the Markov property if the future depends only on the current state and action, not on any history leading up to it:
P(st+1 | st, at) = P(st+1 | s0, a0, ..., st, at)
This is not always true in the real world — but it is a powerful simplification. If the state captures enough information, the Markov property holds or is a close enough approximation. It means you only need to track the current state, not the entire trajectory.
| Symbol | Name | Meaning |
|---|---|---|
| S | State space | The set of all possible states the agent can be in |
| A | Action space | The set of all actions the agent can take |
| P | Transition function | P(s′|s,a) = probability of reaching s′ from s after action a |
| R | Reward function | R(s,a,s′) = immediate reward for the (s,a,s′) transition |
| γ | Discount factor | γ ∈ [0,1) controls how much future rewards are discounted |
A policy maps states to action probabilities: π(a|s) = P(A=a | S=s). A deterministic policy always picks the same action in a given state: a = π(s). A stochastic policy samples from a distribution, which is useful during exploration.
The agent’s goal is to find the optimal policy π* that maximises the expected return from every state.
The value function tells us how good it is to be in a state under a given policy:
vπ(s) = E[Gt | St=s, π] = E[rt + γrt+1 + γ2rt+2 + ... | St=s, π]
The discount factor γ makes future rewards worth less than immediate ones. With γ=0 the agent is completely myopic and only cares about the next reward. With γ→1 it treats all future rewards equally — valid for finite episodes but risky for infinite-horizon tasks.
The value function satisfies a recursive relationship called the Bellman equation:
vπ(s) = Σa π(a|s) Σs' P(s'|s,a) [R(s,a,s') + γ · vπ(s')]
This says: the value of a state is the expected immediate reward plus the discounted value of the next state. It expresses every state’s value in terms of its neighbours — which is what makes it solvable.
Where vπ(s) asks “how good is this state?”, qπ(s,a) asks “how good is taking action a in state s?”:
qπ(s,a) = Σs' P(s'|s,a) [R(s,a,s') + γ · vπ(s')]
Q-functions are more useful in practice because they let the agent choose actions without needing the model P(s'|s,a). In Q-Learning and DQN, the agent learns Q directly and picks actions as a = argmaxa Q(s,a).
A policy π* is optimal if vπ*(s) ≥ vπ(s) for all states s and all policies π. There is always at least one deterministic optimal policy. The Bellman optimality equations characterise it:
v*(s) = maxa Σs' P(s'|s,a) [R(s,a,s') + γ · v*(s')]
For small MDPs, this can be solved directly using dynamic programming (policy iteration or value iteration). For large or continuous state spaces, RL algorithms like Q-Learning approximate the solution.
For a fixed deterministic policy, the Bellman equation becomes a linear system:
vπ = Rπ + γ Pπ vπ ⇒ vπ = (I − γ Pπ)−1 Rπ
This is the closed-form solution: invert a matrix once and read off all state values simultaneously. Only tractable for small S (hundreds, not millions). The VzCode demo below solves a 4-state MDP this way.
Say the answer out loud before you reveal it — recalling it is what makes it stick.
What is the Markov property and why does it matter for MDPs?
What is the difference between v_π(s) and q_π(s,a)?
Why is the discount factor γ important in the Bellman equation?
What does it mean for a policy to be optimal?
MDP = (S,A,P,R,γ). Markov property: next state depends only on current state+action. Value function v_π(s) = E[G_t|S=s,π]. Bellman: v(s) = Σ_a π(a|s) Σ_s' P(s'|s,a)[R+γv(s')]. Matrix solution: v = (I-γP)^{-1}R for small MDPs.