Markov Decision Processes and Optimal Control

Table of Contents

• Introduction

• Requirements

  • Modules
• Markov Decision Processes
• Summary and Outlook
• Literature
• Licenses

Introduction

Goal of this notebook is to introduce Markov Decision Processes (MDPs) and how to solve them by dynamic programming. MDPs model the interaction between an agent and the environment.

In the full reinforcement learning problem the environment-agent model is unknown. However, an understanding of MDPs is fundamental for reinforcement learning.

Requirements

Python Modules

With the deep.TEACHING convention, all python modules needed to run the notebook are loaded centrally at the beginning.

Markov Decision Processes

Markov decision processes (MDP) are a model of the agent-enviroment interaction.

In this notebook key elements of MDPs are introduced.

Definition

A countable MDP is defined as a triple$ \mathcal M = (\mathcal{S, A, P_{0}}) $ with

• A countable not-empty set of states$ s \in \mathcal S $.
• Countable not-empty set of actions$ a \in \mathcal A $.
• Transition probability kernel$ \mathcal P_0 $:$ \mathcal P_0 $ describes the (stochastic) reaction of the enviroment to the agents action. For each state-action pair$ (S=s, A=a) \in \mathcal S \times \mathcal A $ there is a probability distribution over$ \mathcal S \times \mathbb R $:$ P_0(\cdot \mid s, a) $ with the following semantics: For$ U \in \mathcal S \times \mathbb R $ is$ P_0(U \mid s, a) $ the probability that the next states and the reward$ R $ belongs to the set$ U $ given that the current state is$ s $ and the action taken is$ a $.

MDPs are models of the interaction between the enviroment and the agent.

Agent and Environment

An agent takes an action in the given environment with the goal to maximize the long-term received reward (cumulative reward). This principle can be seen in figure 1 as an infinite loop.

At timestep$ t $ the agent receives a state$ S_{t}=s $ (for example a camera image) and performs an action$ A_{t}=a $. In the next timestep$ t+1 $, a reward$ R_{t+1}=r $ and the resulting new state$ S_{t+1}=s' $ from the taken action$ A_{t}=a $ of timestep$ t $, is given to the agent. Notice, that the state and reward which are received in$ t+1 $ are a result of an action taken at timestep$ t $, so the reward is not instantaneous but delayed.

If the random variable$ S_t $ takes value$ s $ we use the abbreviation$ s_t $.

The MDP and agent together give rise to a sequence called trajectory that begins like this:

Reward Function

From the definition we also have a reward function$ \mathcal R(s,a) $ which is the expected reward for taking action$ a $ in state$ s $:

$ \mathcal R(s,a) = \mathbb E [R \mid S = s, A =a]=\int_{\mathbb R} \sum_{\mathcal s' \in S} r \cdot P_0(s',r \mid s,a) dr $

We will explicit represent the function as matrix, so we will use the notation$ \mathcal R_s^a $.

Analog we also have a function (of three variables) if the next state$ S_{t+1}=s' $ at time$ t+1 $ is also given:

$ \mathcal R(s, a, s') = \mathcal R_{s,s'}^a =\mathbb E [R_{t+1} \mid S_t = s, A_t =a, S_{t+1}=s'] = \int_{\mathbb R} r \cdot P_0(s', r \mid s,a) dr $

Markov Property

A state$ S_t=s $ includes all information about the past to predict future states. Additional information about the past such as previous states and actions doesn't give more information about future states.

In other word the states are Markovian, i.e.:

$ \mathbb P[S_{t+1}, R_{t+1} \mid S_t, A_t] = \mathbb P[S_{t+1}, R_{t+1} \mid S_1, A_1 \dots , S_{t-1}, A_{t-1}, S_{t}, A_{t}] $

State transition probability kernel

From$ \mathcal P_0 $ we can derive the state transition probability kernel$ \mathcal P $ which for any$ (s, a, s') \in \mathcal S \times \mathcal A \times \mathcal S $ triple gives the probability of moving from state$ s $ to some other state$ s' $ provided that action$ a $ was chosen in$ s $:

$ P(s,a,s') = P_0(\{s'\} \times \mathbb R \mid a, s) $

Example: Jacks Car Rental

(from [SUT98])

"Jack manages two locations for a nationwide car rental company. Each day, some number of customers arrive at each location to rent cars. If Jack has a car available, he rents it out and is credited$ \ $1$ by the national company. If he is out of cars at that location, then the business is lost. Cars become available for renting the day after they are returned. To help ensure that cars are available where they are needed, Jack can move them between the two locations overnight, at a cost of SINGLE``SINGLE 2 $ per car moved. We assume that the number of cars requested and returned at each location are Poisson random variables with mean$ \lambda $. Suppose$ \lambda $ is 3 and 4 for rental requests at the first and second locations and 3 and 2 for returns. To simplify the problem slightly, we assume that there can be no more than 20 cars at each location (any additional cars are returned to the nationwide company, and thus disappear from the problem) and a maximum of five cars can be moved from one location to the other in one night. We take the discount rate to be and formulate this as a continuing finite MDP, where the time steps are days, the state is the number of cars at each location at the end of the day, and the actions are the net numbers of cars moved between the two locations overnight."

• if more cars should be moved from a location as available, then it will charged the full action but only the available cars are moved.
• cars can be rent and returned at each location at all nationwide locations.

• We call the first location A and the second location B

We want to answer the following question:

• What is the optimal transfer policy of cars between branches?

States

Question:

• What are the valid states of the Jacks car rental enviroment?

Answer:

• Number of cars in each location ready for rent (e.g. the tuple (3,5) means 3 cars in location A and 5 cars in location B).

Probability to be in a state

The probability for the states can be represented as a vector. For Jacks Car Rental:

$ p(\vec s) = \begin{pmatrix} p(S=s_0) \\ p(S=s_1) \\ p(S=s_2) \\ \dots \\ p(S=s_{21}) \\ p(S=s_{22}) \\ \dots \\ p(S=s_{440}) \end{pmatrix} \begin{matrix}(0,0) \\ (0,1) \\ (0,2)\\ \dots \\ (1,0) \\ (1,1) \\ \dots \\ (20,20) \end{matrix} $

For the Jacks Car Rental problem it's sometimes easier to work with a state probability matrix:

$ P(\hat S) = \begin{pmatrix} P(S=s_{0}) & P(S=s_{1})& \dots & P(S=s_{20}) \\ P(S=s_{21}) & P(S=s_{22}) & \dots & P(S=s_{41})\\ \vdots & \vdots & \ddots & \vdots\\ . & . & \dots & p(S=s_{440}) \end{pmatrix} $

The indices of$ P(\hat S) $ correspond directly to the probability of the number of cars at each location.
Note that we can use np.reshape to switch between the different representations.

We define a function to get the most probable location of a given state:

We define a function to get the state vector for given$ a $ and$ b $, where$ a $ is the amount of cars at$ A $ and$ b $ is the amount of cars at$ B $.

Actions

Actions are the nightly movements of the cars. We encode them as a number between -5 to 5, e.g.

• Action +3: move three cars from A to B.
• Action -1: move one car from B to A.

State transition probability kernel for Jacks Car Rental

Definition $ \vec s' = P \vec s $

with

$ \vec s $: probabilities for the states at time$ t $ $ \vec s' $: probabilities for the states at time$ t+1 $ *$ P = \mathcal P $: State Transition Probability Kernel

In the following we construct the (transpose of the) state transition probability kernel. First note that the kernel decomposes as

$ P = P_{ret} P_{req} P_{move} $

with

$ P_{move} $: The kernel for the nightly moves according to the actions. $ P_{req} $: The kernel for the requests of cars. *$ P_{ret} $: The kernel for the returns of cars.

Note: for$ P_{req} $ and$ P_{ret} $ we don't have actions.

Form of the Transition Matrix:

• for earch old state we have a column
• for each new states we have a row

Note:
Here we have 441 possible states (for the old and new ones). So the transition matrix has dimension (441, 441). Each column of the transition matrix describes how a states is transformed.

Request State Transition Probability Kernel

We define a function that calculates the transitions for one given location. Therefore, the Poisson probability mass function (PMF) is used. For further information about Poisson distribution in general, see e.g. here.

If we have e.g. eight cars at location A, after the renting the requested cars we get the following distribution:

Note that the defined matrix has shape 21x21. So the index considers only the location A. A full state is given by the pair "(location A, location B)". So we must extend the matrix to a "full" transition matrix 441x441.

We define a function to retrieve the "full" transition matrix A for a given location.

We define a function to retrieve the full transition matrix B for a given location. Note, that the positions of equal B locations in the full state vector a different a for location A.

Full state vector: $ \begin{bmatrix}(0,0) \\ (0,1) \\ (0,2)\\ \dots \\ (1,0) \\ (1,1) \\ \dots \\ (20,20) \end{bmatrix} $

e.g.

• indices for location A=0:$ 0,1, \dots, 20 $
• indices for location B=0:$ 0,21,42, \dots, 420 $

Return State Transition Probability Kernel

Similar to the requests, we define the return state transition probability kernel.

The combinations of requests and returns is given by the dot product:

$ P_{ret/req} = P_{ret} P_{req} $

Nightly Moves State Transition Probability Kernel

We implement$ P_{move} $ as a 3d numpy array with indices [to_state_index, from_state_index, action_index].

Note:
actions and indices for actions differ, e.g. action 2 has index 2+5.

Construct the full transition probability kernel (request, returns and nightly shifts):

$ P $ is the full state transition probability kernel for the Jack's car rental problem. $ P $ has the following indices:$ (s', s, a) $

Reward Function

Let's construct the expected reward aka reward function

$ \mathcal R(s,a) = \mathcal R_s^a = \mathbb E[R \mid s, a] $

Policy

A policy$ \pi $ is the behaviour of an agent. It maps states$ s $ to actions$ a $:

• Deterministic Policies:$ a = \pi(s) $
• Stochastic Policies:$ \pi(a\mid s) = P(a\mid s) $

Markov Reward Process

A stationary policy$ \pi $ and a MDP induce a MRP. Choose always the action$ a $ according to the policy$ \pi $.

A Markov Reward Process (MRP) is a tuple$ \langle \mathcal{S}, \mathcal P_0'\rangle $ with

$ \mathcal S $: finite set of states$ s $ $ \mathcal P'_0 $: state transition Kernel matrix:$ \mathcal P'_0 $ assigns to each state$ (S=s) \in \mathcal S $ a probability measure over$ \mathcal S \times \mathbb R $:$ P'_0(\cdot \mid s) $ with the following semantics: For$ U \in \mathcal S \times \mathbb R $ is$ P'_0(U \mid s) $ the probability that the next states and the reward$ R $ belongs to the set$ U $ given that the current state is$ s $.

This implies again a reward function$ \mathcal R^\pi(s) $ resp.$ \mathcal R^\pi_s $ as for the MDP.

State Transition Probability Matrix for the MRP

$ \mathcal P_{ss'}^\pi = \mathbb P [S_{t+1} = s' \mid S_t = s , a = \pi(s)] $

$ \mathcal P^\pi = \begin{pmatrix} \mathcal P_{11} & \dots & \mathcal P_{1n} \\ \vdots & & \\ \mathcal P_{n1} & \dots & \mathcal P_{nn} \end{pmatrix} $

Note that the indicies of the matrix are$ ss' $ in contrast to the above constructed state transition kernel which has the indicies$ s'sa $.

Given a MDP$ \langle \mathcal{S, A, \mathcal P_o} \rangle $ and a policy$ \pi $:

• The state sequence$ s_1, s_2, \dots $ is a Markov process
• The state and reward sequence$ s_1, r_2, s_2, \dots $ is a Markov Reward Process where $ \mathcal P^\pi_{s,s'} = \sum_{a\in \mathcal A} \pi(a \mid s) \mathcal P^a_{s,s'} $ $ \mathcal R^\pi_{s} = \sum_{a\in \mathcal A} \pi(a \mid s) \mathcal R^a_{s} $

Total Discounted Reward

The return$ G_t $ is defined as the total discounted reward:

$ G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots = \sum_{k=0}^\infty \gamma^k R_{t+k+1} $

Sum of discounted rewards is finite

Note that with all rewards$ R_t>0 $

$ \sum_{t=0}^\infty R_t = \infty $

Independent of the actual values of$ R_t $. So we can't compare the (expected) reward of different states respectivly policies (which cases the state sequence).

But $ \sum_{t=0}^\infty \gamma^t R_t $

with the discount$ \gamma $ $ 0<\gamma<1 $

has as result a finite number, because with the maximum reward$ R_{max} = \max_t (R_t) $ in the serie it is bounded by

$ \sum_{t=0}^\infty \gamma^t R_t \leq \sum_{t=0}^\infty \gamma^t R_{max} = \frac{R_{max}}{1-\gamma} $

Proof of$ \sum_i \gamma^i = 1/(1-\gamma) $

$ x = \gamma^0 +\gamma^1 + \gamma^2 + \dots $

$ \gamma^0 +\gamma^1 + \gamma^2 + \dots = \gamma^0 + \gamma (\gamma^0 +\gamma^1 + \gamma^2 + \dots) $

$ x = \gamma^0 + \gamma x = 1 + \gamma x $

$ x(1-\gamma) = 1 $

$ x = \frac{1}{1-\gamma} $

Value functions

The state-value function$ v_\pi (s) $ of an MDP is the expected return starting from state$ s $, and then follow policy$ \pi $

$ v_\pi (s) = \mathbb E_\pi[G_t \mid S_t=s] = \mathbb E \left[ \sum_{t'=t}^\infty \gamma^{t'-t} R_{t'+1} \mid S_t=s \right], s \in \mathcal S $

The value function can be decomposed into an immediate part and the discounted value function of the successor states:

$ v_\pi(s) = \mathbb E[G_t \mid S_t =s] \\ = \mathbb E [R_{t+1}+γR_{t+2}+\gamma^2 R_{t+3} + \dots \mid S_t =s] \\ = \mathbb E [R_{t+1} + \gamma (R_{t+2}+\gamma R_{t+3} + \dots ) \mid S_t = s] \\ = \mathbb E [R_{t+1} + \gamma G_{t+1} \mid S_t = s] \\ = \mathbb E [ R_{t+1} \mid S_t = s]+ \gamma v_\pi(S_{t+1} ) $

so, we have the Bellmann Equation (for deterministic policies):

$ v_\pi(s) = \mathcal R_s^\pi + \gamma \sum_{s'\in \mathcal S} P_{ss'}^\pi v_\pi (s') $

Note:$ v(s') $ are the values of the successor states of$ s $, so in$ \sum_{s'\in \mathcal S} P_{ss'} v(s') $ the weights$ P_{ss'} $ of the values$ v(s') $ are the transitions back in time.

Bellman Equation

also for non deterministic policies:

$ v_\pi(s) = \sum_a \pi(a \mid s) \left( \mathcal R_s^a + \gamma \sum_{s' \in \mathcal S} \mathcal P^a_{s,s'} v_\pi(s')\right) $

Bellmann equations in vector-matrix form:

$ \vec v = \mathcal R^{\pi} + \gamma P^{\pi} \vec v $

Here, we can directly solve the Bellmann equation:

$ \vec v = (I - \gamma \mathcal P^\pi)^{-1} \mathcal R^\pi $

For large state spaces computing the inverse is costly in terms of space and time. However, the bellman equation can be solved by an iteration:

Policy Evaluation

Computing the state-value function$ v^\pi(s) $ for an arbitrary policy by an iterative application of Bellman expectation backup is called policy evaluation:

*$ v_1 \rightarrow v_2 \rightarrow v_3 \rightarrow \dots \rightarrow v_\pi $

• loop until convergence (using synchronous backups)

  • at each iteration$ k+1 $
  • for all states$ s \in \mathcal S $
  • update$ v_{k+1}(s) $ from$ v_k(s') $, where$ s' $ is a successor state of$ s $

$ \vec v_{k+1} = \vec {\mathcal R}^\pi + \gamma {\mathcal P}^\pi \vec v_{k} $

Optimal Value Function

$ v^* (s) = \max_\pi v_\pi(s) $

The optimal value$ v^*(s) $ of state$ s \in \mathcal S $ is defined as the highest achievable expected return when the process is started from state$ s $. The function$ v^* : \mathcal S \rightarrow \mathbb R $ is called the optimal value function.

Policy Iteration

• Starting with an arbitrary policy

• Iteration until the values converge (to the optimal policy). Alternating sequence of

  • Policy Evaluation : Compute the values of the policy
  • Greedy Policy Improvement: Use the "best" action in each state, i.e. chose the action which result in the highest return for each state.

"Policy iteration often converges in surprisingly few iterations." [SUT98]

Greedy Policy Improvement

For greedy policy improvement we need the model (transition probabilities) if we are using the value function$ v(s) $: For each action$ a $ we compute the probabilities of the next states and calculate the average value of the discounted return.

If we start from state$ s $ with action$ a $, and then follow policy$ \pi $ we get as expected return

$ q_\pi (s,a) = \mathbb E \left[ R\mid s,a \right]+ \mathbb E \left[ \gamma \sum_{s'\in \mathcal S} P_{ss'}^\pi v_\pi (s') \right] $ $ q_\pi (s,a) $ is called the action-value function$ q_\pi (s,a) $.

Here, we compute$ q $ explicitly for each state$ s $ and action$ a $ (respectivly in matrix form). For each state we chose the action that results in the highest value.

To understand why Greedy Policy Improvement works read the section of Sutton's book about the policy improvement.

Q-Function

The action-value function$ q_\pi (s,a) $ of an MDP is the expected return starting from state$ s $ with action$ a $, and then follow policy$ \pi $

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

Optimal action-value function

$ q^* (s, a) = \max_\pi q^\pi(s, a) $

The optimal action-value$ q^*(s, a) $ of state-action pair$ (s,a) \in \mathcal S \times \mathcal A $ gives the highest achievable expected return when the process is started from state$ s $, and the first action chosen is$ a $. The function$ q^* : \mathcal S \times \mathcal A \rightarrow \mathbb R $ is called the optimal action-value function.

Connection between optimal value- and action-value function

$ v^*(s) = \max_{a \in \mathcal A} q^*(s,a), s \in \mathcal S $

$ q^*(s,a) = \mathcal R_s^a + \gamma\sum_{s' \in \mathcal S} P(s,a,s')v^*(s') ; s \in \mathcal S, a \in \mathcal A $

Bellman Equation for Q

$ q_\pi(s, a) = \mathcal R_s^a + \gamma \sum_{s' \in \mathcal S} \mathcal P^a_{s,s'} \left( \sum_{a'\in \mathcal A} \pi(a' \mid s') q_\pi(s',a') \right) $

for a deterministic policy:

$ q_\pi(s, a) = \mathcal R_s^a + \gamma \sum_{s' \in \mathcal S} \mathcal P^a_{s,s'} q_\pi(s',\pi(s')) $

$ \hat Q^\pi = \hat R + \gamma \mathcal P \vec Q^\pi_\pi $

with

*$ \vec \pi $: Policy vector

• Matricies$ \hat Q^\pi, \hat R $ with entries$ \cdot_{sa} $
• 3d Array$ \mathcal P $ with entries$ \cdot_{sas'} $ *$ \vec Q^\pi_\pi = \vec v^\pi $

Policy Evaluation for Q

Computing the state-action-value function$ q^\pi(s, a) $ for an arbitrary policy by an iterative application of Bellman expectation backup is also called policy evaluation:

*$ q_1 \rightarrow q_2 \rightarrow q_3 \rightarrow \dots \rightarrow q_\pi $

• using synchronous backups

  • at each iteration$ k+1 $
  • for all states$ s \in \mathcal S $ and$ a \in \mathcal A $
  • update$ q_{k+1}(s, a) $ from$ q_k(s', \cdot) $, where$ s' $ is a successor state of$ s $.

$ \hat Q^{k+1} = \hat R + \gamma \mathcal P \vec Q^k_{k} $

Policy Iteration for Q

• Starting with an arbitrary policy

• Iteration until the values converge (to the optimal policy). Alternating sequence of

  • Policy Evaluation : Compute the values of the policy

  • Greedy Policy Improvement: *$ \pi'(s) = \text{arg} \max_{a \in \mathcal A} q^\pi(s,a) $

    • Note: Here we don't use the (transition) model.

Bellman Optimality Equation

$ v^*(s) = \max_a \mathbb E \left[ R_{t+1} + \gamma v^*(S_{t+1}) \mid S_t = s, A_t = a\right] \\ = \max_a \left(\mathcal R^a_{s} + \gamma \sum_{s'} P_{ss'}^a \mathcal v^*(S_{t+1}=s')\right) $

$ q^*(s, a) = \mathbb E \left[ R_{t+1} + \gamma \max_{a'} q^*(S_{t+1},A_{t+1}=a') \mid S_t = s, A_t = a\right] \\ = \mathcal R^a_{s} + \gamma \sum_{s'} P_{ss'}^a \mathcal \max_{a'} q^*(S_{t+1}=s',A_{t+1}=a') $

Value Iteration

From the Bellmann optimality equation we can derive an iterative method to find the optimal value function:

$ v_{k+1}(S_t = s) = \max_a \mathbb E[R_{t+1} + \gamma v_k(S_{t+1}=s') \mid S_t=s, A_t=a] \\ = \max_a \left( \mathcal R_{s}^a + \gamma \sum_{s'} \mathcal P_{ss'}^a v_k(s')\right) $

Summary and Outlook

Here we introduced MDPs as a model of the agent-environment interaction. We showed how to construct an explicit transition model on an example of R. Suttons Book "Introduction to Reinforcement Learning".

We also showed how to solve the corresponding optimization problem by dynamic programming.

In the next section no explicit transition kernel will be given. However, the interaction of the environment and the agent is also defined by a MDP. However, without the explicit transition kernel only tranjectories (as data) from the interaction are known. Such problems can not be solved by dynamic programming. Here, techniques from reinforcement learning are needed.

Literature

Licenses

Notebook License (CC-BY-SA 4.0)

The following license applies to the complete notebook, including code cells. It does however not apply to any referenced external media (e.g., images).

Introduction to Reinforcement Learning
by Christian Herta, Patrick Baumann is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Based on a work at https://gitlab.com/deep.TEACHING.

Code License (MIT)

The following license only applies to code cells of the notebook.

Copyright 2018 Christian Herta, Patrick Baumann

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.