Overview of MDPs

• Evaluative feedback
• Associative aspects
• Sequential decision making
• Tradeoff immediate vs. delayed rewards
• Bandits: $q_{\ast }(a)$
• MDPs: $q_{\ast }(s,a)$ and $v_{\ast }(s)$

Agent-Environment Interface

Problem Representation

“Any problem of learning goal-directed behavior can be reduced to three signals passing back and forth between an agent and its environment.”

• Choices (actions of agent)
• Basis for choices (states of environment)
• Goal definition (rewards to agent)

Agent-Environment Interface

• Interaction at discrete time steps, $t=0,1,2,3,\cdots$
• Agent: chooses actions $A_t\in \mathcal{A}(s)$
• Environment: has a state $S_t\in \mathcal{S}$
• Environment: generates rewards $R_t\in \mathcal{R}$
• Trajectory: $S_0,A_0,R_1,S_1,A_1,R_2,S_2,A_2,R_3,S_3,\cdots$

Time Steps

• $t=0,1,2,3,\cdots$
• May refer to fixed intervals of real time
• May refer to arbitrary successive stages of decision making and acting

Actions

• $A_t\in \mathcal{A}(s)$
• Any decision we want to learn how to make
• Low-level controls - voltage on a motor (continuous)
• High-level decisions - have lunch (binary), go to graduate school (binary)
• Can be mental or computational (think about $X$, focus on $Y$)

States

• $S_t\in \mathcal{S}$
• Anything we can know that might be useful in decision making
• Low-level sensations (sensor readings)
• High-level and abstract (symbolic description of objects in a room)
• May include memory
• May be mental (not knowing: where are my keys)
• May be subjective (surprise in a clearly defined sense)

Rewards

• $R_t\in \mathcal{R}$
• Formalizes the goal of the agent
• Part of the environment
• Computed/derived inside natural or artificial (robotic) agents, but considered external to agent

Agent-Environment Boundary

• Environment: anything that cannot be changed arbitrarily by agent
• Boundary: limit of agent’s absolute control (but not of its knowledge)
• Robots: motors, linkages, sensors $\in$ environment
• Person/animal: muscles, skeleton, sensory organs $\in$ environment

Example: Bioreactor

• Objective: Determine temperature and stirring rate for bioreactor
• State: thermocouple, other sensors, ingredients, target chemicals
• Actions: target temperature and stirring rate (passed to lower level controller)
• Reward: rate of target chemical production
• States & actions: vectors
• Reward: scalar value

Example: Pick-and-Place Robot

• Objective: Control motion of robotic arm in repetitive task (fast smooth motion)
• State: Positions and velocities of linkages
• Action: Motor voltages
• Reward: +1 (for each pick-and-place success) - jerkiness of motion

Discuss these Examples

• Stop smoking
• Play Packman
• Invest wisely
• Driving to a destination (move the boundry around)

Look at Example 3.3

• Action set that depends on the state
• Markovity of states defined in graph
• Dynamics are tabulated (finite MDP)

Finite MDP

• $\mathcal{S}\mathcal{,}\mathcal{A}\mathcal{,}\mathcal{R}$ are finite sets
• RVs $S_t,A_t,R_t$ have PMFs
• MDP dynamics:

$$\begin{array}{c}p(s^{\prime },r|s,a)=\text{Pr}\left\{\begin{array}{c}{S}_t=s^{\prime }\\ R_t=r\end{array}|\begin{array}{c}{S}_{t-1}=s\\ A_{t-1}=a\end{array}\right\}\\ \sum _{s^{\prime }\in \mathcal{S}}\sum _{r\in \mathcal{R}}p(s^{\prime },r|s,a)=1,\mathrm{\forall }s\in \mathcal{S},a\in \mathcal{A}(s)\end{array}$$

Markov Property

• Not restriction on MDP
• Markovity is in the state

$$(S_t,A_t)\mapsto S_{t+1}$$

Goals

• Maximize total amount of reward received
• Don’t focus on immediate (short run) reward
• Focus on cumulative reward in the long run

Rewards

• Incentivize what you want the agent to learn
• If you want the agent to learn “to do something for us, then provide rewards to it in such a way that in maximizing them the agent will also achieve our goals.”
• Rewards communicate what to achieve, not how to achieve it

Chess

• Reward winning (what)
• Don’t reward subgoals (how)
  • Taking opponent’s pieces (how)
  • Controlling center of board (how)
  • +10 for win (reward winning the game)
  • -1 for each turn (reward winning the game in few moves)

Examples

Do these reward the right thing?

• Robotic walking - make reward proportional to forward motion on each time step
• Escape maze - reward is -1 for every time step

Returns

• Choose $A_t$ to maximize return $G_t$
• Return $G_t$ is cumulative reward received after time $t$
• Return $G_t=R_{t+1}+R_{t+2}+R_{t+3}+\cdots +R_T$
• Return could be some other function of reward sequence
• Note: Action $A_t$ cannot maximize $G_{t-k}$ for $k>0$

Episodes

• Episode is a repeated interaction
  • Starting state is known or drawn from distribution
  • Ending in terminal state $s\in {\mathcal{S}}^{+}$ at time $T<\mathrm{\infty }$
  • $T$ is an RV
• Episodic tasks (games, mazes, etc.)
• Nonepisodic tasks continue without end
  • Process control task
  • Robot with long life span
  • $T=\mathrm{\infty }$

Discounting

• Choose $A_t$ to maximize discounted return $G_t=\sum _{k=0}^{\mathrm{\infty }}{\gamma }^k{R}_{t+k+1}$

• $\gamma \in [0,1]$ is the discount rate

• Discounting puts diminishing weight on future rewards

• $\gamma =0$ (myopic agent) focuses attention on immediate reward $R_{t+1}$

• $\gamma \to 1$ (farsighted agent)

Recursion

$$\begin{array}{rl}{G}_t& =\sum _{k=0}^{\mathrm{\infty }}{\gamma }^k{R}_{t+k+1}=R_{t+1}+\gamma G_{t+1}\mathrm{\forall }t<T\\ G_t& =\sum _{k=0}^{\mathrm{\infty }}{\gamma }^k=\frac{1}{1-\gamma },R_t=1\mathrm{\forall }t\end{array}$$

Example: Cart-Pole

Example: Cart-Pole

Maze escape robot

• $R_t=1$ for esacpe and $R_t=0$ otherwise. Why doesn’t this work?
• How can we communicate through the reward what we want the robot to do?

Task Types

• Episodic: $S_{t,i},A_{t,i},R_{t,i},{\pi }_{t,i},T_i$ for the $i^{\text{th}}$ episode
• Convention: Drop the $i$ most of the time
• Continuing: $S_t,A_t,R_t,{\pi }_t,T$
• Same notation for both task types

Return

• Epsiodic: $G_t=R_{t+1}+R_{t+2}+\cdots +R_T$
• Continuing: $G_t=R_{t+1}+R_{t+2}+R_{t+3}+\cdots$
• Want same notation for both task types
• To unify notation, define absorbing (square) state for episodic task where rewards are zero

Unified Notation

$$G_t=\sum _{k=0}^{T-t-1}{\gamma }^k{R}_{t+k+1}=\sum _{k=t+1}^T{\gamma }^{k-t-1}{R}_k$$

• Continuing: $T=\mathrm{\infty }$ and $\gamma \in [0,1)$ (need convergence)
• Episodic: $T<\mathrm{\infty }$ and $\gamma \in [0,1]$ (convergence guaranteed)
• Episode numbers not needed

Policy

$$\begin{array}{c}\pi (a|s)=\text{Pr}\{A_t=a|S_t=s\}\\ a\in \mathcal{A}(s),s\in \mathcal{S}\end{array}$$

• Policy: How the agent chooses actions in the context of a state
• RL methods: How $\pi$ changes based on experience

State-Value Function for Policy $\pi$

$$v_{\pi }(s)=E_{\pi }[G_t|S_t=s]=E_{\pi }[\sum _{k=0}^{\mathrm{\infty }}{\gamma }^k{R}_{t+k+1}|S_t=s]$$

• Expected return (value) when starting in state $s$ and following policy $\pi$ thereafter

Action-Value for Policy $\pi$

$$\begin{array}{rl}{q}_{\pi }(s,a)& =E_{\pi }[G_t|S_t=s,A_t=a]\\ & =E_{\pi }[\sum _{k=0}^{\mathrm{\infty }}{\gamma }^k{R}_{t+k+1}|S_t=s,A_t=a]\end{array}$$

• Expected return (value) of taking action $a$ in state $s$ and following policy $\pi$ thereafter

Look Ahead (Monte Carlo Methods)

• Expectations in $v_{\pi }$ and $q_{\pi }$ can be estimated from sample averages over many episodes
• How? For each state maintain average return that followed that state under policy $\pi$. This converges to $v_{\pi }$.
• How? For each state-action pair maintain average return that followed under policy $\pi$. This converges to $q_{\pi }$.

Look Ahead (Approximation Methods)

• If too many states, then keeping averages in each state is not practical.
• Approximate $v_{\pi },q_{\pi }$ as parameterized functions (e.g. DNN) and adjust parameters to match observed returns.

Exercises

• Give an equation for $v_{\pi }$ in terms of $q_{\pi }$ and $\pi$ (solution)
• Given an equation for $q_{\pi }$ in terms of $v_{\pi }$ and four-argument $p$ (solution)

Answers

$$\begin{array}{rl}{v}_{\pi }(s)& =\sum _a{q}_{\pi }(s,a)\pi (s|a)\\ q_{\pi }(s,a)& =\sum _{s^{\prime }}\sum _r[r+\gamma v_{\pi }(s^{\prime })]p(s^{\prime },r|s,a)\end{array}$$

Backup Diagram for $v_{\pi }$

$$v_{\pi }(s)=\sum _a{q}_{\pi }(s,a)\pi (s|a)$$

Backup Diagram for $q_{\pi }$

$$q_{\pi }(s,a)=\sum _{s^{\prime }}\sum _r[r+\gamma v_{\pi }(s^{\prime })]p(s^{\prime },r|s,a)$$

Value Recursion

Substitute $v_{\pi }$-$q_{\pi }$ relations into one another to obtain recursions.

$$\begin{array}{rl}{v}_{\pi }(s)& =\sum _a\pi (a|s)\sum _{s^{\prime },r}[r+\gamma v_{\pi }(s^{\prime })]p(s^{\prime },r|s,a)\\ q_{\pi }(s,a)& =\sum _{s^{\prime },r}[r+\gamma \sum _{a^{\prime }}{q}_{\pi }(s^{\prime },a^{\prime })\pi (s^{\prime }|a^{\prime })]p(s^{\prime },r|s,a)\end{array}$$

State-Value Recursion

$$v_{\pi }(s)=\sum _a\pi (a|s)\sum _{s^{\prime },r}[r+\gamma v_{\pi }(s^{\prime })]p(s^{\prime },r|s,a)$$

• Consistency condition between $v_{\pi }(s)$ and $v_{\pi }(s^{\prime })$
• Expected value of $r+\gamma v_{\pi }(s^{\prime })$ over $p(s^{\prime },r,a|s)=\pi (a|s)p(s^{\prime },r|s,a)$
• Bellman equation for $v_{\pi }$
• $v_{\pi }$ is unique solution to Bellman equation
• Bellman equation: Compute, approximate, learn $v_{\pi }$

Backup Diagram for $v_{\pi }$

• Start state $s$ at top (open circle)
• Policy $\pi$ gives action $a$ (solid circle)
• Environment responds with reward $r$ and next state $s^{\prime }$ according to probability $p$

Gridworld

• See Example 3.5 in text (page 60).
• Here are my calculations.

Optimal Policies

• Value function defines a partial order for policies

$$\pi \ge {\pi }^{\prime }\iff v_{\pi }(s)\ge v_{{\pi }^{\prime }}(s)\mathrm{\forall }s\in \mathcal{S}$$

• An optimal policy exists but may not be unique
• Denote optimal policies by ${\pi }_{\ast }$
• Denote optimal state-value function $v_{\ast }=v_{{\pi }_{\ast }}$

Optimal Policies

$$\begin{array}{rl}{v}_{\ast }(s)& =\underset{\pi }{max}{v}_{\pi }(s)\mathrm{\forall }s\in \mathcal{S}\\ q_{\ast }(s,a)& =\underset{\pi }{max}{q}_{\pi }(s,a)\mathrm{\forall }s\in \mathcal{S}\text{and}a\in \mathcal{A}(s)\end{array}$$

• The same policy optimizes both value functions

Relations

• Q: What does the optimal policy ${\pi }_{\ast }$ look like?
• A: It puts all its weight on the best action (greed)

$$\begin{array}{c}{\pi }_{\ast }(a|s)={\mathbb{1}}_{a=a_{\ast }}=\{\begin{array}{ll}1,& a=a_{\ast }\\ 0,& \text{otherwise}\end{array}\\ v_{\ast }(s)=\sum _{a\in \mathcal{A}(s)}{\pi }_{\ast }(a|s)q_{\ast }(s,a)=\underset{a\in \mathcal{A}(s)}{max}{q}_{\ast }(s,a)\end{array}$$

Recursion for Optimal Value Function

Leveraging this derivation and $\pi ={\pi }_{\ast }$, we have

$$\begin{array}{rl}{v}_{\ast }(s)& =\underset{a}{max}{q}_{\ast }(s,a)\\ & =\underset{a}{max}E[R_{t+1}+\gamma G_{t+1}|S_t=s,A_t=a]\\ & =\underset{a}{max}E[R_{t+1}+\gamma v_{\ast }(S_{t+1})|S_t=s,A_t=a]\\ & =\underset{a}{max}\sum _{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma v_{\ast }(s^{\prime })]\end{array}$$

Apply Greed

$$\begin{array}{rl}{v}_{\pi }(s)& =\sum _a\pi (a|s)\sum _{s^{\prime },r}[r+\gamma v_{\pi }(s^{\prime })]p(s^{\prime },r|s,a)\\ v_{\ast }(s)& =\underset{a}{max}\sum _{s^{\prime },r}[r+\gamma v_{\ast }(s^{\prime })]p(s^{\prime },r|s,a)\end{array}$$

$$\sum _a{\pi }_{\ast }(a|s)\stackrel{\text{greed}}{⟶}\underset{a}{max}$$

Recursion for Optimal Action-Value Function

Applying greed, we have

$$\begin{array}{rl}{q}_{\pi }(s,a)& =\sum _{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma \sum _{a^{\prime }}\pi (s^{\prime }|a^{\prime })q_{\pi }(s^{\prime },a^{\prime })]\\ q_{\ast }(s,a)& =\sum _{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma \underset{a^{\prime }}{max}{q}_{\ast }(s^{\prime },a^{\prime })]\end{array}$$

Backup Diagrams for Optimal Value Functions

Optimal Policy for Gridworld

(We don’t yet know how to find $v_{\ast }$. Take this as given for now.)

Optimal Policy $\leftarrow$ Optimal Value

• Given $v_{\ast }(s)$, ${\pi }_{\ast }(a|s)$ assigns non-zero probability to best action(s) and zero probability to all other actions
• Optimal policy ${\pi }_{\ast }$ is greedy wrt optimal value $v_{\ast }$
• A one-step (short-run) search is long-run optimal
• $v_{\ast }$ “takes into account the reward consequences of all possible future behavior”
• Expected long-term return is encoded into $v_{\ast }$

Optimal Policy $\leftarrow$ Optimal Value

• Same for $q_{\ast }(s,a)$ … in any state $s$, choose the best action $a$
• Costs more to store $q_{\ast }(s,a)$ than $v_{\ast }(s)$
• $q_{\ast }$ encodes best action(s) without needing to know values of next states or environment dynamics $p(s^{\prime },r|s,a)$

Bellman’s Eqations in Practice

$$\begin{array}{rl}{v}_{\ast }(s)& =\underset{a}{max}\sum _{s^{\prime },r}[r+\gamma v_{\ast }(s^{\prime })]p(s^{\prime },r|s,a)\\ q_{\ast }(s,a)& =\sum _{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma \underset{a^{\prime }}{max}{q}_{\ast }(s^{\prime },a^{\prime })]\end{array}$$

• Usually don’t know $p(s^{\prime },r|s,a)$
• Usually can’t compute (sum and max too big)
• Markov property (assume this)