Regime-Adaptive Robust Critic
Implementation & benchmark of arXiv:2608.06545 — Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions
Source paper: Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions arXiv:2608.06545 ⓘ · analyzed Aug 31, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Train a neural average-reward actor-critic that turns robustification on only when the estimated uncertainty scale σH₀ is comparable to or larger than the desired critic accuracy ε. In the high-tolerance regime use an ordinary nominal Bellman target; in the low-tolerance regime add a total-variation pessimism penalty proportional to the learned bias span. This avoids injecting a large robustness penalty when it is statistically unnecessary while retaining protection against transition uncertainty when it matters.
Formulas
Mathematical statement
The paper's central minimax characterization is $NSA\asymp\frac{SA}{\varepsilon^{2}}\min\{H_{0},H_{\sigma}\}$ when $\varepsilon\gtrsim\sigma H_{0}$, and $NSA\asymp\frac{SA}{\varepsilon^{2}}\left(\min\{H_{0},H_{\sigma}\}+\sigma H_{\sigma}^{2}\right)$ when $\varepsilon\lesssim\sigma H_{0}$. Here $S$ is the number of states, $A$ the number of actions, $N$ the samples per state-action pair, $\sigma$ the radius of the rectangular total-variation uncertainty set, $\varepsilon$ the target performance accuracy, $H_{0}$ the span of the nominal optimal average-reward bias function, and $H_{\sigma}$ the span of the robust optimal bias function. For a neural implementation, define the span of a scalar critic $h_\theta$ on a state reservoir as $\widehat H(\theta)=\max_i h_\theta(s_i)-\min_i h_\theta(s_i)$. Under total variation $\operatorname{TV}(q,p)=\frac12\|q-p\|_1$, the worst-case expectation over a TV ball is approximately $p^\top h-\frac{\sigma}{2}\operatorname{span}(h)$ when enough probability mass can be moved from high-value to low-value states. Therefore use the robust average-reward residual $\delta_t=r_t-\hat\rho+h_\theta(s_{t+1})-h_\theta(s_t)-\frac{\sigma}{2}\widehat H(\theta)$ whenever $\varepsilon\leq c\sigma\widehat H_0$. The additional $\sigma H_\sigma^2$ term explains why robustification should not always be enabled: the low-tolerance regime has a distinct uncertainty-dependent statistical cost.
Implementation notes
Integrate this method into the critic target of an average-reward neural actor-critic, not into the actor network initially. Maintain a scalar bias critic hθ(s), an average-reward estimate ρ̂, and a reservoir R of several thousand recently observed states plus uniformly sampled replay states. Every K critic updates, compute Ĥ0=maxR hθ−minR hθ using a slowly updated nominal critic or an exponential moving average of the current critic before robustification. Set the regime ratio τ̂=σĤ0/ε. For each transition (s,a,r,s′), form the nominal residual δnom=r−ρ̂+hθ(s′)−hθ(s). Form the robust residual δrob=δnom−(σ/2)Ĥ, where Ĥ is computed from the current reservoir; stop gradients through Ĥ so the critic cannot reduce the penalty simply by shrinking its own span. Use δrob when τ̂≤c and δnom when τ̂>c, with c initially 1 and optional hysteresis thresholds 0.8 and 1.2 to prevent rapid switching. Update θ by Huber loss on the selected residual, update ρ̂ by ρ̂←ρ̂+βρ(r−ρ̂), and update the actor using an advantage estimated from the selected critic. The mathematical quantities supplied by the paper are the regime boundary and span-dependent penalty; the state reservoir and uncertainty estimate are empirical engineering approximations. If σ is unknown, estimate it from an ensemble of transition models using the average clipped total variation between ensemble predictive distributions. First test on a 20-state uncertain chain or MiniGrid with a 2-layer MLP, comparing nominal actor-critic, always-robust critic, and this adaptive switch with equal replay samples. Evaluate nominal return, worst-case return under sampled TV perturbations, critic span, switching frequency, and steps to reach a fixed robust-return threshold. The method succeeds if it learns faster than always-robust training when ε>σH₀ and achieves higher worst-case return than nominal training when ε<σH₀, without oscillation near the boundary.
Verification
This idea has not been verified yet.
Verification happens in two stages: Stage 1 — a mechanism check on a toy system confirms the claimed mathematical phenomenon reproduces; Stage 2 — a benchmark implements the idea on a real (small) neural network task and compares it against a tuned baseline over 8 paired seeds with a permutation test.
Artifacts
Artifacts unavailable.