Markov Decision Processes

A Markov decision process models sequential choice under uncertainty. At time $t$, an agent observes state $S_t$, chooses action $A_t$, receives reward $R_{t+1}$, and moves to a new state $S_{t+1}$.

Defining Mechanism

An MDP is usually written as $(\mathcal{S},\mathcal{A},P,R,\gamma )$:

Component	Meaning
$\mathcal{S}$	possible states
$\mathcal{A}$	possible actions
$P(s^{\prime }\mid s,a)$	transition probability from state $s$ to next state $s^{\prime }$ after action $a$
$R(s,a,s^{\prime })$	expected immediate reward for that transition
$\gamma \in [0,1]$	discount factor for future rewards

The Markov assumption says the next transition depends on the current state and action, not on the full history:

$$P(S_{t+1}=s^{\prime },R_{t+1}=r\mid S_t,A_t,S_{t-1},A_{t-1},\dots )=P(S_{t+1}=s^{\prime },R_{t+1}=r\mid S_t,A_t).$$

This does not mean the world has no memory. It means the state representation should contain the information needed for prediction and control.

Return

The discounted return from time $t$ is

$$G_t=R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\cdots =\sum _{k=0}^{\infty }{\gamma }^k{R}_{t+k+1}.$$

If $\gamma =0.9$, a reward one step away keeps full weight, a reward two steps away has weight $0.9$, and a reward three steps away has weight $0.81$. Lower $\gamma$ makes the agent more short-sighted; higher $\gamma$ makes delayed consequences matter more.

Worked Scenario

In a lane-change decision, the state might include ego speed, adjacent-lane occupancy, distance to the lead vehicle, and road geometry. The actions are not labels; they change the future. Choosing “change left” affects the next state, which changes whether future acceleration is safe and whether the final route objective can be met.

Time	State summary	Action	Immediate reward	Future implication
$t$	slow lead car, left lane clear	move left	small lane-change cost	opens a faster lane
$t+1$	centered in left lane	accelerate	speed reward	increases following distance risk
$t+2$	faster speed, vehicle ahead	hold speed	comfort reward	avoids hard braking

The decision is sequential because the best action at $t$ depends on expected future rewards, not just the immediate reward.

Caveats

The hardest modeling choice is the state. If important information is hidden, the process becomes partially observable and the policy may need memory, belief-state tracking, recurrent models, or history windows. If the reward omits safety or long-term cost, the optimal policy for the MDP can still be wrong for the real task.

Connections

• Value Functions and Bellman Equations define expected return under an MDP.
• Q-Learning and DQN learn action values from transitions.
• Autonomous Driving often decomposes the full driving problem into perception, prediction, planning, and control rather than treating the whole stack as one unconstrained MDP.

References

• Sutton and Barto, 2018, Reinforcement Learning: An Introduction

Nav

Section — Reinforcement Learning

Value Functions and Bellman Equations →

Learning path — Reinforcement learning

← Reinforcement Learning Value Functions and Bellman Equations →