Let’s start by giving a formal definition of MDPs:
A Markov Decision Process is a 5-tuple (S, A, R, P, γ) such that:
- S is the set of states the agent can be in
- A is the set of actions the agent can take
- R : S x A → R the reward function
- P is the set of probability distributions defined such that P(s’|s,a) is the probability of transitioning to state s’ if the agent takes action a in state s. Note that MDPs are Markov processes, meaning that the Markov property holds on the transition probabilities: P(Sₜ₊₁|S₀, A₀, …, Sₜ, Aₜ) = P(Sₜ₊₁|Sₜ, Aₜ)
- γ ∈ (0, 1] is a discount factor. While we usually deal with discounted problems (i.e. γ < 1), the formulations presented are also valid for undiscounted MDPs (γ = 1)
We then define the policy, i.e. what dictates the agent’s behavior in an MDP:
A policy π is a probability measure over the action space defined as: π(a|s) is the probability of taking action a when the agent is in state s.
We finally introduce the value function, i.e. the agent’s objective in an MDP:
The value function of a policy π is the expected discounted reward under this policy, when starting at a given state s:
In particular, the value function of the optimal policy π* satisfies the Bellman optimality equation:
Which yields the deterministic optimal policy:
Deriving the LP formulation of MDPs:
Given the above definitions, we can start by noticing that any value function V that satisfies
is an upper bound on the optimal value function. To see it, we can start by noticing that such value function also satisfies:
We recognize the value iteration operator applied to V:
i.e.
Also noticing that the H*operator is increasing, we can apply it iteratively to have:
where we used the property of V* being the fixed point of H*.
Therefore, finding V* comes down to finding the tightest upper bound V that obeys the above equation, which yields the following formulation:
Here we added a weight term corresponding to the probability of starting in state s. We can see that the above problem is linear in V and can be rewritten as follows: