Lihan Lian

Lihan Lian

Robotics enthusiast. Passionate about optimal control and deep learning.

Dwell on Differential Dynamic Programming (DDP) and Iterative Linear Quadratic Regulator (iLQR)

6 minute read

Published:

Although optimal control and reinforcement learning appear to be distinct field, they are, in fact closely related. Differential Dynamic Programming (DDP) and Iterative Linear Quadratic Regulator (iLQR), two powerful algorithms commonly utilized in trajectory optimizations, exemplify how model-based reinforcement learning can bridge the gap between these domains. This blog begins by discussing the fundational principles, including Newton’s method and Bellman Equation. It then delves into the specifics of the DDP and iLQR algorithms, illustrating their application through the classical problem of double pendulum swing-up control.

Netwon’s Method is an iterative optimization algorithm primarily employed for root finding and unconstrained optimization problems. It is a valuable numerical approach that leverages second-order derivative information, especially when the analytical solutions are impractical. Line search is a technique that used in optimization to determine a suitable step size, ensuring appropriate update. It is often used in conjunction with gradient-based methods including Newton’s Method.

  • Newton’s Method for Root Finding

    • Updating Equation:

      The goal of the root finding problem for a function \(f(x)\) is to find the \(x\) such that \(f(x) = 0\). The equation used for iteratively updating the guess of \(x\) is as follows:

      \[x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}\]

    • Derivation:

    1. Start with approximating the function \(f(x)\) by first-order Talyor expansion at \(x_n\):

      \[f(x) \approx f(x_n) + f'(x_n)(x - x_n)\]

    2. Since the the goal is to find the root of \(f(x)\) , set \(f(x)\) to \(0\) using the approximated expression:

      \[0 \approx f(x_n) + f'(x_n)(x_{n+1} - x_n)\]

    3. Solving for \(x_{n+1}\):

      \[x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}\]

  • Newton’s Method for Optimization

    Newton’s method for optimization seeks to find the minimum or maximum of a function \(f(x)\). This involves solving \(\nabla f(x) = 0\), where \(\nabla f(x)\) is the gradient.

    • Updating Equation:
    \[x_{n+1} = x_n - H_f(x_n)^{-1}\nabla f(x_n)\]
    • Derivation:

    1. Use second-order Taylor series expansion to approximate \(f(x)\) around \(x_n\):

      \[f(x) \approx f(x_n) + \nabla f(x_n)^T(x - x_n) + \frac{1}{2}(x - x_n)^T H_f(x_n)(x - x_n)\]

    2. Take the derivative on both side. For optimization, we need to set \(\nabla f(x) = 0\) using the approximated expression:

      \[\nabla f(x) \approx \nabla f(x_n) + H_f(x_n)(x_{n+1} - x_n)\] \[0\approx \nabla f(x_n) + H_f(x_n)(x_{n+1} - x_n)\]

    3. Solving for \(x_{n+1}\):

      \[x_{n+1} = x_n - H_f(x_n)^{-1}\nabla f(x_n)\]

  • The overshoot issue might occur when the function is highly nonlinear. If the quadratic approximation suggests a step size that is too large, it will lead to divergence from the true optimal point. To mitigate the risk of overshoot, a line search can be incorporated into Newton’s method. The idea is to modify the step size along the direction suggested by Newton’s method rather than taking the full step as calculated by \(- H_f(x_n)^{-1} \nabla f(x_n)\).

    • Steps for Incorporating Line Search:
    1. Direction Determination:
      • Compute the Newton step direction: \(p_n = -H_f(x_n)^{-1} \nabla f(x_n)\)
    2. Line Search:
      • Perform a line search along the direction \(p_n\) to find an optimal step size \(\alpha\). The goal is to minimize the function \(f\) along this direction: \(x_{n+1} = x_n + \alpha p_n\)
      • The line search involves evaluating \(f(x_n + \alpha p_n)\) for different values of \(\alpha\) (typically between 0 and 1) to find the step size that results in the greatest reduction in the function value.
    • Backtracking Line Search is one of the systematic approaches that based on Armijo–Goldstein condition. Another techniques called Control Damping introduced in this note can also be used to achieve the same goal.

Bellman’s Principle of Optimality

Principle of Optimality: An optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision.

– Richard Bellman

Bellman’s Principle of Optimality is a fundamental principle to both optimal control and reinforcement learning. In discrete time setting, it is in the form of Bellman Equation and in continuous time setting, it is expressed in the form of Hamilton-Jacobi-Bellman Equation. Check out this blog post for more detailed explanation on these concepts. Since both iLQR and DDP are mostly used as direct method of trajectory optimization, which are in discrete time settings, we will only focus on the Bellman Equation here.

  • Bellman Equation

    The iLQR algorithm can be seen as an iterative method to solve the Bellman Equation for nonlinear systems by successively improving a control policy through local approximations of the Q-function and the value function. Let’s break down iLQR in terms of the Bellman Equation and discuss how Newton’s Method is related to the optimization process.

    1. Bellman Equation Recap:

    The Bellman Equation for the optimal value function \(V^*(x)\) is:

    \[V^*(x) = \min_{u} \left[ g(x, u) + V^*(f(x, u)) \right]\]

    where:

    • \(g(x, u)\) is the immediate cost at state \(x\) with control \(u\).
    • \(f(x, u)\) describes the system dynamics, i.e., how the state transitions from \(x\) to the next state \(x'\).
    • \(V^*(f(x, u))\) is the value function evaluated at the next state.

    The Q-function \(Q(x, u)\) is the cost of taking action \(u\) in state \(x\) and then following the optimal policy thereafter:

    \[Q(x, u) = g(x, u) + V(f(x, u))\]

iLQR Algorithms

DDP Algorithms

Example:

Summary

  • Root Finding: Uses the first derivative \(f'(x)\). The method in the picture shows: \(x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}\)

  • Optimization: Uses both the gradient \(\nabla f(x)\) and the Hessian \(H_f(x)\) for multi-dimensional problems. In one dimension, the Hessian is simply \(f''(x)\), but in general optimization problems, it involves the second-order partial derivatives.

References

You May Also Enjoy

Shed Some Light on Proximal Policy Optimization (PPO) and Its Application Permalink

1 minute read

Published:

Proximal Policy Optimization (PPO) is a reinforcement learning algorithm that refines policy gradient methods like REINFORCE using importance sampling and a clipped surrogate objective to stabilize updates. PPO-Penalty explicitly penalizes KL divergence in the objective function, and PPO-Clip instead uses clipping to prevent large policy updates. In many robotics tasks, PPO is first used to train a base policy (potentially with privileged information). Then, a deployable controller is learned from this base policy using imitation learning, distillation, or other techniques. This blog explores PPO’s core principle, with code available at repo1 and repo2.

From Q-Learning to Deep Q-Learning and Deep Deterministic Policy Gradient (DDPG) Permalink

18 minute read

Published:

Q-learning, an off-policy reinforcement learning algorithm, uses the Bellman equation to iteratively update state-action values, helping an agent determine the best actions to maximize cumulative rewards. Deep Q-learning improves upon Q-learning by leveraging deep Q network (DQN) to approximate Q-values, enabling it to handle continuous state spaces but it is still only suitable for discrete action spaces. Further advancement, Deep Deterministic Policy Gradient (DDPG), combines Q-learning’s principles with policy gradients, making it also suitable for continuous action spaces. This blog starts by discussing the basic components of reinforcement learning and gradually explore how Q-learning evolves into DQN and DDPG, with application for solving the cartpole environment in Isaac Gym simulator. Corresponding code can be found at this repository.

Implementation Details of Basic-and-Fast-Neural-Style-Transfer Permalink

7 minute read

Published:

Neural style transfer (NST) serves as an essential starting point those interested in deep learning, incorporating critical components or techniques such as convolutional neural networks (CNNs), VGG network, residual networks, upsampling and normalization. The basic neural style transfer method captures and manipulates image features using CNNs and the VGG network directly over the input image. In contrast, the fast neural style transfer method employs a dataset to train an inference neural network that can be used for real-time style transfer. This blogs provides the explanation of the implementation of both methods. Corresponding repository can be found here.

On Derivation of Hamilton-Jacobi-Bellman Equation and Its Application Permalink

13 minute read

Published:

The Hamilton-Jacobi-Bellman (HJB) equation is arguably one of the most important cornerstones of optimal control theory and reinforcement learning. In this blog, we will first introduce the Hamilton-Jacobi Equation and Bellman’s Principle of Optimality. We will then delve into the derivation of the HJB equation. Finally, we will conclude with an example that shows the derivation of the famous Algebraic Riccati equation (ARE) from this perspective.