Reinforcement Learning
Many sequential decision making and control problems are hard to provide explicit supervision for.
Instead provide a reward function and let the learning algorithm figure out how to choose actions over time.
Successful in applications such as helicopter flight, legged locomotion, network routing, marketing strategy selection, etc
Markov Decision Processes (MDP)
Provide formalism for many RL problems
Terminology
- States : $s$
- Actions : $a$
- State Transition Probabilities : $P_{sa}$
- Discount Factor : $\gamma \in [0,1)$
- Reward Function : $R : S \times A \mapsto \mathbb{R}$
Dynamics of MDPs
- Start in some state $s_0$
- Choose some action $a_0 \in A$
- MDP randomly transitions to successor state $s_1 \sim P_{s_0a_0}$
- Pick another action
- Repeat
Represent as $$ s_0 \overset{a_0}{\rightarrow} s_1 \overset{a_1}{\rightarrow} s_2 \overset{a_2}{\rightarrow} s_3 \overset{a_3}{\rightarrow} \dots $$ Total Payoff $$ R(s_0, a_0) + \gamma R(s_1, a_1) + \gamma^2 R(s_2, a_2) + \dots $$ Goal : Maximise expected value of total payoff $$ E \left[ R(s_0) + \gamma R(s_1) + \gamma^2 R(s_2) + \dots \right] $$
Policy
Function $\pi : S \mapsto A$ maps states to actions
Execute a policy by following the prescribed action
Value Function
The expected sum of discounted rewards upon starting in $s$ and taking actions according to $\pi$ $$ V^\pi(s) = \mathbb{E} \left[ R(s_0) + \gamma R(s_1) + \gamma^2 R(s_2) + \dots | s_0 = s,\pi \right] $$
Bellman Equation
Given a fixed policy $\pi$, it’s value function $V^\pi$ satisfies the Bellman equations $$ V^\pi(s) = R(s) + \gamma \sum_{s’ \in S} P_{s\pi(s)}(s’) V^\pi(s’) $$ Which consists of two terms:
- Immediate reward $R(s)$ Get for starting in $s$
- Expected sum of future discounted rewards Can we rewritten as $E_{s’\sim P_{s\pi(s)}}[V^\pi(s’)]$ The expected sum of starting in $s’$ where $s’$ is distributed according to to $P_{s\pi(s)}$
Can be used to efficiently solve for the value function $V^\pi$
- Write down one equation for every state
- Gives a set of $|S|$ linear equations in $|S|$ variables
Optimal Value Function
Best possible expected sum of discounted rewards which can be attained using any policy
$$ V^*(s) = \max_\pi V^\pi (s) $$
Which has it’s own version of the Bellman Equation
$$ V^{\ast}(s) = R(s) + \max_{a\in A} \gamma \sum_{s’\in S}{P_{sa} (s’) V^{\ast}(s’)} $$
The second term is a $\max$ over all possible actions because that is the optimal reward.
Optimal Policy
$$ \pi^{\ast}(s) = \arg \max_{a\in A} \sum_{s’\in S} P_{sa}(s’) V^*(s’) $$
Which gives the action that attains the $\max$ in the optimal value function
For every state $s$ and policy $\pi$ $$ V^\ast(s) = V^{\pi*}(s) \geq V^\pi(s) $$ Which says that
The value function for the optimal policy is equal to the optimal value function for every state $s$
The value function for the optimal policy is greater than or equal to every other policy
- $\pi^*$ is the optimal policy for all states
Value Iteration and Policy Iteration
Two efficient algorithms for solving finite-state MDPs with known transition probabilities
Value Iteration
For each state s, initialize $V(s) := 0$ for until convergence do For every state, update $$ V(s) := R(s) + \max_{a\in A} \gamma \sum_{s’} P_{sa}(s’) V(s’) $$
- Repeatedly update estimated value function using the Bellman equation
Can be:
- Synchronous
- Compute new values for all states and update at once
- Can be viewed as implementing a Bellman Backup Operator, which maps the current estimate to a new estimate
- Asynchronous
- Loop over states and update one at a time
Both algorithms will cause $V$ to converge to $V^*$
Policy Iteration
Initialise $\pi$ randomly
for until convergence do
Let $V := V^\pi$
For each state $s$ $$ \pi(s) := \arg \max_{a \in A} \sum_{s’} P_{sa}(s’) V(s’) $$
- Repeatedly computes value function for the current policy
- Update policy using current value function
- This is the policy that is greedy w.r.t. $\bold V$
- The value function can be updated using Bellman equations
- After a finite number of iterations, $V$ will converge to $V^\ast$ and $\pi$ to $\pi^\ast$
Value vs Policy Iteration
- No universal agreement which is better
- Small MDPs : Policy iteration tends to be fast
- Larger MDPs : Value iteration might be faster
- Policy iteration can reach the exact $V^*$
- Value iteration will have small non-zero error
Learning a Model for an MDP
In many realistic problems, we do not know the state transition probabilities and rewards
Must be estimated from data
Given enough trials, can derive maximum likelihood estimates for the state transition probabilities $$ P_{sa}(s’) = \frac{num. \text{ times } a \text{ led to } s’ } {num. \text{ times we took } a} $$ In the case of $\frac{0}{0}$, can set $P$ to $\frac{1}{|S|}$ (estimate as uniform)
Efficient Update
Keep count of numerator & denominator
Solving Learned MDP
- Can use policy/value iteration
Continuous State MDPs
- Infinite number of states
- Consider settings where state space is $S = \mathbb{R}^d$
Discretization
- Simplest way
- Discretize state space
- Use value/policy iteration
Downsides
- Fairly naive representation for $V^*$
- Assumes the value function is constant over each discretization interval
- Piecewise constant representation isn’t good for many smooth functions
- Little smoothing over inputs
- No generalization over different grid cells
- Suffers from curse of dimensionality
- For $S = \mathbb{R}^d$, we will have $k^d$ states
Rule of Thumb
- Works well for 1D/2D cases
- Can work for 3D/4D cases
- Rarely works above 6D
Value Function Approximation
- Approximate $V^*$ directly
Using Model/Simulator
- Assume we have a model/simulator for the MDP
- Any black-box with
- Input : State $s_t$, Action $a_t$
- Output : Next-state $s_{t+1}$ sampled
Getting the Model
Using physics simulation
- Can use off-the-shelf physics simulation
Data collected in the MDP
- Can be done with:
- Random actions
- Executing some policy
- Other way of choosing actions
[?] Control law?
- Apply learning algorithm to predict $s_{t+1}$ as function of $s_t$
Example : Learn linear model
using linear regression $$ \arg \min_{A,B} \sum_{i=1}^{n} \sum_{t=0}^{T-1} \left\Vert s_{t+1}^{(i)} - (A s_t^{(i)} + Ba_t^{(i)}) \right\Vert^2_2 $$ Can build either a deterministic $$ s_{t+1} = As_t + Ba_t $$ or stochastic model $$ s_{t+1} = As_t + Ba_t + \epsilon_t $$ with $\epsilon_t$ being a noise term usually modelled as $\epsilon_t \sim \mathcal{N}(0,\Sigma)$
or non-linear function $$ s_{t+1} = A\phi_s(s_t) + B\phi_a(a_t) $$ Eg: Locally weighted linear regression
Fitted Value Iteration
- Algorithm for approximating the value function of a continuous state MDP
- Assume state space $S = \mathcal{R}^d$
- But action space $A$ is small and discrete
Perform value iteration update $$ \begin{aligned} V(s) :&= R(s) + \gamma \max_a \int_{s’} P_{sa}(s’) V(s’) ds’ \cr &= R(s) + \gamma \max_a E_{s’ \sim P_{sa}} [V(s’)] \end{aligned} $$
- Main difference is the $\int$ instead of $\sum$
- Approximately update over a finite sample of states $s^{(1)}, \dots, s^{(n)}$
- Use supervised learning algorithm, linear regression to approximate value function as linear/nonlinear function of the states
$$ V(s) = \theta^T \phi(s) $$
Algorithm
Compute $y^{(i)}$, the approximation to $R(s) + \gamma \max_a E_{s’ \sim P_{sa}} [V(s’)]$ (RHS)
Use supervised learning to get $V(s) = y^{(i)}$
Repeat
Convergence
- Cannot be proved to converge
- But in practice it often does, and works well for many problems
Deterministic Simplification
- Can set $k=1$
- Because expectation of a deterministic distribution requires 1 sample
Policy
- Outputs $V$, an approximation of $V^*$
- Implicitly defines policy
When in state $s$, choose $$ \arg \max_a E_{s’\sim P_{sa}} [V(s’)] $$
- Process for computing/approximating this is similar to the fitted value iteration algorithm