A Model for Perturbations in MDPs
Nominal MDP
\[\mathcal{K}_t = \{h_t(s,a) \leq 0\}\]
\[\text{Cost: } c_t(s,a)\]
\[\text{Kernel: } P_t(ds'|s,a)\]
\[\text{Optimal: } \pi^*_t,\; V^*_t\]
Perturbed MDP (small \(\epsilon\))
\[\widetilde{\mathcal{K}}_t = \{h_t(s,a) + \epsilon\widetilde{h}_t(s,a) \leq 0\}\]
\[\text{Cost: } c_t(s,a) + \epsilon\,\widetilde{c}_t(s,a)\]
\[\text{Kernel: } \widetilde{P}_t(ds'|s,a) \text{ (may also change)}\]
\[\text{Optimal: } \widetilde{\pi}^*_t,\; \widetilde{V}^*_t\]
Given \(\pi^*\) and \(V^*\) from the nominal MDP (solved once):
- Do we have \(\widetilde{\pi}^* \approx \pi^* + \epsilon\,d + o(\epsilon)\)
- can we compute \(d\) using simple computations
Solving the Perturbed OCP
Unperturbed Bellman: \[V_t(s_t) = \min_{a_t} \left\{c_t(s_t,a_t) + V_{t+1}(f_t(s_t,a_t))\right\} \quad \text{s.t.}\;\; h_t(s_t,a_t) \leq 0\]
Perturbed Bellman — expand \(V^\epsilon_t = V_t + \epsilon\widetilde{V}_t + o(\epsilon)\):
\[V_t(s_t) + \epsilon\widetilde{V}_t(s_t) + o(\epsilon) = \min_{a_t} \Big\{
\underbrace{c_t + V_{t+1}\circ f_t}_{\text{nominal cost-to-go}} + \epsilon\underbrace{\Big(\widetilde{c}_t + \widetilde{V}_{t+1}\circ f_t\Big)}_{\text{first-order perturbation}}+ o(\epsilon)
\Big\} \quad \text{s.t.}\;\; h_t(s_t,a_t) + \epsilon\widetilde{h}_t \leq 0\]
Separate \(O(1)\) and \(O(\epsilon)\) terms:
- \(O(1)\) → recovers original Bellman (trivially satisfied by \(\pi^*\), \(V^*\))
- \(O(\epsilon)\) → a single QP per time-step for the correction \(d_t(s)\), \(\widetilde{V}_t(s)\)
Ignore \(o(\epsilon)\) term in the optimization
Regularity Assumptions & Main Theorem
A1 (Smoothness): \(c_t\), \(h_t\) twice differentiable; \(f_t\) differentiable; \(V_t\) twice differentiable.
A2 (LICQ): Active-constraint Jacobian \(A_t(s) := \bigl[\nabla_a h_{t,i}(s,\pi^*_t(s))\bigr]_{i \in \mathcal{A}(s)}\) is full row rank for all \(s\).
A3 (SOSC): \(\nabla^2_{aa}(c_t + V_{t+1}\circ f_t)(s,\pi^*_t(s)) \succ 0\) (positive definite).
A4 (Strict Complementarity): \(\mu^*_{t,j}(s) > 0\) for all active constraints \(j\).
Theorem — Differentiability of the Perturbed Optimal Policy
Under A1–A4, the optimal perturbed policy \(\pi^\epsilon_t\) is differentiable in \(\epsilon\) at \(\epsilon = 0\), and
\[\boxed{\pi^\epsilon_t = \pi^*_t + \epsilon\,d_t + o(\epsilon)}\]
where the correction direction \(d_t(s)\) is computable via a single QP.
Proof: Implicit Function Theorem applied to the KKT stationarity conditions.
First-Order Perturbation: Quadratic Case
Nominal QP: \[\min_{z \in \mathbb{R}^p} \;\frac{1}{2}z^\top H z + e^\top z \;\text{ s.t. }\; Az = b\] \[\Rightarrow z^* = -H^{-1}(e + A^\top\kappa^*)\] \[\kappa^* = -(AH^{-1}A^\top)^{-1}(AH^{-1}e+b)\]
Perturbed QP: \[\min_z \;\frac{1}{2}z^\top(H+\epsilon\widetilde{H})z + (e+\epsilon\widetilde{e})^\top z\] \[\text{ s.t. }\; Az = b + \epsilon\widetilde{b}\]
First-Order Correction
Taylor expansion of matrix inverse: \[(H+\epsilon\widetilde{H})^{-1} = H^{-1} - \epsilon\, H^{-1}\widetilde{H}H^{-1} + o(\epsilon)\]
First-order correction: If \(z^* = 0\), then
\[\boxed{\widetilde{z}^\epsilon - z^* = \epsilon\, \underbrace{H^{-1}\!\begin{bmatrix} A^\top M A H^{-1} - I \;\big|\; A^\top M \end{bmatrix}\!\begin{bmatrix} \widetilde{e} \\ \widetilde{b} \end{bmatrix}}_{\text{Correction Direction: } d} + \underbrace{o(\epsilon)}_{\text{Negligible for small } \epsilon}}\]
\[\widetilde{\kappa}^\epsilon - \kappa^* = -\epsilon\, M\bigl(AH^{-1}\widetilde{e} + \widetilde{b}\bigr) + o(\epsilon)\]
where \(M = (AH^{-1}A^\top)^{-1}\)
Note: \(\widetilde{z}^\epsilon\) is differentiable in \(\epsilon\) → consistent with main theorem.
WASP Algorithm: Warm-Start DP
Per-state quantities (all evaluated at nominal optimum \(\pi^*_t(s)\)):
\[H(s) = \nabla^2_{aa} c_t(s,\pi^*_t(s)) + \nabla^2_{aa} (V_{t+1} \circ f_t)(s,\pi^*_t(s))\]
\[\widetilde{e}(s) = \nabla_a \widetilde{c}_t(s,\pi^*_t(s)) + \nabla_a (\widetilde{V}_{t+1} \circ f_t)(s,\pi^*_t(s))\]
\[A(s) = \bigl[\nabla_a h_{t,i}(s,\pi^*_t(s))^\top\bigr]_{i \in \text{active}}, \qquad \widetilde{b}(s) = -\bigl[\widetilde{h}_{t,i}\bigr]_{i \in \text{active}}\]
WASP closed-form update:
\[d_t(s) = H^{-1}\!\begin{bmatrix} A^\top M A H^{-1} - I \;\big|\; A^\top M \end{bmatrix}\!\begin{bmatrix} \widetilde{e}(s) \\ \widetilde{b}(s) \end{bmatrix}\]
\[\boxed{\widetilde{\pi}^*_t(s) \approx \pi^*_t(s) + \epsilon\,d_t(s)} \qquad \text{[policy update]}\]
\[\widetilde{V}_t(s) = \widetilde{c}_t(s,\pi^*_t(s)) + \nabla_a(c_t + V_{t+1}\circ f_t)^\top(s,\pi^*_t(s))\,d_t(s) \qquad \text{[value update]}\]
Perturbations in Forecasts
Physical systems have measurable (and forecastable) parameters \(\theta_t\):
\[\min_{\{a_t\}} \;\; \sum_{t=0}^T c_t(s_t, a_t, \theta_t) \quad\text{s.t.}\quad h_t(s_t, a_t, \theta_t) \leq 0,\;\; s_{t+1} = f_t(s_t, a_t, \theta_t)\]
Perturbed problem — parameter shifts by \(\delta\theta_t\) (forecast update):
\[\min_{\{a_t\}} \;\; \sum_{t=0}^T c_t(s_t, a_t, \theta_t + \delta\theta_t) \quad\text{s.t.}\quad h_t(s_t, a_t, \theta_t + \delta\theta_t) \leq 0,\;\; s_{t+1} = f_t(s_t, a_t, \theta_t + \delta\theta_t)\]
WASP for parametrized OCP — define:
\[\widetilde{c}_t(s,a) = \nabla_\theta c_t(s,a,\theta_t)\cdot\delta\theta_t, \quad \widetilde{h}_t(s,a) = \nabla_\theta h_t(s,a,\theta_t)\cdot\delta\theta_t, \quad \widetilde{f}_t(s,a) = \nabla_\theta f_t(s,a,\theta_t)\cdot\delta\theta_t\]
A similar WASP formula applies — perturbation in parameters maps to perturbation in cost/constraints/dynamics.
