Markov Decision Process (MDP) in Reinforcement Learning

Motivation and Framing

Let's consider a real world scenario where a robot is instructed to move forward in a room with two doors, one door is an exit and another door is a fire pit. The robot has to find a path and navigate to the exit. The robot might go to the wrong exit. In short, unlike other algorithms, where the robot knows exactly where it will land if it takes a certain step, the algorithm MDP(Markov Decision Processes) are the framework for the decision making process where the outcome of the game, search, etc are uncertain but the probability of next state is known.

A prime example of this problem is Grid world: an AI agent walking through a grid, trying to reach the reward grid. In this kind of problem the movement of the agent might not always go right as commanded i.e. telling the agent to move North makes the agent go North 80% of the time, but 10% times it goes East and 10% times it goes West. This happens because of random behavior mimicking the real world.

Formal Definition

In MDP, there are following variables that we need to understand first:

• S: States - A set of all the situation where the agent can be
• A: Action - All set of actions that an agent can do
• T(s, a, s’) or P(s' | s, a) - P: Transition Probability Function : probability of ending in a state s’, when an agent takes action “a” from state “s”
• R(s, a, s’) - Reward Function : Reward for taking an action from s to s’
• γ - Discount factor: A number in [0,1] controlling how much future reward is worth today
• s₀- Start state
• Terminal/absorbing states: states where the game ends (like eating the dot in your Pacman example once completed, no more actions are taken).

Formally, an MDP is defined as a 5-tuple: \((S, A, P, R, γ)
Note: In RL, the agent has to learn T and R on its own through its own experience.

Policies

A policy π is a function that defines the action an agent has to take when it is in a state s. It is not the same as a plan where the plan is like a sequence of actions like North, East, West etc and it does not look at where we currently are. If we end up somewhere unexpected, plan can’t adapt to it. In contrast, policy is derived from each state, so it gives action to the next step considering the current state instead of blindly giving direction.

Utilities of Sequence

Taking each step and moving from a state s to s’, the agent is provided with certain rewards(positive and negative). The agent should be rewarded for the entire sequence of action, not just a single one. So, Discounting introduces a weighing scheme which controls the reward. It defines the value of reward to the agent immediately vs in the future. This is controlled by γ (gamma). Where 0 <= γ < = 1). 0 means immediate reward only and future rewards are not considered whereas 1 means all the actions get equal rewards. It is given by:

U([r0,r1,r2 ,…]) = r0+ γ .r1 + γ2 . r2 + γ3. r3…….

Finite vs Infinite horizon

When the game has no ending and has no stop condition, the game could go on forever like the “Overheating Car” problem. So adding a gamma weight factor, shrinks the weight on each reward. When γ = 1, the reward is never decayed and never converges which makes it impossible to compare two policies. So keeping the value γ < 1, keeps the sum finite and makes the sum convergent.

The value function

The value function which is denoted by V*(s) is the total expected utility starting from a state s and acting optimally in each move. In simple words it says, “starting from this state, if i only move perfectly, how much reward i get to collect in total?”. It simply says how good is it to be in a particular state. There is another function which is Vk (The value of V if there are only K time step left). The game is cut off after K moves in this case.

Q-value function

Q*(s,a) which is referred to as Q-value function is the total expected utility starting at a state s after taking an action a and acting optimally afterwards. The difference between Value function and Q-value function is that V*(s) gives the value at a particular state where as Q*(s, a) gives the value of state s after taking an action a and acting optimally afterwards. These two are interrelated by the following relation:

V∗ (s)= max​a Q∗(s,a)

It tells us that the value of a state is the best value provided by possible actions from a state. This term Q-value is an important thing in Reinforcement Learning because in the case where we do not know T and R, the agent can quickly refer to Q-value to know which is the best step to take.

Bellman Equation

The bellman equation is the core of this topic. It is given by the following relation

V∗(s)=max​a(s′) ∑s′ ​T(s,a,s′)[R(s,a,s′)+γV∗(s′)]

Let’s break this down into piece by piece and read it:

T(s,a,s′)[R(s,a,s′)+γV∗(s′)]: The value of s is given by there is a reward we get immediately plus the discounted value of the future state(γV∗(s′) from that state.
max​a(s′) ∑s′ : out of all the possible outcomes whose value are averaged, pick the best one with highest expected value).

Therefore, the corresponding Q*(s,a) value is given by:

Q* (s,a)= ∑s′​T(s,a,s′)[R(s,a,s′)+γmax​ a′ Q*(s′,a′)]

(Note: This is an Iterative formula because every unknown value depends on other unknown values. So, for the calculation, we need value iterative algorithm like value iteration to calculate each steps)

Value Iteration

It is an iterative algorithm that solves the Bellman equation by turning it into a static equation and calculating the value for a step using a future step. It is given by:

Vk+1​(s)←max​a​(s′)∑​T(s,a,s′)[R(s,a,s′)+γVk​(s′)]

Steps:

1. Initialize V0(s) = 0 for all states.
2. Repeatedly compute V k+1 from V k using the formula above for each state.
3. Stop when the values stop to change or very small change happens in each step.
4. Once the values are converged V* is reached.

The cost per iteration is O(S2A) for every state S, with action A and for each action, the resulting state is added (up to S of them).

Policy Extraction

π∗(s) = argmax​a (s′) ∑​T(s,a,s′)[R(s,a,s′)+γV*(s′)]

After the calculation of V*, we get a vector of all the values from value iteration, the step called policy extraction needs to be done because V* only tells us how good the resulting step is, not which action to take. Since the Value iteration V* does not remember what action, from which state, produced the value. But replacing the V*(s) with Q*(s,a) it remembers which action produced the optimal result. So, policy extraction performs the comparison one more time, for each state, look at the possible action, compute what action yields the best reward and take the argmax(not the value itself).

Question: Why V* forgets and Q* remember?

Answer: Say state B has three possible actions, and we've already computed how good each one is:

East -> 0.5

South -> 0.5

West -> 0

Max looks at the maximum value out of three and returns 0.5. Whereas arg max returns South or East. Same input, same comparison, different output value. So, Since V* only stores the value as 0.5, after each calculation, we need to compute and rebuild the table from scratch if we need to know which action produced that particular result. But Q* resolves this by storing the whole table as Q*(B, East) = 0.5 and so on. Each value is stored as one per action. So looking at the technical side, when it is calculated, looking at 0.5 only as a value doesn’t tell anything about what action it came from but Q*(B, south) = 0.5 is informative. This is the reason policy extraction needs an extra lookahead step for V.

Policy Iteration

Unlike value iteration which repeatedly keeps on updating the value function by choosing an action that appears best currently, Policy Iteration starts with a fixed policy, evaluates how good that policy is, and then updates the policy by choosing better actions based on those values. There are two distinct phases:

1. Policy Evaluation
2. Policy Improvement

Policy Evaluation

Vπ k+1(s)=∑​s′ T(s,π(s),s′)[R(s,π(s),s′)+γVπ k(s′)]

(We do not have max here because the action is already set by the policy and no multiple actions from a particular state is obtained to choose the best one)
Policy Improvement

Now with a value Vπ(s), we have to calculate a policy which is even better than the previous one. The formula is given by:

ΠK + 1(s) = argmaxa ∑​s′ T(s,a,s′)[R(s,a,s′)+γVπ k(s′)]

Policy vs Value Iteration

Title	Value Iteration	Policy Iteration
What's tracked	V_k(s), updated every sweep	A full policy π, updated every outer loop
Inner step	One Bellman max update per state	Full policy evaluation (possibly solving a linear system or many sweeps)
Outer iterations needed	Often many (until value convergence)	Usually few (until policy stops changing)
Cost per outer iteration	Cheap (one update per state)	Expensive (a full evaluation phase)
Guaranteed to find π*?	Yes, in the limit	Yes, in finitely many iterations

Examples

MDP Numerical Examples