Skip to content

8 Markov Decision Processes I

  • state
  • actions
  • cost associated with each resulting state and action
  • I can learn from one state to the other, what the optimal policy is to get to the goal state

reinforcement learning

  • read the raw pixels from an Atari game to calculate the next best action
  • RL is typically used to solve a control problem
  • How do I drive learning to solve a "game"

What are the long chains of actions I need to take?

Example: The grid world

  • a maze-like problem
  • The agent lives in the grid
  • Walls block his path
  • noisy movement: actions do not always go as planned
  • 80% of the time, the action North takes the agent North.
  • 10% of the time, North takes it West; 10% East
  • If there is a wall in the direction the agent would have been taken, the agent stays put
  • The agent receives rewards each time step
  • small living reward each step (can be negative)
  • Big rewards come at the end (good or bad)
  • goal: maximize rewards

deterministic Grid world

Moving from one state \(S\) takes you to state \(S'\)

In a stochastic grid world:

Now there is some uncertainty: you could take action, but you could also end up somewhere else.

in any grid world, or any MDP,

A MDP is defined as (Markov Decision Process)

  • A set of states \(s \in S\)
  • set of actions \(a \in A\)
  • Transition function: \(T(s, a, s')\)
  • probability that \(a\) from \(s\) leads to \(s'\), ie \(P(s'|s, a)\)
  • also called the model or the dynamics
  • a reward function
  • \(R(s)\) or \(R(s')\)
  • A start State
  • maybe a terminal state.

MDPs are non deterministic search problems

  • one way to solve them is with expectimax
  • we'll have a new tool soon

What is Markov about MDPs?

  • given the future and dependent state the future and past are all independent

Policies

  • in deterministic single-agent search problems we wanted an optimal path or sequence of actions, from start to goal
  • for MDP's we want an optional optimal policy \(\pi^*: S \to a\)
  • An explicit policy defines a reflex agent
  • a policy \(\pi\) ///

optimal POLICIES>

Example: Racing

  • robot car wants to travel far, quickly
  • two actions, slow, fast
  • going faster gets double reward.

What does a search tree look like for this problem. By some chance, you could be at the cool node or the warm/overheated nodes. i can with some probability go to all of these different states

technically we could incur the same negative result

cp zn xzlxo bd vofmulzgdc likd expevtimax for search tree

in a tree, it is color coded wrong as another one we could dod go

\((s, a, s')\) is a transition \(T(s, a, s') = P(s'|s, a)\)

Utilities of sequences

still thinking about expectimax want to go a little bit into utilities still wanna go over some of the concepts I learned.

Utilities of sequences

  • what preferences should an agent have over reward sequences?
  • more or less?
  • \((1, 2, 2)\) or \((2, 3, 4)\)
  • now or later?
  • \((0, 0, 1)\) or \((1, 0, 0)\)

something we might want to think about we are recognizing these preferences, so

so far that makes sense

discount factor? Explain?

  • it is reasonable to maximize the sum of rewards
  • it is also reasonable to prefer which rewards now to rewards later
  • one solution: values of rewards decay exponentially

if i got a diamond now: right now it is worth 1 - after some next step the value is \(1-\gamma\) - after double the time the value is \(1-\)

if we assume stationary preferences:

  • \([a_1, a_2, a_3, \dots] > [b_1, b_2, b_3, \dots]\) implies (both ways) that:
  • \([r, a_1, a_2, a_3, \dots] > [r, b_1, b_2, b_3]\)

there are only two ways to define utilities - additive utility - I prefer \(a_1-a_2\) over \(b_1-b_2\) - discounted utility

Quiz: Discounting

  • given \([10, \_, \_, \_, 1]\)
  • actions: east west, exit (only available exit states at idx 0, idx 4)
  • transitions: deterministic
  • rewards: 0 except exit, which gives 10 and 1 as shown
  • for \(\gamma = 1\), what is the optimal policy
  • for \(\gamma = 0.1\), what is the optimal policy?
  • for which \(\gamma\) is being in idx 4 have equally good policies
g = 1/sqrt(10)

10 * (g^3) =>
1 * g =>

infinite utilities

  • what if the game last forever? do we get infinite rewards/
  • eg racing game
  • solutions
  • finite horizons (similar to depth limited search)
    • terminate episodes after a limited T steps (eg life)
    • gives nonstationary policies (\(\pi\) depends on time left)
  • discounting: use \(0 < y < 1\)

Recap, defining MDPs

  • markov decision processes
  • set of states
  • start state
  • set of actions \(A\)
  • transitions
  • rewards (and discount)
  • mdp quantities so far
  • policy = choice of action for each state
  • utility = sum of undiscounted rewards

so far i've described solving the policy, etc.

Optimal quantities

  • \(V^*(s)\) = expected utility starting in \(s\) and acting optimally
  • the value utility of a q-state \((s, a)\)
  • \(Q^*(s, a)\) = expected utility starting out having taken action from state \(s\) and thereafter acting optimally
  • the optimal policy
  • \(\pi^*(s)\) = optimal action from state \(s\)

Recursive definition of value

One flag: your diamond example says rewards "decay exponentially" but then writes \(1-\gamma\) — with exponential discounting a reward worth 1 now is worth \(\gamma\) after one step and \(\gamma^2\) after two, not \(1-\gamma\).