RL as an Adaptive Optimal Control

Slide: Explore reinforcement learning (RL) by comparing the Markov Chain and the Markov Decision Process (MDP). Understand how RL functions as a direct adaptive optimal control method through the example of Q-Learning. Inspired by Sutton's paper "Reinforcement Learning is Direct Adaptive Optimal Control" and Pieter Abbeel's lecture "Foundations of Deep RL".

Recap

Problem Formulation

Consider the deterministic discrete-time optimal control problem:

$$\begin{array}{rl}\underset{x_{1:N},u_{1:N-1}}{min}& \sum _{n=1}^{N-1}l(x_n,u_n)+l_F(x_N)\\ \text{s.t. }& x_{n+1}=f(x_n,u_n)\\ & u_n\in \mathcal{U}\end{array}$$

The first-order necessary conditions for optimality can be derived using:

• The Lagrangian framework (special case of KKT conditions)
• Pontryagin's Minimum Principle (PMP)

Lagrangian Formulation

Form the Lagrangian:

$$L=\sum _{n=1}^{N-1}l(x_n,u_n)+{\lambda }_{n+1}^{\mathrm{\top }}(f(x_n,u_n)-x_{n+1})+l_F(x_N)$$

Define the Hamiltonian:

$$H(x_n,u_n,{\lambda }_{n+1})=l(x_n,u_n)+{\lambda }_{n+1}^{\mathrm{\top }}f(x_n,u_n)$$

Rewrite the Lagrangian using the Hamiltonian:

$$L=H(x_1,u_1,{\lambda }_2)+[\sum _{n=2}^{N-1}H(x_n,u_n,{\lambda }_{n+1})-{\lambda }_n^{\mathrm{\top }}{x}_n]+l_F(x_N)-{\lambda }_N^{\mathrm{\top }}{x}_N$$

Optimality Conditions

Take derivatives with respect to $x$ and $\lambda$:

$$\begin{array}{rl}\frac{\partial L}{\partial {\lambda }_n}& =\frac{\partial H}{\partial {\lambda }_n}-x_{n+1}=f(x_n,u_n)-x_{n+1}=0\\ \frac{\partial L}{\partial x_n}& =\frac{\partial H}{\partial x_n}-{\lambda }_n^{\mathrm{\top }}=\frac{\partial l}{\partial x_n}+{\lambda }_{n+1}^{\mathrm{\top }}\frac{\partial f}{\partial x_n}-{\lambda }_n^{\mathrm{\top }}=0\\ \frac{\partial L}{\partial x_N}& =\frac{\partial l_F}{\partial x_N}-{\lambda }_N^{\mathrm{\top }}=0\end{array}$$

For $u$, we write the minimization explicitly to handle constraints:

$$\begin{array}{rl}{u}_n=& \arg \underset{u}{min}H(x_n,u,{\lambda }_{n+1})\\ & \text{s.t. }u\in \mathcal{U}\end{array}$$

Summary of Necessary Conditions

The first-order necessary conditions can be summarized as:

$$\begin{array}{rl}{x}_{n+1}& ={\mathrm{\nabla }}_{\lambda }H(x_n,u_n,{\lambda }_{n+1})\\ {\lambda }_n& ={\mathrm{\nabla }}_{x}H(x_n,u_n,{\lambda }_{n+1})\\ u_n& =\arg \underset{u}{min}H(x_n,u,{\lambda }_{n+1}),\text{s.t. }u\in \mathcal{U}\\ {\lambda }_N& =\frac{\partial l_F}{\partial x_N}\end{array}$$

In continuous time, these become:

$$\begin{array}{rl}\dot{x}& ={\mathrm{\nabla }}_{\lambda }H(x,u,\lambda )\\ -\dot{\lambda }& ={\mathrm{\nabla }}_{x}H(x,u,\lambda )\\ u& =\arg \underset{\tilde{u}}{min}H(x,\tilde{u},\lambda ),\text{s.t. }\tilde{u}\in \mathcal{U}\\ \lambda (t_F)& =\frac{\partial l_F}{\partial x}\end{array}$$

Application to LQR Problems

For LQR problems with quadratic cost and linear dynamics:

$$\begin{array}{rl}l(x_n,u_n)& =\frac{1}{2}(x_n^{\mathrm{\top }}{Q}_n{x}_n+u_n^{\mathrm{\top }}{R}_n{u}_n)\\ l_F(x_N)& =\frac{1}{2}{x}_N^{\mathrm{\top }}{Q}_N{x}_N\\ f(x_n,u_n)& =A_n{x}_n+B_n{u}_n\end{array}$$

The necessary conditions simplify to:

$$\begin{array}{rl}{x}_{n+1}& =A_n{x}_n+B_n{u}_n\\ {\lambda }_n& =Q_n{x}_n+A_n^{\mathrm{\top }}{\lambda }_{n+1}\\ {\lambda }_N& =Q_N{x}_N\\ u_n& =-R_n^{-1}{B}_n^{\mathrm{\top }}{\lambda }_{n+1}\end{array}$$

This forms a linear two-point boundary value problem.

MDP & RL

Bridging Optimal Control and RL

Markov Chains

• State space $\mathcal{X}$
• Action space $\mathcal{U}$
• System dynamics $f(x_n,u_n)$
• Cost function $l(x,u)$ and $l_F(x)$

Find feedback $\mathit{u}\mathbf{=}\mathit{K}\mathbf{(}\mathit{x}\mathbf{)}$ to minimize $J(x_0,u)$

$$J(x_0,u)=\mathbb{E}[\sum _{n=0}^{N-1}l(x_n,u_n)+l_F(x_N)]$$

subject to $x_{n+1}\sim f(x_n,u_n)$.

Markov (Decision) Process

• State space $\mathcal{S}$
• Action space $\mathcal{A}$
• Transition dynamics $P(s^{\prime }|s,a)$
• Reward function $R(s,a,s^{\prime })$

Find policy $\mathit{\pi }\mathbf{(}\mathit{a}\mathbf{|}\mathit{s}\mathbf{)}$ to maximize $V(s_0,\pi )$

$$V(s_0,\pi )=\mathbb{E}[\sum _{n=0}^H{\gamma }^{n}R(s_n,a_n,s_{n+1})]$$

subject to $s_{n+1}\sim P(\cdot |s_n,a_n)$, $a_n\sim \pi (\cdot |s_n)$, where $\gamma \in [0,1)$ is the discount factor.

RL is an adaptive method to solve MDP in the absence of model knowledge.

Value Function and Action-Value Function

Optimal Control:

• Value Function:$$V(x)=\underset{u}{min}\mathbb{E}[\sum _{n=0}^{N-1}l(x_n,u_n)+l_F(x_N)|x_0=x]$$
• Action-Value Function:$$Q(x,u)=\mathbb{E}[l(x,u)+V(x^{\prime })|x^{\prime }\sim f(x,u)]$$

Reinforcement Learning:

• Value Function:$$V^{\pi }(s)=\mathbb{E}[\sum _{n=0}^H{\gamma }^{n}R(s_n,a_n,s_{n+1})|s_0=s,a_n\sim \pi (\cdot |s_n)]$$
• Action-Value Function:$$Q^{\pi }(s,a)=\mathbb{E}[R(s,a,s^{\prime })+\gamma V^{\pi }(s^{\prime })|s^{\prime }\sim P(\cdot |s,a)]$$

Q-Learning

The Scalability Challenge

For discrete, low-dimensional problems with a known model, Optimal Control and Model-based RL can be solved exactly using Dynamic Programming (DP). But what if...

• The model $f(x,u)$, $l(x,u)$ or $P(s^{\prime }|s,a),R(s,a,s^{\prime })$ is unknown?
• The state or action space is too large or continuous making DP loops intractable?
• The system is too complex to model accurately?

We need model-free, stochastic, and approximate methods.

(Tabular) Q-Learning

(Tabular) Q-Learning replace expectation by samples:

• For an state-action pair $(s,a)$ , receive $s^{\prime }\sim P(s^{\prime }|s,a)$
• Consider old estimate $Q_k(s,a)$
• Consider new sample estimate: $\text{target}(s^{\prime })=R(s,a,s^{\prime })+\gamma \underset{a^{\prime }}{max}{Q}_k(s^{\prime },a^{\prime })$
• Incorporate the new estimate into a running average:$$Q_{k+1}(s,a)\leftarrow (1-\alpha )Q_k(s,a)+\alpha [\text{target}(s^{\prime })]$$

Q-learning converges to optimal policy even if you're acting suboptimally and is called off-policy learning. Requires sufficient exploration and a learning rate $\alpha$ that decays appropriately:

$$\sum _{t=0}^{\mathrm{\infty }}{\alpha }_t(s,a)=\mathrm{\infty }\sum _{t=0}^{\mathrm{\infty }}{\alpha }_t^2(s,a)<\mathrm{\infty }$$

Approximate Q-Learning

Instead of a table, we use a parametrized Q function $Q_{\theta }(s,a)$ to approximate:

• Learning rule:$$\begin{array}{rl}\text{target}(s^{\prime })& =R(s,a,s^{\prime })+\gamma \underset{a^{\prime }}{max}{Q}_{{\theta }_k}(s^{\prime },a^{\prime })\\ {\theta }_{k+1}& \leftarrow {\theta }_k-\alpha {\mathrm{\nabla }}_{\theta }[\frac{1}{2}(Q_{\theta }(s,a)-\text{target}(s^{\prime }){)}^2]{|}_{\theta ={\theta }_k}\end{array}$$
• Practical details:
  • Use Huber loss instead of squared loss on Bellman error:$$L_{\delta }(a)=\{\begin{array}{ll}\frac{1}{2}{a}^2& \text{for }|a|\le \delta \\ \delta (|a|-\frac{1}{2}\delta )& \text{otherwise}\end{array}$$
  • Use RMSProp instead of vanilla SGD.
  • It is beneficial to anneal the exploration rate over time.

Conclusion

RL as an Adaptive Optimal Control

Common Core:

• Value Function
• Bellman Equation
• Sequential Decision Making

The Evolution:

• Expectation $\to$ Samples
• Table $\to$ Function Approximation
• Exact Solution $\to$ Stochastic Optimization

A powerful and adaptive optimal control framework.