betaFeedback

WorksComputer Science

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

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 qq and establish distinct performance regimes as qq varies. When qq is sufficiently small, we show that no policy can improve over OL control by more than O(1)O(1) cumulative cost. For large values of qq, we find that CE achieves an Ω(T)Ω(T) advantage over OL control. Our main finding is that for intermediate values of qq, we can construct a policy that occasionally probes for information and achieves an Ω(T)Ω(T) advantage over OL control while CE only achieves an O(1)O(1) advantage, establishing an Ω(T)Ω(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.

Introduction

In sequential control problems, feedback allows a controller to adapt its actions based on observations collected over time, rather than committing to an action sequence in advance. In partially observed control, the controller must choose actions based on incomplete information about the state. Moreover, an action may influence not only the state, but also the quality of future observations. This creates a dual effect Bar-Shalom and Tse, [3]: a controller’s action affects both its immediate performance and the information available for future decisions. Consequently, an action that is not immediately optimal for control may be worthwhile to improve future decision-making. In the classical linear-quadratic-Gaussian (LQG) problem this tradeoff does not arise due to action-independent observations, and the separation principle allows estimation and control to be treated separately [26, 2]. When observations are action-dependent, this separation can fail [22], raising the question of when the benefit of actively acquiring information is large enough to justify its cost.

The informational role of actions is also central in sequential decision-making. In regret-minimization bandits, performance is measured by cumulative sub-optimality relative to a benchmark, and actions balance immediate reward against acquiring information useful for future decisions [5]. In pure exploration problems such as best-arm identification, the sampling strategy is designed directly around collecting enough information to distinguish among alternatives [8]. Interestingly, in some of these problems, strong guarantees can be achieved using a sampling allocation fixed in advance, without adapting to observations [18]. This raises a broader question in sequential decision-making: when is a policy fixed in advance sufficient, and when does adaptation to observations provide a genuine advantage?

In dynamic or stateful environments, this distinction also determines which policy class provides an appropriate benchmark for regret analysis. Benchmarks may range from fixed action policies, to an open-loop action sequence chosen in advance, to a fully history-dependent closed-loop policy. These choices can lead to substantially different notions of performance. For example, in restless bandits, weak regret compares against a fixed-arm benchmark [25], whereas strong regret compares against an optimal closed-loop policy [24, 19]. Optimal closed-loop policies, however, can be hard to compute. In some structured settings, this difficulty can be avoided by weakening the benchmark: when state evolution is deterministic, the state trajectory is determined by the action sequence, so an open-loop benchmark suffices. This is the case in several stateful bandit models with deterministic state evolution [16, 14, 21, 4, 13]. Thus, whether adaptation provides a meaningful advantage depends on the structure of the problem.

Related questions about benchmark choice arise in recent works on bandits with latent dynamics. Choi et al. [7] study a non-stationary bandit problem with latent linear dynamics and bilinear rewards, measuring regret against an optimal open-loop action sequence. Hwang et al. [11] develop an adaptive optimism-based algorithm for this model while retaining the same open-loop benchmark. Other dynamic learning and online-control formulations make different comparator choices. One common notion in non-stationary bandits is dynamic regret, which compares against a time-varying oracle [17]; related formulations have also been studied in linear control [9]. In online and non-stochastic control, regret is often instead measured relative to a restricted class of feedback-controllers [1, 23]. Together, these formulations emphasize that there is no universal choice of benchmark for sequential problems with dynamics.

In partially observed dynamical systems, this benchmark question leads to several natural policy classes with different uses of feedback. Open-loop control commits to an action sequence without adapting to observations, while certainty-equivalent (CE) control responds to observations through a state estimate, applying the fully observed controller as if that estimate were the true state. The optimal policy may instead depend on the full information state, and explicitly account for how actions affect future information. While CE is known to be optimal in the classical LQG setting [15], recent work shows that CE can be suboptimal in linear-quadratic control with bilinear observations [22]. However, this result does not characterize how the resulting performance gap scales with the horizon. We ask when the performance gaps between open-loop, CE, and optimal control grow with the horizon.

We study this question in the scalar linear-quadratic setting with bilinear observations, where observation quality depends on the action. This structure creates a failure mode for CE: when the state estimate is small, CE takes a small action, resulting in weak observations and little new information. We identify an instance-dependent information strength parameter qq that captures how strongly information acquired under CE contributes to the growth rate of the state estimate, and hence to the informativeness of future observations. We show that the relative performance of open-loop, CE, and optimal control varies qualitatively across different ranges of qq. Our contributions are as follows.

  1. We establish four instance-dependent thresholds q1<q2<q3<q4q_1 < q_2 < q_3 < q_4 that separate different performance regimes. When q<q1q < q_1 no policy can achieve more than an O(1)O(1) advantage over open-loop control. When q<q3q < q_3, CE achieves at most an O(1)O(1) advantage over open-loop control. Conversely, when q>q4q > q_4, CE achieves an Ω(T)\Omega(T) advantage over open-loop control.

  1. Our main finding is that when q>q2q > q_2 optimal control has an Ω(T)\Omega(T) advantage over open-loop control. Consequently, when q2<q<q3q_2 < q < q_3, the performance gap between optimal control and CE control is Ω(T)\Omega(T). To establish this result, we construct a policy that occasionally deviates from CE to probe for information and show that when q>q2q > q_2 it achieves an Ω(T)\Omega(T) advantage over open-loop control.

Table Table 1 summarizes the established bounds.

RegimeThresholdRT(π⋆,πOL)R_T(\pi^\star,\pi^{OL})RT(πCE,πOL)R_T(\pi^{CE},\pi^{OL})
Low info.q<q1q < q_1O(1)O(1)O(1)O(1)
Separationq2<q<q3q_2 < q < q_3Ω(T)\Omega(T)O(1)O(1)
High info.q4<qq_4 < qΩ(T)\Omega(T)Ω(T)\Omega(T)

Table 1. RT(π,π′)R_T(\pi,\pi') refers to the regret of policy π′\pi' with respect to π\pi as the benchmark. πOL\pi^{OL}, πCE\pi^{CE}, and π⋆\pi^\star refer to the optimal OL, CE, and optimal policies, respectively.

Preliminaries

Notation. We denote the positive integers, integers, and nonnegative integers by N\mathbb{N}, Z\mathbb{Z}, and Z≥0\mathbb{Z}_{\ge0}, respectively. For T∈Z≥0T \in\mathbb{Z}_{\ge0}, let [T]:={0,1,…,T}[T] := \{0, 1, \ldots, T\}. For a set AA, let Δ(A)\Delta(A) denote the set of probability distributions over AA, and let 1{E}\mathbb{1}\{E\} denote the indicator of an event EE. For a matrix AA, tr⁡(A)\operatorname{tr}(A), ρ(A)\rho(A), and ∥A∥\lVert A\rVert denote its trace, spectral radius, and spectral norm, respectively, while ∥⋅∥2\lVert\cdot\rVert_2 denotes the Euclidean norm. For symmetric matrices AA and BB, we write A⪰BA \succeq B (resp. A≻BA \succ B) if A−BA-B is positive semidefinite (resp. positive definite). Finally, X=dYX \overset{d}{=} Y denotes equality in distribution.

General problem setting. We first introduce a general partially observable control setting to define the three policies being compared. A partially observable control problem is defined by (X,U,Y,f,g,c,μ,T)(\mathcal{X},\mathcal{U},\mathcal{Y},f,g,c,\mu,T), where X,U,Y\mathcal{X},\mathcal{U},\mathcal{Y} are the state, action, and observation spaces respectively, f:X×U→Δ(X)f:\mathcal{X}\times\mathcal{U}\to\Delta(\mathcal{X}) is the state transition kernel, g:X×U→Δ(Y)g:\mathcal{X}\times\mathcal{U}\to\Delta(\mathcal{Y}) is the observation kernel, c:X×U→Rc:\mathcal{X}\times\mathcal{U}\to\mathbb{R} is the stage cost, μ∈Δ(X)\mu\in\Delta(\mathcal{X}) is the initial state distribution, and TT is the horizon. Interaction is as follows. We start at initial state x0∼μ(⋅)x_0\sim\mu(\cdot), which is unobserved. Then at each time step t=0,…,Tt=0,\ldots,T, a controller takes action utu_t based on previous observations, incurs cost c(xt,ut)c(x_t,u_t), and obtains observation yt∼g(⋅∣xt,ut)y_t\sim g(\cdot\mid x_t,u_t). The state of the system transitions to xt+1∼f(⋅∣xt,ut)x_{t+1}\sim f(\cdot\mid x_t,u_t).

Policies. We define the history of observations available when choosing utu_t as

Ht:=(u0,y0,…,ut−1,yt−1)H_t := (u_0,y_0,\ldots,u_{t-1},y_{t-1})

with H0=∅H_0 = \emptyset. In particular, yty_t is observed only after utu_t has been chosen. Let Ht=(U×Y)t\mathcal{H}_t = (\mathcal{U} \times\mathcal{Y})^t denote the space of histories. Let Π\Pi denote the class of policies π={πt}t=0T\pi= \{\pi_t\}_{t=0}^T where each πt:Ht→U\pi_t : \mathcal{H}_t \to\mathcal{U} is measurable and ut=πt(Ht)u_t = \pi_t(H_t). We call a policy open-loop if its actions do not depend on the history [15]. Formally, we define the class of open-loop policies

ΠOL:={π∈Π:πt(H)=πt(H′), ∀H,H′∈Ht, t∈[T]}.\Pi^{OL} := \{\pi\in\Pi: \pi_t(H) = \pi_t(H'),\ \forall H,H' \in\mathcal{H}_t,\ t \in[T]\}.

Equivalently, open-loop policies commit to a deterministic action sequence before interaction begins. For a policy π\pi, let Eπ\mathbb{E}_{\pi} denote expectation with respect to the trajectory distribution induced by the initial distribution μ\mu, transition kernel ff, observation kernel gg, and actions selected according to π\pi.

Objectives. We define the expected cumulative cost of a policy π∈Π\pi\in\Pi as

JT(π)=Eπ[∑t=0Tc(xt,ut)].J_T(\pi) = \mathbb{E}_{\pi}\left[\sum_{t=0}^{T} c(x_t,u_t)\right].

We adopt the convention that a policy designer aims to minimize JTJ_T. For π,π′\pi,\pi' we define the regret of π′\pi' with respect to π\pi as

RT(π,π′)=JT(π′)−JT(π).R_T(\pi,\pi') = J_T(\pi') - J_T(\pi).

Alternatively, RTR_T can be considered the advantage of π\pi over π′\pi'.

State-action cost-to-go. In order to define CE we consider the corresponding fully observed problem where the state is known. For each tt, define the state-action cost-to-go function Q~t:X×U→R\widetilde{Q}_t : \mathcal{X} \times\mathcal{U} \to\mathbb{R} recursively by:

Q~T(x,u)=c(x,u)\widetilde{Q}_T(x,u) = c(x,u)

and for each t∈[T−1]t \in[T-1],

Q~t(x,u)=c(x,u)+Ex′∼f(⋅∣x,u)[min⁡u′∈UQ~t+1(x′,u′)].\widetilde{Q}_t(x,u) = c(x,u) + \mathbb{E}_{x' \sim f(\cdot\mid x,u)}\left[\min_{u' \in\mathcal{U}} \widetilde{Q}_{t+1}(x',u')\right].

Then,

arg⁡min⁡u∈U Q~t(x,u)\underset{u \in\mathcal{U}}{\arg\min}\ \widetilde{Q}_t(x,u)

denotes the set of optimal actions at time step tt and state xx in the fully observed problem. The CE policy will apply this fully observed decision rule to a state estimate.

State estimation. The final ingredient needed to define CE is the state estimate. Because the system is only partially observed, the controller generally does not know xtx_t when choosing utu_t and must instead estimate it from the history. We use the conditional mean

x^t:=E[xt∣Ht]\hat{x}_t := \mathbb{E}[x_t \mid H_t]

as the state estimate. More generally, CE control may be defined with an alternative state estimator when the conditional mean is unavailable or does not belong to the state space.

Benchmark policies. Now we define the benchmark policies that we consider in this paper.

  1. The optimal policy π⋆\pi^\star is defined as

π⋆∈arg⁡min⁡π∈ΠJT(π)\pi^\star\in\arg\min_{\pi\in\Pi} J_T(\pi)
  1. The certainty-equivalent (CE) policy πCE\pi^{CE} applies the optimal fully observed policy to the estimated state x^t\hat{x}_t and is defined as

References

  1. [1]Agarwal, N., Bullins, B., Hazan, E., Kakade, S., and Singh, K. (2019). Online control with adversarial disturbances. In International Conference on Machine Learning, pages 111–119. PMLR.arxiv.org/abs/1902.08721
  2. [2]Åström, K. J. (2012). Introduction to stochastic control theory. Courier Corporation.
  3. [3]Bar-Shalom, Y. and Tse, E. (1974). Dual effect, certainty equivalence, and separation in stochastic control. IEEE Transactions on Automatic Control, 19(5):494–500.DOI
  4. [4]Basu, S., Sen, R., Sanghavi, S., and Shakkottai, S. (2019). Blocking bandits. Advances in Neural Information Processing Systems, 32.arxiv.org/abs/1907.11975
  5. [5]Bubeck, S. and Cesa-Bianchi, N. (2012). Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends® in Machine Learning, 5(1):1–122.
  6. [6]Cao, D., Du, B., Lowitt, A., Choi, S., Dean, S., and Sattar, Y. (2026). Dual control of linear systems from bilinear observations with belief space model predictive control. arXiv preprint arXiv:2604.24663.arxiv.org/abs/2604.24663
  7. [7]Choi, S., Sattar, Y., Jedra, Y., Fazel, M., and Dean, S. (2026). Explore-then-commit for nonstationary linear bandits with latent dynamics. In Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, pages 2071–2079. PMLR.arxiv.org/abs/2510.16208
  8. [8]Garivier, A. and Kaufmann, E. (2016). Optimal best arm identification with fixed confidence. In Conference on Learning Theory, pages 998–1027. PMLR.
  9. [9]Goel, G. and Hassibi, B. (2020). Regret-optimal control in dynamic environments. arXiv preprint arXiv:2010.10473.arxiv.org/abs/2010.10473
  10. [10]Hager, W. W. and Horowitz, L. L. (1976). Convergence and stability properties of the discrete riccati operator equation and the associated optimal control and filtering problems. SIAM Journal on Control and Optimization, 14(2):295–312.DOI
  11. [11]Hwang, T., Choi, H., Ann, H., and Oh, M.-H. (2026). Block optimism for nonstationary bandits with latent linear dynamics. arXiv preprint arXiv:2610.00911.arxiv.org/abs/2610.00911
  12. [12]Kalman, R. E. (1960). A new approach to linear filtering and prediction problems. Journal of Basic Engineering, 82(1):35–45.DOI
  13. [13]Khosravi, K., Leme, R. P., Podimata, C., and Tsorvantzis, A. (2023). Preferences evolve and so should your bandits: bandits with evolving states for online platforms. arXiv preprint arXiv:2307.11655.arxiv.org/abs/2307.11655
  14. [14]Kleinberg, R. and Immorlica, N. (2018). Recharging bandits. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 309–319. IEEE.DOI
  15. [15]Kumar, P. R. and Varaiya, P. (2015). Stochastic systems: Estimation, identification, and adaptive control. SIAM.
  16. [16]Levine, N., Crammer, K., and Mannor, S. (2017). Rotting bandits. Advances in neural information processing systems, 30.arxiv.org/abs/1702.07274
  17. [17]Liu, Y., Kuang, X., and Van Roy, B. (2023). A definition of non-stationary bandits. arXiv preprint arXiv:2302.12202.arxiv.org/abs/2302.12202
  18. [18]Maynard-Zhang, L., Xiong, Z., Jamieson, K., and Fazel, M. (2026). On the complexity of best-arm identification in non-stationary linear bandits. In Proceedings of Thirty Ninth Conference on Learning Theory, pages 5021–5052. PMLR.
  19. [19]Ortner, R., Ryabko, D., Auer, P., and Munos, R. (2012). Regret bounds for restless markov bandits. In International conference on algorithmic learning theory, pages 214–228. Springer.
  20. [20]Pav, S. E. (2015). Moments of the log non-central chi-square distribution. arXiv preprint arXiv:1503.06266.DOI
  21. [21]Pike-Burke, C. and Grunewalder, S. (2019). Recovering bandits. Advances in Neural Information Processing Systems, 32.
  22. [22]Sattar, Y., Choi, S., Jedra, Y., Fazel, M., and Dean, S. (2025). Sub-optimality of the separation principle for quadratic control from bilinear observations. In 2025 IEEE 64th Conference on Decision and Control (CDC), pages 3862–3867. IEEE.arxiv.org/abs/2504.11555
  23. [23]Simchowitz, M., Singh, K., and Hazan, E. (2020). Improper learning for non-stochastic control. In Conference on Learning Theory, pages 3320–3436. PMLR.arxiv.org/abs/2001.09254
  24. [24]Tekin, C. and Liu, M. (2011). Adaptive learning of uncontrolled restless bandits with logarithmic regret. In 2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 983–990. IEEE.DOI
  25. [25]Tekin, C. and Liu, M. (2012). Online learning of rested and restless bandits. IEEE Transactions on Information Theory, 58(8):5588–5611.DOI
  26. [26]Witsenhausen, H. S. (1971). Separation of estimation and control for discrete time systems. Proceedings of the IEEE, 59(11):1557–1566.DOI

Paper details

vlnc:W_pyqpqkgv
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents