.. role:: python(code) :language: python .. index:: Markov Decision Process; state Markov Decision Process; action Markov Decision Process; reward Markov Decision Process; transition Markov Decision Process; policy Markov Decision Process; discount Markov Decision Process; value Markov Decision Process; quality Markov Decision Process; policy evaluation Markov Decision Process; value iteration Markov Decision Process; optimum policy state action reward transition policy discount value quality policy evaluation value iteration optimum policy .. `MDP graph (game) ` `MDP types/structures ` `Expectation ` `MDP value (game) ` `MDP policy evaluation (game) ` `MDP value iteration (game) ` .. _`sec:mdp`: Markov Decision Process ----------------------- Definitions ^^^^^^^^^^^ A Markov Decision Process (MDP) is a mathematical framework used to model decision-making in environments where outcomes are partially random and partially under the control of a decision-maker. It serves as the formal foundation for Reinforcement Learning (RL), providing a structured way to describe how an agent interacts with a system over time to achieve a specific goal. To define an MDP, you typically use four primary elements: + **States** (:math:`S`): A set of all possible configurations or situations the system can be in (for example, the position and velocity of a mechanical arm). + **Actions** (:math:`A`): The choices available to the decision-maker in each state (for example, applying a specific amount of torque). An action :math:`a` may lead to a change of state from :math:`s` to :math:`s'`. + **Rewards** (:math:`R`): The immediate feedback :math:`r` received after an action, used to signal whether an action was beneficial. The simplified case is when the reward is deterministic :math:`R(s'|s, a)` (fixed for a transition between the current state :math:`s` and the next state :math:`s'`). However, sometimes the reward is stochastic (it fluctuates randomly following a distribution associated to the transition to the next state :math:`s'` from the current state :math:`s` when the action :math:`a` is taken). + **Transition** Probability (:math:`T`): The simplified definition is the probability that taking action :math:`a` in state :math:`s` will result in moving to state :math:`s'`. To be more explicit, this transition can be noted :math:`T(s'|s, a)` as the probability to reach :math:`s'` knowing :math:`s` and :math:`a`. However, in the case of stochastic rewards, one uses the joint probability :math:`T(s', r|s, a)` as the probability to reach :math:`s'` and collecting :math:`r` knowing :math:`s` and :math:`a`: :math:`\sum_{s', r} T(s', r|s, a) = 1`. A MDP is typically represented as a graph with two types of nodes: state nodes and chance|action nodes as illustrated on the :ref:`Figure ` below. From a state node (blue ellipses), one or several actions are possible, taking an action (red arrow) moves you to the chance node (gray diamond). From the chance node, you randomly end up on a state node following the transition probability and collecting the reward. A reward can be seen as the opposite of a cost. A special state is the end state :math:`s_{\textrm{end}}` from which no action can be performed and the process stops. For a deterministic agent behavior, a **policy** :math:`\pi(s)` defines the action :math:`a` the agent will take for every state :math:`s`. However, the agent may behave stochastically. In this case, the policy defines for every state :math:`s` the probability to take an action :math:`a` and would be noted :math:`\pi(a | s)`. For example, the agent may choose its actions completely randomly: at every state it picks randomly an action in the set of available actions. The **value** :math:`V_\pi(s)` of a policy is the expected discounted sum of rewards collected following this policy :math:`\pi` from state :math:`s` until an end state is reached. Usually, the goal is to find an **optimum** policy: a policy with the maximum value. Since an immediate reward is sometimes preferred to a future reward, a **discount factor** :math:`\gamma` (between 0 and 1) is used to weight down future rewards. .. _`fig:mdp_structure`: .. figure:: mdp_structure.png :width: 200 :alt: mdp_structure MDP structure .. admonition:: Exercise (easy) This exercise is inspired from CS221 :cite:`stanford_online_CS221`. Imagine a game, you are either "in" or "out". In the later case, the game is ended. If you are "in", you can either "quit" or "stay". On one hand, if you choose to quit, you collect a reward of 10€ and the game is ended. On the other hand, you choose to stay, you role a die and you have a 2/3 probability to collect 4€ and be able to play again, and a 1/3 probability to be kicked out or the game and collect 5€. Draw the MDP graph of this game .. _`ex:mdp_game_graph`: .. collapse:: Correction .. figure:: game.png :width: 200 :alt: mdp_game MDP game A transition of 1 means that you are certain to quit if you decide to quit. .. admonition:: Exercise (easy) For deterministic rewards and agent: 1. What python structure would you use to communicate a MDP assuming that the states and actions are :python:`str`? Fill it with the values corresponding to the game of the previous exercise. 2. Same question for a policy? For stochastic rewards and agent: 3. Same as 1. 4. Same as 2. .. _`ex:mdp_python_structure`: .. collapse:: Correction 1. There is obviously not a unique answer: +------------------------+------------+--------------+-------------+--------------+ | State s | | | | | +========================+============+==============+=============+==============+ | | Action a | | | | +------------------------+------------+--------------+-------------+--------------+ | | | NextState s' | | | +------------------------+------------+--------------+-------------+--------------+ | | | |Transition T | Reward r | +------------------------+------------+--------------+-------------+--------------+ | | | NextState s''| | | +------------------------+------------+--------------+-------------+--------------+ | | | |Transition T'| Reward r' | +------------------------+------------+--------------+-------------+--------------+ | | Action a' | ... | | | +------------------------+------------+--------------+-------------+--------------+ For every state, potentially several actions are available. For each action, several next state are possible with a given transition / reward. .. code-block:: python :linenos: type State = str type Action = str type NextState = str type Reward = float type Transition = float type Outcomes = dict[NextState, tuple[Transition, Reward]] type MDPMapping = dict[State, dict[Action, Outcomes]] .. code-block:: python {'in': {'quit': {'out': (1.0, 10.0)}, 'stay': {'in': (2.0/3.0, 4.0), 'out': (1.0/3.0, 5.0)}}, 'out': {}} 2. +--------------+----------------+ | State s | Action a | +--------------+----------------+ | State s' | Action a' | +--------------+----------------+ A deterministic policy tells you the action to perform for every state. .. code-block:: python type PolicyMapping = dict[State, Action] 3. +------------------------+------------+--------------+---------------+--------------+ | State s | | | | | +========================+============+==============+===============+==============+ | | Action a | | | | +------------------------+------------+--------------+---------------+--------------+ | | | NextState s' | | | +------------------------+------------+--------------+---------------+--------------+ | | | |Transition T | Reward r | +------------------------+------------+--------------+---------------+--------------+ | | | |Transition T' | Reward r' | +------------------------+------------+--------------+---------------+--------------+ | | | NextState s''| | | +------------------------+------------+--------------+---------------+--------------+ | | | |Transition T'' | Reward r'' | +------------------------+------------+--------------+---------------+--------------+ | | | | ... | | +------------------------+------------+--------------+---------------+--------------+ Note that now, the rewards are stochastic. It means that you have different probabilities for different rewards for a given (state, action to next state) case. .. code-block:: python type Outcomes = dict[NextState, tuple[tuple[Transition, Reward], ...]] 4. +--------------+----------------+-----------------+ | State s | | | +--------------+----------------+-----------------+ | | Proba π | Action a | +--------------+----------------+-----------------+ | | Proba π' | Action a' | +--------------+----------------+-----------------+ | State s' | | | +--------------+----------------+-----------------+ | | Proba π'' | Action a'' | +--------------+----------------+-----------------+ Note that the policy is now stochastic. It means that for each state you have a distribution of potential actions. .. code-block:: python type ActionProbability = float type PolicyMapping = dict[State, tuple[tuple[ActionProbability, Action], ...] ] Policy value ^^^^^^^^^^^^ .. admonition:: Exercise (easy) Preliminary question, imagine you play with a die (6 faces). You have one throw. If you get 1 or 2, you win 1€; 3, you win 10€; 4, 5, 6, you win 4€. What is the expected gain? .. _`ex:preliminary_mdp_expected`: .. collapse:: Correction .. math:: 1\textrm{€} \cfrac{2}{6} + 10\textrm{€} \cfrac{1}{6} + 4\textrm{€} \cfrac{3}{6} = 4\textrm{€} From a given state :math:`s`, several states :math:`s'` are reachable following action :math:`a` from the policy :math:`\pi`. Each one has a transition :math:`T(s' | s, a)` and a reward :math:`R(s' | s, a)`. As a result, each next state :math:`s'` contributes :math:`T(s' | s, a) R(s' | s, a)` to the expected value :math:`V_\pi(s)` of state :math:`s` following :math:`\pi`. However, one must also account for the remaining value :math:`V_\pi(s')` of every next state :math:`s'`: :math:`\gamma T(s' | s, a) V_\pi(s')` (the :math:`\gamma` is discounting the value :math:`V_\pi(s')` because this value is one step in the future, and currents rewards are more valuable than future rewards). For a deterministic policy, the value of a state :math:`s` following a policy :math:`\pi` is: .. math:: :label: eq:mdp_policy_value V_\pi(s) = \sum_{s'} \left( R(s' | s, a) + \gamma V_\pi(s') \right) T(s' | s, a) V_\pi(s_{\textrm{end}}) = 0 It is useful for later to define the **quality** :math:`Q_\pi(s, a)` as the expected value from state :math:`s` after action :math:`a`: .. math:: :label: eq:mdp_quality Q_\pi(s, a) = \sum_{s'} \left( R(s' | s, a) + \gamma V_\pi(s') \right) T(s' | s, a) For a stochastic policy: .. math:: :label: eq:mdp_policy_value_stochastic V_\pi(s) = \sum_a \pi(a | s ) Q_\pi(s, a) .. admonition:: Exercise (intermediate) 1. For the :ref:`game ` of the first exercise, calculate by hand the value of the policy "always play" assuming a discount value of 1. 2. Calculate by hand the value of the random policy :math:`\pi`, and all the qualities. .. _`ex:mdp_value`: .. collapse:: Correction 1. Applying the equations above: .. math:: :label: eq:mdp_value_game V_\textrm{stay}(\textrm{in}) = \underbrace{\cfrac{1}{3} (5 + 0)}_{\textrm{next state: out}} + \underbrace{\cfrac{2}{3} \left( 4 + V_\textrm{stay}(\textrm{in}) \right)}_{\textrm{next state: in}} V_\textrm{stay}(\textrm{in}) \left( 1 - \cfrac{2}{3} \right) = \cfrac{13}{3} V_\textrm{stay}(\textrm{in}) = 13 Obviously, it is not always possible to solve directly the recursive equation of the value. Next sections will present a general algorithm to do so. 2. One must distinguish clearly the value of the random policy from the quality of the policy when a specific action has been taken from a state: .. math:: :label: eq:mdp_value_game_random V_\pi(\textrm{in}) = \cfrac{1}{2} \left( Q_\pi(\textrm{in}, \textrm{stay}) + Q_\pi(\textrm{in}, \textrm{quit}) \right) Q_\pi(\textrm{in}, \textrm{stay}) = \underbrace{\cfrac{1}{3} (5 + 0)}_{\textrm{next state: out}} + \underbrace{\cfrac{2}{3} \left( 4 + V_\textrm{stay}(\textrm{in}) \right)}_{\textrm{next state: in}} = \cfrac{13}{3} + \cfrac{2}{3} V_\pi(\textrm{in}) Q_\pi(\textrm{in}, \textrm{quit}) = 10 V_\pi(\textrm{in}) = \cfrac{1}{2} \left( \cfrac{13}{3} + \cfrac{2}{3} V_\pi(\textrm{in}) + 10 \right) = \cfrac{43}{4} Q_\pi(\textrm{in}, \textrm{stay}) = \cfrac{13}{3} + \cfrac{2}{3} \cfrac{43}{4} = \cfrac{23}{2} Optimum policy ^^^^^^^^^^^^^^ As mentioned, the next obvious step is to determine the optimum policy. The optimum policy is the mapping of actions per state which leads to the maximum expected value. For the type of MDP considered here, the optimum policy :math:`\pi_\textrm{opt}(s)` is deterministic: for every state there is one action which will lead to the maximum value. As a result, the stochastic policy notation is dropped. For notation convenience, deterministic rewards are considered. For every available action :math:`a` from state :math:`s`, the optimum policy consists in choosing the action leading to a maximum value: .. math:: :label: eq:mdp_optimum_policy V_\textrm{opt}(s) = \max_{a} \underbrace{\sum_{s'} \left( R(s'|s, a ) + \gamma V_\textrm{opt}(s') \right) T(s'|s, a)}_{Q_\textrm{opt}(s, a)} \pi_\textrm{opt}(s) = \textrm{arg}\max_{a} Q_\textrm{opt}(s, a) Algorithms ^^^^^^^^^^ .. hint:: Equations :eq:`eq:mdp_policy_value` and :eq:`eq:mdp_optimum_policy` have a form: :math:`x=F(x)` where the unknown :math:`x` is the value. You already encountered this type of equations and numerically solved it iteratively using the by initializing the unknown at step :math:`(0)`, and then improving until convergence the value of :math:`x^{((k+1))}` from :math:`x^{((k))}`: .. math:: :label: eq:mdp_substitution_algorithm \begin{cases} x^{(0)} = x_0 \\ x^{((k+1))} = F(x^k) \end{cases} Policy evaluation ~~~~~~~~~~~~~~~~~ An algorithm to solve Equation :eq:`eq:mdp_policy_value` for every state is called **policy evaluation**: .. _`algo:mdp_policy_evaluation`: .. code-block:: text :linenos: get all states initialize the value for all states to 0 until convergence for all states calculate the quality for the current state ... ... and the action from the policy using the current estimates of values for the next states update the value of the current state check convergence .. admonition:: Exercise (easy) 1. For the :ref:`game ` of the first exercise, use the previous algorithm by hand to evaluate the policy "always stay" assuming a discount value of 1. 2. Same question for the random policy. .. _`ex:mdp_policy_evaluation`: .. collapse:: Correction 1. For always play: .. math:: :label: eq:mdp_policy_evaluation V^{(0)}_\textrm{stay}(\textrm{in}) = 0 ; V^{(0)}_\textrm{stay}(\textrm{out}) = 0 V^{(1)}_\textrm{stay}(\textrm{in}) = \cfrac{1}{3} 5 + \cfrac{2}{3} (4+0) = \cfrac{13}{3} V^{(2)}_\textrm{stay}(\textrm{in}) = \cfrac{1}{3} 5 + \cfrac{2}{3} \left(4 + \cfrac{13}{3}\right) = \cfrac{65}{9} V^{(3)}_\textrm{stay}(\textrm{in}) = \cfrac{1}{3} 5 + \cfrac{2}{3} \left(4 +\cfrac{65}{9}\right) = ... which leads to the first ten values: +--------+-------+ | step | V | +========+=======+ | 0 | 0.00 | +--------+-------+ | 1 | 4.33 | +--------+-------+ | 2 | 7.22 | +--------+-------+ | 3 | 9.15 | +--------+-------+ | 4 | 10.43 | +--------+-------+ | 5 | 11.29 | +--------+-------+ | 6 | 11.86 | +--------+-------+ | 7 | 12.24 | +--------+-------+ | 8 | 12.49 | +--------+-------+ | 9 | 12.66 | +--------+-------+ and ultimately a convergence towards the exact value which is 13. 2. For random policy: .. math:: :label: eq:mdp_policy_evaluation_random V^{(k+1)}_\pi(\textrm{in}) = \cfrac{1}{2}\left( \underbrace{\cfrac{1}{3} 5 + \cfrac{2}{3} (4+V^{(k+1)}_\pi(\textrm{in}))}_{\textrm{action stay}} + \underbrace{10}_{\textrm{action quit}} \right) which converges towards 43/4. Value iteration ~~~~~~~~~~~~~~~ An algorithm to solve Equation :eq:`eq:mdp_optimum_policy` is called **value iteration**: .. _`algo:value_iteration`: .. code-block:: text :linenos: get all states initialize the value for all states to 0 until convergence for all states for all actions at the current state calculate the qualities for the current state ... ... and the current action using current estimates of values for the next states update the value of the current state with the maximum quality between actions update the policy for the current state with the action giving the maximum quality check convergence .. admonition:: Exercise (easy) For the :ref:`game ` of the first exercise, use the previous algorithm by hand to find the optimum policy assuming a discount value of 1. .. _`ex:mdp_value_iteration`: .. collapse:: Correction Careful, one uses the current value of the optimum policy, which can fluctuate during convergence: .. math:: \begin{cases} Q_\textrm{opt}^{(0)}(\textrm{in}, \textrm{stay}) = \cfrac{1}{3} 5 + \cfrac{2}{3} (4 + \mathbf{0}) = \cfrac{13}{3} \\ Q_\textrm{opt}^{(0)}(\textrm{in}, \textrm{quit}) = 10 \\ V_\textrm{opt}^{(0)}(\textrm{in}) = \max \left[ (\cfrac{13}{3}, \textrm{in}, \textrm{stay}); (10, \textrm{in}, \textrm{quit}) \right] = (10, \textrm{in}, \textrm{quit}) \\ \pi_\textrm{opt}^{(0)}(\textrm{in}) = \textrm{quit} \end{cases} .. math:: \begin{cases} Q_\textrm{opt}^{(1)}(\textrm{in}, \textrm{stay}) = \cfrac{1}{3} 5 + \cfrac{2}{3} (4 + \mathbf{10}) = 11 \\ Q_\textrm{opt}^{(1)}(\textrm{in}, \textrm{quit}) = 10 \\ V_\textrm{opt}^{(1)}(\textrm{in}) = \max \left[ (11, \textrm{in}, \textrm{stay}); (10, \textrm{in}, \textrm{quit}) \right] = (11, \textrm{in}, \textrm{stay})\\ \pi_\textrm{opt}^{(1)}(\textrm{in}) = \textrm{stay} \end{cases} In the three following examples (game, magic tram, swamp isle) of the next section, the problem definition and the solving algorithms will be clearly separated similarly as what was done for the :ref:`state problems `. The basic structure of the problem is very similar to the state model structure. The key differences are: + the notion of transition (the next state is not certain after an action) + one maximizes rewards instead of minimizing costs (purely conventional) Let us base the problem definition on the following types: .. note:: The :python:`Outcomes` type differs from the :python:`Outcome` type of the state problems precisely to account for transitions. Instead of a simple pair (next state, cost), one has a mapping between next states and pairs (transition, reward) .. literalinclude:: ../../../../src/ai/reinforcement/mdp_types.py :name: mdp_types :linenos: :caption: src If the MDP is defined explicitly from a mapping, the :python:`MDPProblem` can be specified: .. literalinclude:: ../../../../src/ai/reinforcement/mdp_from_mapping.py :pyobject: MDPFromMapping :name: mdp_from_mapping :linenos: :caption: src