CS Paper Radar

Performance Gaps Between Open-Loop, Certainty-Equivalent, and Optimal Control Under Action-Dependent Observations

Leo Maynard-Zhang, Sunmook Choi, Yahya Sattar, Yassir Jedra, Sarah Dean, Maryam Fazel

cs.LG eess.SY ·submitted 2026-10-24 03:00 UTC · v1

Abstract

In dynamical systems, feedback can improve performance by allowing decisions to depend on past observations, rather than being designed a priori. Under full observation, the current state is sufficient for decision-making; under partial observation, the controller must instead estimate the state from measurements. When actions also affect observations, control can have a dual role: actions influence both the state and the information available for future decisions. This interaction can invalidate certainty-equivalent (CE) control, a widely used strategy that applies state feedback policies as if the estimated state were the true state. We ask when this suboptimality leads to a quantitative performance gap that grows with the horizon. We study this question in a linear-quadratic system with bilinear observations by comparing the optimal policy, certainty-equivalent control, and the optimal open-loop (OL) policy. We identify an instance-dependent information-strength parameter $q$ and establish distinct performance regimes as $q$ varies. When $q$ is sufficiently small, we show that no policy can improve over OL control by more than $O(1)$ cumulative cost. For large values of $q$, we find that CE achieves an $Ω(T)$ advantage over OL control. Our main finding is that for intermediate values of $q$, we can construct a policy that occasionally probes for information and achieves an $Ω(T)$ advantage over OL control while CE only achieves an $O(1)$ advantage, establishing an $Ω(T)$ gap between CE and optimal control. Our analysis relies on a regret decomposition that captures the tradeoff between the immediate cost of gathering information and its future benefit.

Closest papers

Nearest neighbours by meaning across the whole index.

Polylogarithmic Regret via Certainty Equivalence in Degenerate LQR

cs.LG math.OCeess.SY ·2026-11-16 ·Luca Vignola, Melanie Zeilinger, Bruce D. Lee
theory similarity 0.69
Abstract · 33 pages, 1 figure

Singular input penalties, as in minimum variance control, can reduce what must be identified to control an unknown linear system. In online linear quadratic control, certainty equivalence can achieve polylogarithmic regret when the optimal controller is identifiable from data collected under optimal feedback. With a positive definite input penalty, however, this condition is restrictive, since for an invertible state matrix it requires all unknown parameters to be identifiable under optimal feedback. We show that singular input penalties relax this requirement, expanding the class of problems in which certainty equivalence achieves polylogarithmic regret. Specifically, we prove that a certainty-equivalence algorithm with a short initial exploration phase achieves $O(\log^2 T)$ expected regret over $T$ interactions whenever controller identifiability holds. We complement this guarantee with an $Ω(\sqrt{T})$ minimax lower bound for a family containing a system where controller identifiability fails. For minimum variance control, knowing the range of the input matrix suffices for controller identifiability, a weaker requirement than knowing the full input matrix, as assumed in prior work with positive definite input penalties. This condition also covers underactuated systems, as we illustrate with a cart-pole example.

0.27

Online Causal Configuration for Networked Systems via Doubly Robust Steady-State Learning

cs.LG stat.ML ·2026-11-06 ·Yuli Liu, Zhiheng Zhang
top venuebenchmarktheory similarity 0.66
Abstract · Accepted at NeurIPS 2026

Measurement exploration reveals how interacting local controllers behave but can alter the steady-state regime a network operator seeks to optimize. Exploratory rewards may therefore fail to identify a configuration's no-exploration value: under full exploration, identical logged distributions can conceal different target values. Identification requires accounting for both action-law mismatch and shifts in the steady-state context distribution. We introduce CAUSAL-UCB, which selects configurations using optimistic bounds on target causal values. Its interference-aware clipped doubly robust evaluator produces predecision certificates separating statistical variation from calibrated identification, transport, and temporal-dependence errors. For any finite horizon and predetermined schedule of measurement-exploration rates $\{η_t\}$, we prove lower bounds of $Ω((1+\sum_tη_t)^{-1/2})$ on minimax inference error and $Ω(\sum_tη_t)$ on measurement-induced deployment loss in a stationary, potentially slow-mixing family. We bound regret under valid certificates and selected-information growth, and establish an anytime finite-sample certificate with a shared radius for estimation, selection, and reporting in a restricted known-local-interference model. In a high-mismatch benchmark with 24 paired seeds and 200 rounds, CAUSAL-UCB attains target regret of $1.732$ versus $6.326$ for certified IPS-UCB, with deployment gaps of $30.607$ and $23.217$, respectively. Independent-audit coverage tests and trace-driven semi-synthetic studies further assess certificate coverage and deployment trade-offs.

0.43

Learning and Control Beyond Linearity: Towards a Non-asymptotic Theory for Bilinear Systems

eess.SY cs.LGcs.ROmath.OC+1 ·2026-09-16 ·Yahya Sattar, Yassir Jedra, Robin Strässer, Frank Allgöwer, Maryam Fazel +1 more
benchmark similarity 0.64
Abstract

This tutorial provides a unified view of the emerging area of bilinear learning and control. Using linear systems as a benchmark, it explains what fundamentally changes in the bilinear settings, how recent theory addresses finite-sample learning and control, and how these ideas connect to broader themes in nonlinear control, representation learning, and data-driven decision making. For learning, we emphasize tools that are particularly useful in the bilinear settings, such as one-sided Bernstein's inequality for dependent and heavy-tailed covariates, blocking arguments, and martingale concentration for input-dependent noise. We then apply these tools to obtain finite-sample learning guarantees for fully observed bilinear systems, partially observed bilinear systems, and linear systems with bilinear observations. For control, we discuss quadratic control from bilinear observations, where the classical separation principle fails, and review tractable approaches based on belief-space receding horizon control. We also cover stabilization of bilinear dynamics under state feedback using semi-definite programming, LMI relaxations, sum-of-squares methods, and Koopman-based lifting. We conclude by discussing connections to reinforcement learning and machine learning, and some open problems in combined learning and control of bilinear systems.

0.17

Logarithmic Regret via Passive Change Detection in Piecewise-Stationary Self-Tuning Regulation

cs.LG cs.AI ·2026-10-07 ·A. Ch. Madhusudanarao, Rahul Singh
theory similarity 0.64
Abstract

We study minimum-variance control of an unknown autoregressive system with exogenous inputs and coefficients that change at unknown times. Under bounded independent disturbances, fixed detection gaps, stability and feasibility conditions, and sufficient time between changes, we prove \(O((C+1)\log((T+1)/δ))\) regret with probability at least \(1-δ\), where \(T\) is the horizon and \(C\) the number of changes. Unlike switching bandits, where unselected arms can change unobserved, admissible plant changes provide information during exploitation: the correct feasible controller leaves only the disturbance in the output, whereas a detectable change raises output energy under the old controller. PIECE-CD explores initially and after alarms, then uses gated recursive least squares for control. Its energy test compares windowed output power with a threshold above the noise floor; the extension to unstable controller mismatches also monitors the reference controller's input proposal. We control false alarms across the horizon and prove logarithmic detection delay. Inputs are clipped to prescribed bounds. Logarithmic regret also holds under an explicit condition ensuring that clipping becomes inactive after a finite burn-in. Under the stated feasibility conditions, the extended detector covers destabilizing changes with detectable excess energy over a fixed window.

0.26

Belief-Informed Hybrid Control with Almost-Sure Target-Set Convergence

eess.SY cs.ROmath.OC ·2026-10-06 ·Clinton Enwerem, Saleh Kemal, John S. Baras, Calin Belta
theorycode/data similarity 0.64
Abstract · 8 pages, 5 figures, 6 tables. Project page: https://clintonenwerem.com/belief-hybrid-control/

Controlling a hybrid system to a target set under parameter uncertainty can require informative actions that temporarily drive the system state away from the specified set. We propose a belief-informed dual-control algorithm that combines belief-space receding-horizon selection with an expected-decrease constraint on a nonnegative target-set progress function. To accommodate exploratory deviations, a scalar controller state bounds the constraint's cumulative slack. Our algorithm's two-step lookahead selection uses predicted observations to update the parameter belief before evaluating the subsequent action's admissibility. Under distance-comparison bounds, correct conditional prediction, and recursive feasibility, we prove almost-sure target-set convergence at decision times and bound both the sum of expected progress-function values and the expected neighborhood-entry time. Upper confidence bounds extend these convergence guarantees to bounded model samples with summable error probabilities. In planar regulation with an unknown control direction, we verify recursive feasibility: the proposed two-step selection reduces the Euclidean state norm below 0.01 within 11 decisions for either sign, whereas a myopic one-step selection loses admissibility immediately after zero input. In a simulated bimanual assembly task, our algorithm's one-step implementation uses clearance feedback to complete the assembly under nominal friction, yielding a 96.4% lower infinity-norm relative-position error than the reference-tracking baseline at the method's completion time. At lower friction, its posterior conditioning successfully detects an empty admissible set, whereas a fixed-prior alternative admits an action that violates the conditional decrease constraint. Project page: https://clintonenwerem.com/belief-hybrid-control/.

0.37

Linear Bandits under Exact Sliding-Window Constraints

cs.LG ·2026-10-06 ·Seyed Mohammad Hadi Hosseini, Yasin Abbasi-Yadkori, Sattar Vakili
similarity 0.64
Abstract · 53 pages, including supplementary material; 8 figures and 6 tables

We study linear bandits under exact sliding-window constraints, where every consecutive block of actions must belong to a prescribed feasible set. In the offline setting, where the reward function is known, we show that convexity and cyclic-shift invariance make a stationary solution optimal when $w\mid T$ and within an additive $O(w)$ gap otherwise. In the online setting, we show that geometric structure alone is insufficient for learning, and sublinear regret can be impossible. We introduce a transition diameter $τ$ that quantifies feasible reachability and develop a rare-switching OFUL algorithm with regret $\widetilde{O}(d\sqrt{T}+τd+w)$ against the offline-optimal feasible trajectory. Finally, we remove cyclic invariance and consider general sliding-window constraints, where optimal behavior may be non-stationary. We represent recent action history as the state of a finite-memory control problem and introduce a history-state diameter $D$ that measures feasible communication between viable histories. Combining optimistic remaining-horizon planning with rare policy updates, we obtain a regret bound of $\widetilde{O}(d\sqrt{T}+dD+w)$. We evaluate our approach on real-world and synthetic benchmarks, showing that it maintains exact feasibility while achieving reward and regret comparable to baselines with substantially fewer policy updates.

0.23

Sample complexity of variance-reduced policy gradient: weaker assumptions and lower bounds

cs.LG ·2026-10-02 ·Gabor Paczolay, Matteo Papini, Alberto Maria Metelli, Istvan Harmati, Marcello Restelli
publishedhighly cited similarity 0.63
Abstract

Several variance-reduced versions of REINFORCE based on importance sampling achieve an improved $O(ε^{-3})$ sample complexity to find an $ε$-stationary point, under an unrealistic assumption on the variance of the importance weights. In this paper, we propose the \algo (Defensive Policy Gradient) algorithm, based on defensive importance sampling, which achieves the same rate without any assumption on the variance of ordinary importance weights. We also establish lower bounds in a generalized black-box policy-optimization model that hides states and actions and permits parameter-dependent rewards. In this model, the optimal rates are $Θ(ε^{-4})$ with bounded-variance one-policy feedback and $Θ(ε^{-3})$ with mean-square-smooth coupled two-policy feedback. Under standard policy-regularity conditions, REINFORCE and \algo realize the corresponding oracle conditions and attain the $O(ε^{-4})$ and $O(ε^{-3})$ upper bounds, respectively. Although the lower bounds do not apply directly to the classical MDP interaction model in which these algorithms operate, this correspondence provides oracle-level evidence that the faster rate of \algo is optimal and genuinely separated from that of vanilla policy gradient.

0.71

Computationally Efficient Offline Policy Optimization with All-Policy Linear Realizability

cs.LG ·2026-11-08 ·Zhijie Zheng
theory similarity 0.62
Abstract · 25 pages

We study offline policy optimization in finite-horizon Markov decision processes where every deterministic Markov policy has an action-value function linear in known features, with coefficient norm at most $B$. From independent complete trajectories of one unknown Markov behavior policy, and under all-policy occupancy coverage, we give an algorithm with $\widetilde O(\varepsilon^{-2})$ sample dependence and computational complexity polynomial in $\log(2+B)$. The algorithm performs exactly one convex regression per layer. Its stopped-return targets are the values of a single consistent Markov witness policy. A shared reference design and bounded prediction constraints convert fast clipped-regression error into pointwise confidence for the raw linear predictions. Truncated leverage controls the performance loss without requiring empirical covariance approximation at scale $B^{-2}$. Rounding confidence radii upward preserves the exact witness and yields a polynomial-time bit implementation for rational numerical inputs. The guarantees allow any fixed initial-state distribution; realizability and coverage need only be checked for deterministic policies. We also establish a covariance-coverage variant with uniform approximate realizability and polynomial dependence on $B$. A two-action lower bound shows that the accuracy exponent $2$ is necessary.

0.30