Ahmed Haroon

Markov Decision Processes

A Markov Decision Process (MDP) models an agent that repeatedly chooses actions, receives rewards, and moves between states.

It is defined by the tuple:

(S,A,P_{sa},\gamma,R)

where:

$S$ is the set of states.
$A$ is the set of actions.
$P_{sa}$ are the state transition probabilities.
$\gamma$ is the discount factor.
$R$ is the reward function.

The reward may depend on both the state and action, $R(s,a)$ , or only on the state, $R(s)$ . We use $R(s)$ below for simplicity.

The Markov assumption says that once we know the current state and action, the distribution of the next state does not depend on the earlier history.

We also assume the MDP is stationary, so the same transition probabilities and reward function apply at every time step.

For an infinite-horizon discounted problem, we use:

0 \leq \gamma < 1

Values of $\gamma$ close to $1$ place more importance on future rewards.

The agent-environment interaction loop of a Markov decision process — At each step the agent takes an action $a_t$ , and the environment responds with a new state $s_{t+1}$ and a reward $R(s_t)$ .

The discounted sum of future rewards is called the return:

R(s_0) + \gamma R(s_1) + \gamma^2R(s_2) + \cdots

Our goal is to find a policy that maximizes the expected return:

\mathbb E \left[ R(s_0) + \gamma R(s_1) + \gamma^2R(s_2) + \cdots \right]

A policy:

\pi:S\to A

tells the agent which action to take in each state.

The value function $V^\pi(s)$ is the expected return when we start in state $s$ and then follow policy $\pi$ :

V^\pi(s) = \mathbb E \left[ R(s_0) + \gamma R(s_1) + \gamma^2R(s_2) + \cdots \mid s_0=s,\pi \right]

We write:

P_{sa}(s')

for the probability of moving to state $s'$ after taking action $a$ in state $s$ .

Bellman Equations and Dynamic Programming

The value function can then be written recursively using the Bellman equation:

V^\pi(s) = R(s) + \gamma \sum_{s'\in S} P_{s\pi(s)}(s') V^\pi(s')

The first term is the reward received now. The second term is the discounted expected value of the next state.

The optimal value function is the best value achievable over all policies:

V^*(s) = \max_\pi V^\pi(s)

It satisfies the Bellman optimality equation:

V^*(s) = R(s) + \max_{a\in A} \left( \gamma \sum_{s'\in S} P_{sa}(s') V^*(s') \right)

Once we know $V^*$ , we can recover an optimal policy by choosing the best action in each state:

\pi^*(s) = \arg\max_{a\in A} \left( \gamma \sum_{s'\in S} P_{sa}(s') V^*(s') \right)

For finite state and action spaces with known transition probabilities, two standard ways to compute an optimal policy are value iteration and policy iteration.

\textbf{Value Iteration}

\text{For each state }s,\text{ initialize }V_0(s)=0

\text{For }t=0,1,\ldots\text{, repeat until convergence \{}

\quad \text{For each state }s,\text{ set \{}

\quad\quad V_{t+1}(s) \leftarrow R(s) + \max_{a\in A} \left( \gamma \sum_{s'\in S} P_{sa}(s') V_t(s') \right)

\quad \text{\}}

\text{\}}

With bounded rewards and:

0 \leq \gamma < 1

the Bellman operator is a $\gamma$ -contraction, so value iteration converges to the unique optimal value function $V^*$ .

\textbf{Policy Iteration}

\text{Initialize }\pi\text{ randomly}

\text{Repeat until convergence \{}

\quad \text{Compute }V^\pi \qquad \textit{typically by solving a linear system}

\quad \text{For each state }s,\text{ set \{}

\quad\quad \pi(s) \leftarrow \arg\max_{a\in A} \left( \gamma \sum_{s'\in S} P_{sa}(s') V^\pi(s') \right)

\quad \text{\}}

\text{\}}

Policy iteration often reaches an optimal policy in fewer outer iterations than value iteration on small MDPs, but it is not universally faster.

Each policy-evaluation step solves a system of linear equations for $V^\pi$ , so the total runtime depends on both the number and cost of the iterations.

The algorithms above assume that the transition model is known.

If it is unknown but we can collect transitions from the environment, we can estimate it from data:

P_{sa}(s') = \frac{ \text{\# of times action }a\text{ was taken in state }s\text{ and led to }s' }{ \text{\# of times action }a\text{ was taken in state }s }

This estimate is defined only when the data contain visits to the state-action pair $(s,a)$ .

A behavior policy with poor coverage cannot estimate transitions for actions that are never taken.

Value Function Approximation

Tabular methods become impractical when the state space is continuous.

If a $d$ -dimensional state is discretized into $k$ values per dimension, we already get:

k^d

possible states.

Instead of storing one value for every state, we can approximate the value function with a parameterized function.

In a model-based approach, we first learn a model of the environment's dynamics from sampled trajectories.

Suppose we collect $n$ trajectories, each containing $T$ transitions:

s_0^{(1)} \xrightarrow{a_0^{(1)}} s_1^{(1)} \xrightarrow{a_1^{(1)}} s_2^{(1)} \xrightarrow{a_2^{(1)}} \cdots \xrightarrow{a_{T-1}^{(1)}} s_T^{(1)}

s_0^{(2)} \xrightarrow{a_0^{(2)}} s_1^{(2)} \xrightarrow{a_1^{(2)}} s_2^{(2)} \xrightarrow{a_2^{(2)}} \cdots \xrightarrow{a_{T-1}^{(2)}} s_T^{(2)}

\vdots

s_0^{(n)} \xrightarrow{a_0^{(n)}} s_1^{(n)} \xrightarrow{a_1^{(n)}} s_2^{(n)} \xrightarrow{a_2^{(n)}} \cdots \xrightarrow{a_{T-1}^{(n)}} s_T^{(n)}

Several sampled trajectories through a continuous state space — Each trial traces a trajectory of states linked by the actions taken. These transitions are the data used to fit the dynamics model $s_{t+1}=As_t+Ba_t$ .

We can use these trajectories to learn a linear model that predicts the next state from the current state and action:

s_{t+1} = As_t + Ba_t

Here $A$ describes how the current state affects the next state, while $B$ describes the effect of the action.

We can estimate $A$ and $B$ by minimizing the squared prediction error:

\arg\min_{A,B} \sum_{i=1}^n \sum_{t=0}^{T-1} \left\| s_{t+1}^{(i)} - \left( As_t^{(i)} + Ba_t^{(i)} \right) \right\|_2^2

This model predicts a single next state.

To model stochastic transitions, we add Gaussian process noise:

s_{t+1} = As_t + Ba_t + \epsilon_t

where:

\epsilon_t \overset{\mathrm{IID}}{\sim} \mathcal N(0,\Sigma)

This is a linear-Gaussian dynamics assumption: the process noise is independent of the current state and action, has zero mean, and has the same covariance at every transition.

Because:

\epsilon_t \sim \mathcal N(0,\Sigma)

the transition model is:

s_{t+1} \mid s_t,a_t \sim \mathcal N \left( As_t+Ba_t, \Sigma \right)

Therefore:

p(s'\mid s,a) = \mathcal N \left( s'; As+Ba, \Sigma \right)

where the right-hand side is the Gaussian density evaluated at the candidate next state $s'$ .

Fitted Value Iteration

We now have a model for predicting the next state, but we still cannot store $V(s)$ for every continuous state.

If the state space is continuous and the action space is small and discrete, we can combine the learned dynamics model with fitted value iteration.

The continuous-state Bellman update is:

V(s) \leftarrow R(s) + \gamma \max_{a\in A} \left( \int p(s'\mid s,a) V(s') \,ds' \right)

The sum from the discrete Bellman equation has become an integral because the next state is now continuous.

Because there are infinitely many possible states, we cannot store a separate value for each one.

Instead, we approximate the value function using features $\phi(s)$ :

V(s) = \theta^T\phi(s)

The features $\phi(s)$ may be hand-designed or produced by a nonlinear model.

At iteration $t$ , we first use the current value function $V_t$ to compute a Bellman target for each sampled state:

y_t^{(i)} = R(s^{(i)}) + \gamma \max_{a\in A} \left( \int p(s'\mid s^{(i)},a) V_t(s') \,ds' \right)

We then fit the next value function to these targets:

\theta_{t+1} = \arg\min_\theta \sum_{i=1}^n \left( y_t^{(i)} - \theta^T\phi(s^{(i)}) \right)^2

and set:

V_{t+1}(s) = \theta_{t+1}^T \phi(s)

The targets are computed using the frozen previous approximation $V_t$ and remain fixed while fitting $V_{t+1}$ .

Unlike exact tabular value iteration, fitted value iteration is approximate, so convergence is not guaranteed in general.

The integral in the Bellman target may also be difficult to compute exactly.

A simple approach is to approximate it using Monte Carlo samples from the learned transition model.

\text{Choose }n\text{ representative states } s^{(1)},\ldots,s^{(n)}

\text{Initialize } \theta_0\leftarrow0 \text{ and } V_0(s)\leftarrow\theta_0^T\phi(s)

\text{For }t=0,1,\ldots\text{, repeat until convergence \{}

\quad \text{For }i=1\text{ to }n\text{ \{}

\qquad \text{For each action }a\in A\text{ \{}

\qquad\qquad \text{Sample } s'_1,s'_2,\ldots,s'_m \sim p(\cdot\mid s^{(i)},a)

\qquad\qquad q_t(a) \leftarrow R(s^{(i)}) + \gamma \frac1m \sum_{j=1}^m V_t(s'_j)

\qquad \text{\}}

\qquad y_t^{(i)} \leftarrow \max_a q_t(a)

\quad \text{\}}

\quad \theta_{t+1} \leftarrow \arg\min_\theta \sum_{i=1}^n \left( y_t^{(i)} - \theta^T\phi(s^{(i)}) \right)^2

\quad V_{t+1}(s) \leftarrow \theta_{t+1}^T \phi(s)

\text{\}}