Class 02

[ArnaudDeza]

📘 Class 02 Topics

• Optimization notation and root finding
• Constrained Minimization and line search
• Constrainted Minimization, KKT and IPM, penalty, augmented largrangian

---

📚 Useful References

• 🎥 CMU 16-745 Lectures 3–6

---

Please add an references to any books/tutorials I should refer to!

---

• Presentation
• Chapter

[andrewrosemberg]

We had a great question after the first class from someone with an (NN-Based) RL background: (also in #25 (comment))

When or why should I frame my multi-period (robotics) problem as an optimization problem with non-trivial feasibility constraints? Can't I penalize constraints in the objective function and simulate my environment enough times so that I learn to be feasible and optimal?

My understanding of their question:

I presented the multi-stage problem as an expanding tree where you have to both consider the feasibility of your decisions and cleverly manage how to tackle the impact of future (uncertain) stages:

In (Deep) RL literature, $h(\mathbb{x}_t, \mathbb{u}_t) \geq 0$ are usually trivial box constraints. Most of the time, with no constraints on the state and only bounds on the action that can be easily clamped at the output of the parametric policy model:

$$\mathbb{u}_t = \text{clamp}(\pi(\mathbb{x}_{t-1}), (\underline{ \mathbb{u}}, \bar{ \mathbb{u}}))$$

Constrained RL methods deal with state constraints using modified versions of the penalty method you will mention in the 2nd lecture.
However, without access to an underlying model of the feasible region (or at least a close approximation) that can be exploited by the methods we will go over in your lecture (Interior Point Methods, Augmented Lagrangian Methods, and other similar methods), I haven't found (constrained) model-free RL methods that can perform well in even slightly more complex constraints than a polytope with very few sides.

I am sure there must be clever (yet complex) methods that can converge for a few special cases, but my interpretation of their question is that there is this overall idea among some people that you can just use slightly modified versions of classical RL methods to solve any constrained multi-stage problem.

It would be great to show when penalty methods fail or even when they take incredibly longer to converge than the alternative.