Intelligent Systems II · TEE · read

Markov decision process, policies and value functions

Unit 4 · MRP, MDP, policies and Bellman equations

Unit 4 · Markov reward process, Markov decision process, value functions, Bellman equations, applications

Read this	Meaning	Concrete example
π(a\|s)	Probability the policy chooses action a in state s	In room A: left .3, right .7
P(s′\|s,a)	Probability of the environment’s next state after that action	Right action reaches room B with probability .8
vπ(s)	Expected return starting in state s and following policy π	A number scoring the state
qπ(s,a)	Expected return if action a is taken first, then policy π is followed	One score for each possible first action
π in this chapter	A policy	Unlike π in a Markov-chain stationary distribution; context distinguishes them

The policy chooses an action; the transition model describes what happens after the action. They are two separate probability distributions. The worked examples use stationary Markov policies, depending on the current state and unchanged over time. More general policies may depend on time or history.

In one line: an MDP is an MRP in which the agent chooses actions; a policy says which action to choose, and value functions score how good a state or a state–action pair is under that policy.

Markov decision process

A Markov decision process (MDP) is a tuple $\langle\mathcal S,\mathcal A,P,R,\gamma\rangle$ :

$\mathcal S$ : states; $\mathcal A$ : actions;
$P^{a}_{ss'}=P(S_{t+1}=s'\mid S_t=s,A_t=a)$ : transition probabilities, now depending on the action;
$R^{a}_{s}=\mathbb E[R_{t+1}\mid S_t=s,A_t=a]$ : expected reward for taking $a$ in $s$ ;
$\gamma$ : discount factor.

The Markov property still holds: the next state and reward depend only on the current state and action. An MDP is a common model for RL when the chosen state captures the relevant information; partially observed problems require additional treatment.

In s₁ the agent chooses “stay” or “go” (black dots). The environment then decides the outcome: “go” reaches s₂ with probability 0.8 (reward +5) or falls back to s₁ with 0.2 (reward 0).

Policy

A policy $\pi$ is a distribution over actions given states:

\pi(a\mid s)=P(A_t=a\mid S_t=s)

Deterministic policy: one fixed action per state, $a=\pi(s)$ .
Stochastic policy: probabilities, e.g. $\pi(\text{stay}\mid s_1)=0.5,\;\pi(\text{go}\mid s_1)=0.5$ .

The policies used in these examples are stationary Markov policies. The term policy more generally also permits time-dependent or history-dependent decision rules.

Value functions

State-value function: expected return from state $s$ when following $\pi$ :

v_\pi(s)=\mathbb E_\pi[G_t\mid S_t=s]

Action-value function (Q-function): expected return when taking action $a$ in $s$ and following $\pi$ afterwards:

q_\pi(s,a)=\mathbb E_\pi[G_t\mid S_t=s,A_t=a]

They are linked by averaging over the policy's choices:

v_\pi(s)=\sum_{a\in\mathcal A}\pi(a\mid s)\,q_\pi(s,a)

Optimal value functions take the best policy: $v_*(s)=\max_\pi v_\pi(s)$ and $q_*(s,a)=\max_\pi q_\pi(s,a)$ . An optimal policy acts greedily on $q_*$ : $\pi_*(s)=\arg\max_a q_*(s,a)$ .

	Markov process	MRP	MDP
Tuple	$\langle\mathcal S,P\rangle$	$\langle\mathcal S,P,R,\gamma\rangle$	$\langle\mathcal S,\mathcal A,P,R,\gamma\rangle$
Rewards	No	Yes	Yes
Decisions	No	No	Yes (actions)
Value	—	$v(s)$	$v_\pi(s),\;q_\pi(s,a)$

Yaad rakho: MP → +reward = MRP → +action = MDP. v = “state kitni achhi”, q = “is state mein yeh action kitna achha”.