Markov Decision Process

Description:

• A MDP defined with:
  • A set of states $s\in S$
  • A set of actions $a\in A$
  • A Transition Function $T(s,a,s’)$
    • Probability that $a$ from $s$ leads to $s’$, i.e., $P(s’|s,a)$
      • represented with Markov Chain
    • Also called the model or the dynamics
  • A reward function $R(s,a,s’)$
    • Sometimes just $R(s)$ or $R(s’)$
  • A start state
  • Maybe a terminal state
• Usually denoted as tuple 〈S, A, T, R, 𝛄〉
• Only work if we know all the reward functions and transitions
• Better than alpha/beta, expectimax as it eliminates the loop
• So you want to:
  • Compute optimal values: use value iteration or policy iteration
  • Compute values for a particular policy: use policy evaluation
  • Turn your values into a policy: use policy extraction (one-step lookahead)

Policies:

• For MDPs, we want an optimal policy 𝛑*: S → A
  • A policy $p$ gives an action for each state as Markov Chain
  • An optimal policy is one that maximizes expected utility if followed
  • An explicit policy defines a reflex agent
  • Expectimax doesn’t compute entire policies, it computes the action for a single state only
    • as states can be infite and non-recurrent, it is cant be represented with Markov Chain

Optimal quantities:

• $V^{\ast }(s)={\max }_a{Q}^{\ast }(s,a)$
  • utility (value) of state $s$, meaning starting in $s$ and acting optimally
  • Max of expected utility for action $a$
• $Q^{\ast }(s,a)=\sum _{s^{\prime }}T(s,a,s^{\prime })[R(s,a,s^{\prime })+\gamma V^{\ast }(s^{\prime })]$
  • expected utility starting out having taken action a from state s and (thereafter) acting optimally
  • $Q\ast =$ Transition Function*(reward of $s^{\prime }$ coming from $s$ + $\gamma$ * value of $s^{\prime }$ )
    • Note that transition funciton is a probablity
• Then $V^{\ast }(s)={\max }_a{\sum }_{s^{\prime }}T(s,a,s^{\prime })[R(s,a,s^{\prime })+\gamma V^{\ast }(s^{\prime })]$
  • which depends on children and children depends on more children
  • Bellman’s Equation
• ${\pi }^{\ast }(s)$: optimal action from state $s$
• Solution to recursive function:
  • Time-limited value:
    • Define $V_k(s)$ to be the optimal value of $s$ if the game ends in $k$ more steps
      • compute the leaf nodes at the kth steps, then use it to find V* of it parent, and up
    • equivalent to limiting the depth to $k$

Value iteration:

• Init: $\forall s:V(s)=0$
  • Starting with $V_0(s)=0$ as we have no time left so no utility for every cells
  • except terminal states
• Iterate:
  • $\forall s:V_{new}(s)={\max }_a{\sum }_{s^{\prime }}T(s,a,s^{\prime })[R(s,a,s^{\prime })+\gamma V(s^{\prime })]$
  • $V=V_{new}$
  • Use $V^{\ast }(s)=\underset{a}{\max }\sum _{s^{\prime }}T(s,a,s^{\prime })[R(s,a,s^{\prime })+\gamma V^{\ast }(s^{\prime })]$ to find best utility of nodes every other nodes
• Repeat until convergent, which is $V^{\ast }$
  • Complexity of each iteration: $O(S^{2}A)$
  • Calculate $V_{k+1}$ for $S$ terms, each term calculate all actions for which each actions, we calculate the utility of every other state
• theorem will converge to unique optimal values
  • Approximations get refined toward optimal value, based on Long-run Proportion of Markov Chain
• Policy extraction:
  • After we have the optimal value $V^{\ast }(s)$, we need to know which action to take
  • ${\pi }^{\ast }(s)=\arg {\max }_a{Q}^{\ast }(s,a)=\arg {\max }_a{\sum }_{s^{\prime }}T(s,a,s^{\prime })[R(s,a,s^{\prime })+\gamma V^{\ast }(s^{\prime })]$
    • do a small expectimax
    • action such that it maximize expected utility

Policy centric methods:

• Policy Evaluation
• Fixed policies:
  • We dont change the value of the policy
  • The tree would be simpler – only one action to take (according to the fixed policy) per state
    • … though the tree’s value would depend on which policy we fixed
  • Define the utility of a state $s$, under a fixed policy $\pi$: V^𝝿(s) = expected total discounted rewards starting in $s$ and following $\pi$
  • $V^{\pi }(s)={\sum }_{s^{\prime }}T(s,\pi (s),s^{\prime })[R(s,\pi (s),s^{\prime })+\gamma V^{\pi }(s^{\prime })]$
  • $O(S^2)$ per iteration
  • Idea 1: turn the recursive bellman equations into updates
    • $V_0^{\pi }(s)=0$
    • $V_{k+1}^{\pi }(s)={\sum }_{s^{\prime }}T(s,\pi (s),s^{\prime })[R(s,\pi (s),s^{\prime })+\gamma V_k^{\pi }(s^{\prime })]$
    • Recursive, exponential cost
  • Idea 2: without the maxes, the bellman equations becomes linear system
    • Policy matrix * vector of $V^{\pi }(s_1)$
    • much simpler, $O(s^3)$ to solve the matrix
• Policy iteration:
  • combines policy evaluation and fixed policy
  • Step 1: policy evaluation: calculate utilities for some fixed policy (not optimal) until convergent
    • $V_{k+1}^{\pi }(s)=\sum _{s^{\prime }}T(s,{\pi }_i(s),s^{\prime })[R(s,{\pi }_i(s),s^{\prime })+\gamma V_k^{{\pi }_i}(s^{\prime })]$
    • updating the value function $V^{{\pi }_i}$ also updates the policy
  • Step 2: Policy improvement: update policy using one-step look-ahead with resulting converged (but not optimal) utilities as future values?
    • ${\pi }_{i+1}(s)=\arg \underset{a}{\max }\sum _{s^{\prime }}T(s,a,s^{\prime })[R(s,a,s^{\prime })+\gamma V^{{\pi }_i}(s^{\prime })]$
  • Repeat until policy converge

Linear Programming: