stat.MLOct 16, 2026

Parametric Resonance in Primal-Dual Learning for Slowly Non-Stationary Constrained MDPs

Authors: Maxime Baelde

Organizations: Antvoice, Paris, France

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Primal-dual methods for constrained Markov decision processes are analyzed under a two-timescale assumption, with non-stationarity entering through two channels. In the additive channel, where the constraint level oscillates, the dual oscillation saturates at a floor set by the moving optimum and is amplified linearly by the timescale ratio. In the parametric channel, where the constraint sensitivity oscillates, a coherent modulation carries no resonant forcing at any depth: the dual update's stiffness modulation cancels the primal update's damping modulation. Instability instead comes from a mismatch between the constraint estimate used by the primal update and the measurement used by the dual update, producing a parametric resonance at twice the pair's natural frequency. The tolerated mismatch grows with the square root of the forcing bandwidth and collapses with the square root of the dual-to-primal step-size ratio. These results hold on the tangent linear-quadratic reduction around an active saddle, for one constraint and for KK constraints under a common modulation and an isotropy condition. Driving both updates from the same estimate removes the resonant forcing but introduces a stationary offset equal to the estimator's bias. In a Lagrangian soft actor-critic agent, the multiplier locks onto the sub-harmonic at the timescale ratios its identified linear loop predicts and a coherent cost critic suppresses the lock-in, while a proportional (PID) term, predicted to leave the lock-in in place, suppresses most of it through the projection of the multiplier.

Figures & tables

implementationpolicymultiplierrr
openai/safety-starter-agents , PPO-Lagrangian3×10−43\times 10^{-4}5×10−25\times 10^{-2}167167
PKU-Alignment/omnisafe , PPOLag3×10−43\times 10^{-4}3.5×10−23.5\times 10^{-2}117117
PKU-Alignment/Safe-Policy-Optimization , single agent3×10−43\times 10^{-4}3.5×10−23.5\times 10^{-2}117117
Table 1: Default step sizes in the reference Lagrangian implementations
Figure 1: Measured resonance tongue: Floquet exponent per step against the forcing frequency
εθ\varepsilon_{\theta}ελ\varepsilon_{\lambda}h=ελ−εθh=\varepsilon_{\lambda}-\varepsilon_{\theta}predicted μ\mumeasured μ\mu
000−4.502×10−4-4.502\times 10^{-4}−4.502×10−4-4.502\times 10^{-4}
00.150.15−7.55×10−5-7.55\times 10^{-5}−7.52×10−5-7.52\times 10^{-5}
00.200.20+4.94×10−5+4.94\times 10^{-5}+4.97×10−5+4.97\times 10^{-5}
0.30−0.30-0.30+2.992×10−4+2.992\times 10^{-4}+2.988×10−4+2.988\times 10^{-4}
0.20.50.30+2.992×10−4+2.992\times 10^{-4}+2.961×10−4+2.961\times 10^{-4}
00.900.90+1.798×10−3+1.798\times 10^{-3}+1.755×10−3+1.755\times 10^{-3}
Table 2: Parametric channel: predicted against measured Floquet exponent per step
r=α/ηr=\alpha/\etaω0\omega_{0}ζ\zetameasured threshold4σ/ω04\sigma/\omega_{0}4σ/ω~04\sigma/\tilde{\omega}_{0}
10−110^{-1}real spectrum>1>1none ( ≤1.98\leq 1.98 )n/an/a
0.250.25real spectrum>1>1none ( ≤1.98\leq 1.98 )n/an/a
0.960.960.0086440.5079none ( ≤1.98\leq 1.98 )2.35032.0315
0.980.980.0086740.50261.96732.31762.0104
110.0087040.49751.94842.28631.9899
10210^{2}0.0099920.0450200.18020.180220.18008
Table 3: Existence boundary of the phenomenon: mismatch threshold maximized over the forcing frequency
Figure 2: Lagrangian SAC: sub-harmonic amplitude of the multiplier against the forcing frequency
Appendix figures & tables13 assets

Supplementary material from the paper’s appendix.

Appendix

θ\thetapolicy parameter, tangent coordinateω\omegafrequency of the non-stationarity
λ\lambdamultiplier of the active constraintAAamplitude of the additive forcing
η\etaprimal step sizeω~0\tilde{\omega}_{0} , ω0\omega_{0}natural frequency, continuous and exact
α\alphadual step sizeσ\sigmadamping rate of the pair
r=α/ηr=\alpha/\etatimescale ratioζ=σ/ω~0\zeta=\sigma/\tilde{\omega}_{0}reduced damping
g^\hat{g}constraint estimate, consumed by the primalεθ\varepsilon_{\theta}modulation depth seen by the primal
ggconstraint measurement, consumed by the dualελ\varepsilon_{\lambda}modulation depth seen by the dual
Appendix
Table 4: Table of notation
Figure 3: Bandwidth law: mismatch threshold normalized by its own single-line threshold
B/σB/\sigma00.52832
threshold (RMS)0.12640.13820.15900.23100.4262
// ε0\varepsilon_{0}0.991.081.251.813.34
κ\kappa deducedn/a0.3520.2790.2860.318
Appendix
Table 5: Mismatch threshold against bandwidth, and the constant of ( 21 )
η\eta10−310^{-3}α\alpha10−110^{-1}
rr100100ω~0\tilde{\omega}_{0}0.010.01
ω0\omega_{0} (discrete)0.009992160.00999216σ\sigma (per step)4.502×10−44.502\times 10^{-4}
ζ=σ/ω~0\zeta=\sigma/\tilde{\omega}_{0}0.0450200.0450202ω02\omega_{0}0.01998430.0199843
threshold (peak)0.180220.18022threshold (r.m.s.)0.127440.12744
Appendix
Table 6: Reference operating point of the parametric experiments
η\etaα\alpharrζ\zetasup⁡ωΔλ\sup_{\omega}\Delta\lambda/ (2Aa/c2)max⁡{1,r}/\,(2Aa/c^{2})\max\{1,r\}/ (Aα/σ)/\,(A\alpha/\sigma)
10−310^{-3}10−310^{-3}10.5000.2941.471.468
10−310^{-3}10−210^{-2}100.1572.1181.061.049
10−310^{-3}10−110^{-1}1000.04522.3221.121.005
10−210^{-2}10−110^{-1}100.1432.3201.161.049
10−110^{-1}10−210^{-2}0.11.6480.2001.00n/a
Appendix
Table 7: Additive channel: worst case over forcing frequency against the timescale ratio
η\etar=α/ηr=\alpha/\etameasured thresholdpredicted 4σ/ω04\sigma/\omega_{0}ratio
10−510^{-5}10410^{4}0.018010.018001.00
10−410^{-4}10310^{3}0.056940.056931.00
10−310^{-3}10210^{2}0.18010.18021.00
10−210^{-2}10100.56780.57640.99
10−110^{-1}11out of range2.075n/a
Appendix
Table 8: Parametric channel: collapse of the mismatch tolerance with the timescale ratio
ηα\eta\alphabracket for r⋆r^{\star}rrexponent past threshold (per step)
10−210^{-2}(0.85,0.90](0.85,0.90]––
10−410^{-4}(0.96,0.98](0.96,0.98]0.980.98+3.4×10−5+3.4\times 10^{-5}
10−410^{-4}(0.96,0.98](0.96,0.98]11+8.4×10−5+8.4\times 10^{-5}
10−410^{-4}(0.96,0.98](0.96,0.98]10210^{2}+4.6×10−3+4.6\times 10^{-3}
Appendix
Table 9: Existence boundary refined, and the exponent just past it
B/σB/\sigmaε=0.3\varepsilon=0.3ε=0.7\varepsilon=0.7
0 (single line)−3.41×10−4-3.41\times 10^{-4}−2.06×10−4-2.06\times 10^{-4}
1−3.91×10−4-3.91\times 10^{-4}−2.68×10−4-2.68\times 10^{-4}
4−4.26×10−4-4.26\times 10^{-4}−3.56×10−4-3.56\times 10^{-4}
16−4.43×10−4-4.43\times 10^{-4}−4.06×10−4-4.06\times 10^{-4}
Appendix
Table 10: Coherent modulation under broadband forcing: top Lyapunov exponent per step
η\etarrσ\sigmaB/σB/\sigmasingle lineband BBpredicted band BB
10−310^{-3}1004.502×10−44.502\times 10^{-4}100.12770.25700.2576
10−410^{-4}10004.500×10−54.500\times 10^{-5}1000.042220.23930.2273
Appendix
Table 11: Cancellation of the primal step size at fixed physical bandwidth
εθ\varepsilon_{\theta}ελ\varepsilon_{\lambda}Floquet exponentexp⁡(μT)\exp(\mu T)max⁡λ\max\lambda (unprojected)max⁡λ\max\lambda (projected)final Δλ\Delta\lambda% clipped
00−4.502×10−4-4.502\times 10^{-4}5.26×10−135.26\times 10^{-13}1100.0
0.30.3−3.748×10−4-3.748\times 10^{-4}5.98×10−115.98\times 10^{-11}4.6634.1682.78026.7
0.90.9−2.271×10−4-2.271\times 10^{-4}6.38×10−76.38\times 10^{-7}11.21–––
00.3+2.988×10−4+2.988\times 10^{-4}1.41×1081.41\times 10^{8}4.45×1064.45\times 10^{6}3.9332.68528.0
0.30+2.988×10−4+2.988\times 10^{-4}1.41×1081.41\times 10^{8}4.66×1054.66\times 10^{5}–––
0.20.5+2.961×10−4+2.961\times 10^{-4}1.19×1081.19\times 10^{8}1.17×1061.17\times 10^{6}5.6693.64936.6
Appendix
Table 12: Full recursion over 200 periods (62 800 steps), without and with the projection
 ω\omega0.0180.0220.0260.0300.036
 ω/2ω0\omega/2\omega_{0}0.710.871.031.191.43
locked seedsLagrangian5/107/1010/106/101/10
 PID0/101/100/101/100/10
 coherent0/50/50/50/50/5
 PID, ε=0.3\varepsilon=0.3–1/102/10––
 PID, ε=0.35\varepsilon=0.35–1/100/10––
Appendix
Table 13: Lagrangian SAC at r=100r=100 : locking, forced response, projection, return and constraint value against the forcing frequency
Additive control (Table 15 )4040 forcing periods
Additive worst-case sweep (Table 7 )40004000 points log-spaced, ω∈[10−7,π]\omega\in[10^{-7},\pi]
Floquet tongue-centre maxima121121 points on ω/2ω0∈[0.4,1.6]\omega/2\omega_{0}\in[0.4,1.6] , 3535 on [1.6,5.0][1.6,5.0]
Figure 1 grid589589 integer periods, 196196 – 784784 steps
Tongue-centre mismatch bisection5050 halvings
Existence-boundary sweep (Table 3 )6060 periods log-spaced, 88 – 30003000 steps, refined by 121121 points on [0.55,1.45] π/ω0[0.55,1.45]\,\pi/\omega_{0}
Existence-boundary bisection1818 halvings, mismatch split εθ=+d/2\varepsilon_{\theta}=+d/2 , ελ=−d/2\varepsilon_{\lambda}=-d/2 , d≤1.98d\leq 1.98
Appendix
Table 14: Numerical parameters of the protocol
ω\omegacoupledfrozen policyratio
10−610^{-6}0.2000002000.00010 000
10−410^{-4}0.19999420.000100
10−310^{-3}0.1994502.00010
10−210^{-2}0.1596980.2001.3
10−110^{-1}0.0208940.0200081.0
110.0020870.0020861.0
Appendix
Table 15: Additive channel: peak-to-peak multiplier excursion tracking the moving optimum, coupled against frozen policy
More in this topic

Markov Decision Processes

Markov decision processes model sequential choices under uncertainty, linking actions, state transitions, and rewards to planning and reinforcement learning.

See all 157 papers

Explore similar work

CardsList
Jun 5, 2026

Residual-Controlled Multiplier Learning for Stochastic Constrained Decision-Making

Stochastic constrained decision-making requires optimizing performance objectives while enforcing statistical requirements such as safety or fairness. However, standard primal--dual methods struggle to update multipliers robustly under stochastic mini-batch feedback, as the noise of mini-batch gradients and constraint estimates can be directly accumulated into the multiplier memory. To address this issue, we propose Residual-Controlled Multiplier Learning (RCML), which reformulates multiplier updating as projected-pressure feedback. The central idea is to decompose the projected multiplier into an effective pressure signal for primal descent and a pressure-memory residual for finite-gain multiplier tracking. To handle heterogeneous and noisy observations, we further augment this residual-integral backbone with modular stochastic stabilization components. For the convex-affine backbone, we establish finite-gain convergence, derive a stochastic residual bound under mini-batch feedback, and show that the residual feedback law admits a local KKT-residual interpretation near regular KKT points of nonconvex problems. Experiments across optimization, allocation, and fair-ranking tasks show that RCML improves feasibility control and multiplier stability while maintaining competitive objective performance. Code is released at https://anonymous.4open.science/r/RCML-3114/.

Kang Liu, Jianchen Hu, Ziyu Qu +3

School of Future Technology Xi’an Jiaotong University Xi’an, China, 710049 · School of Automation Science and Engineering Xi’an Jiaotong University Xi’an, China, 710049 · School of Mathematics and Physics China University of Geosciences Wuhan, China, 430074 +2

Stochastic OptimizationPrimal-Dual OptimizationConstrained Optimization
AskPDF
Oct 1, 2026

Rate-Optimal Algorithm for Adversarial Linear CMDPs

We study episodic adversarial linear constrained Markov decision processes (CMDPs) with unknown transitions, where both the loss and constraint functions may vary adversarially across episodes. The best previous algorithm achieves O~(K3/4)\widetilde{\mathcal{O}}(K^{3/4}) regret and cumulative constraint violation, leaving a gap to the optimal O~(K)\widetilde{\mathcal{O}}(\sqrt{K}) dependence on the number of episodes KK. We close this gap by proposing a new primal dual algorithm that achieves O~(K)\widetilde{\mathcal{O}}(\sqrt{K}) regret and cumulative constraint violation without assuming Slater's condition. We further extend the algorithm to achieve the same O~(K)\widetilde{\mathcal{O}}(\sqrt{K}) guarantees for regret and hard constraint violation, which does not allow constraint violations to cancel across episodes. The main challenge is that learning linear CMDPs requires uniform concentration over a value function class with a controlled covering number, whereas standard techniques in constrained online learning, such as policy mixing, can make this class more complex. Our algorithm combines adaptive Follow the Regularized Leader (FTRL), contracted value estimation, and an exponential Lyapunov function. An adaptive dual regularizer offsets the dependence on the dual weights in the primal regret bound, removing the need for policy mixing. We further show that the normalization in the FTRL update bounds the policy parameters independently of the magnitudes of the dual weights, which explains why the resulting policy class remains compatible with uniform concentration. Under feature access, the computational complexity is independent of the size of the state space.

Kihyun Yu, Honghao Wei, Dabeen Lee

KAIST · Washington State University · Seoul National University

Regret Minimization in RLMarkov Decision ProcessesConstrained RLLinear Markov Decision Processes
AskPDF
Jul 30, 2026

Hierarchical Multilevel Monte Carlo for Order-Optimal Neural Actor-Critic in Average-Reward CMDPs

Constrained Markov Decision Processes (CMDPs) provide a natural framework for reinforcement learning in safety-critical applications, where agents maximize long-term reward while satisfying long-term constraints. Although primal-dual actor-critic methods with linear critics are well understood, extending order-optimal convergence guarantees to neural critics in average-reward CMDPs has remained open. The main challenge is a fundamental bias-cost trade-off in neural critic estimation: under Neural Tangent Kernel (NTK) analysis, reducing critic bias substantially increases critic optimization cost, preventing order-optimal convergence in the primal-dual framework. We resolve this bottleneck by introducing a hierarchical Multilevel Monte Carlo (MLMC) neural critic that performs debiasing simultaneously across trajectory sampling and critic optimization. The resulting estimator attains the bias of a long critic optimization run with only logarithmic expected sample cost. Building on this estimator, we develop a primal-dual Natural Actor-Critic algorithm that achieves both an optimality gap and a constraint violation of order O~(T−1/2)\tilde{O}(T^{-1/2}). This establishes the first order-optimal convergence guarantees for infinite-horizon average-reward CMDPs with general policy parameterization and neural critics, while eliminating the need to know the underlying mixing time. Our results are novel even in the unconstrained setting.

Ankur Naskar, Vaneet Aggarwal

Indian Institute of Science, India · Purdue University, USA

Average-Reward RLConstrained RLActor-Critic MethodsPolicy LearningVariance Reduction
AskPDF