PaperlayerView exact revision on arXiv

Source-linked AI summary

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

arXiv:2610.33412v1cs.LGcs.SYeess.SY

TL;DR

The paper asks when certainty-equivalent control's suboptimality in partially observed systems with action-dependent observations creates a horizon-growing performance gap. It compares optimal, CE, and open-loop control in a linear-quadratic system with bilinear observations, identifying regimes by information strength q. For intermediate q, probing achieves a linear advantage over open-loop control that CE does not attain.

  • Problem

    The horizon scaling of the performance gap from CE suboptimality in action-dependent observation control is not characterized.

    Source: §1 · p. 2

  • Method

    The paper compares optimal, CE, and open-loop policies in a scalar linear-quadratic system with bilinear observations and characterizes regimes using information strength q.

    Source: §1 · pp. 2–3

  • Results

    For q2 < q < q3, optimal control gains Ω(T) over open-loop control while CE gains only O(1), yielding an Ω(T) gap between optimal and CE control.

    Source: §1 · p. 3

  • Takeaways & Limitations

    In the scalar setting, feedback may offer only a bounded advantage, CE may achieve a linear advantage, or active probing may achieve a linear advantage CE misses.

    Source: §3.1 · p. 6, §5 · p. 13

    The results in Section 4 concern only the scalar setting, where p = n = 1.

    Source: §4 · p. 8

Abstract

from arXiv · show

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 $\Omega(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 $\Omega(T)$ advantage over OL control while CE only achieves an $O(1)$ advantage, establishing an $\Omega(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.

1 Introduction

The introduction asks when feedback and active information gathering yield horizon-growing gains in partially observed control, where actions affect both system performance and future observations. It identifies information-strength regimes in which optimal control, certainty-equivalent control, and open-loop control have distinct performance gaps.

1 Introduction

  • Across sequential decision problems, benchmarks range from fixed actions and open-loop sequences to closed-loop or time-varying policies, so adaptation's value depends on problem structure.The introduction also asks when fixed sampling suffices and when adapting to observations provides an advantage.Source: §1 · p. 2
  • The paper asks how the horizon-scale gaps among open-loop, CE, and optimal control depend on action-dependent observations, since prior work showed CE can be suboptimal without characterizing that gap.Actions can affect both immediate performance and future information; this dual effect distinguishes the setting from classical LQG, where observations are action-independent and separation applies (Witsenhausen, 1971; ˚Astr¨om, 2012).Source: §1 · pp. 1–2
  • In the scalar linear-quadratic setting with bilinear observations, q measures how strongly information acquired under CE grows the state estimate and informs future observations.When the estimate is small, CE takes a small action, yielding weak observations and little new information.Source: §1 · pp. 2–3
  • Four thresholds q1 < q2 < q3 < q4 distinguish regimes: below q1 no policy gains more than O(1) over open-loop, while CE gains O(1) below q3 and Ω(T) above q4..Source: §1 · p. 3
  • For q2 < q < q3, a probing policy gives optimal control an Ω(T) advantage over open-loop control while CE gains only O(1), creating an Ω(T) optimal-versus-CE gap.The policy occasionally departs from CE to gather information.Source: §1 · p. 3

2 Preliminaries

The preliminaries formalize partially observed control as sequential interaction in which actions depend on observation history. They define open-loop and certainty-equivalent benchmarks and introduce the state estimate used by CE.

2 Preliminaries

  • A partially observed control problem specifies state, action, and observation spaces, transition and observation kernels, stage cost, initial-state distribution, and horizon; actions precede observations and state transitions.The initial state is unobserved, and each action incurs cost before the observation and next state arrive.Source: §2 · p. 3
  • A policy maps the available observation history to an action; an open-loop policy ignores that history and commits to an action sequence before interaction.The current observation is received only after the action has been chosen.Source: §2 · p. 4
  • The analysis defines expected cumulative cost and regret between policies, with regret also interpreted as one policy's advantage over another.The optimal open-loop policy serves as a reference for measuring the advantage of feedback policies.Source: §2 · p. 4

Benchmark policies.

  • CE applies the fully observed optimal decision rule to a state estimate; the paper uses the conditional mean of the state given history as that estimate.An alternative estimator may be used when the conditional mean is unavailable or outside the state space.Source: §2 · p. 4, Benchmark policies · p. 5

3 Linear-Gaussian Control With Bilinear Observation

The paper studies linear-quadratic control with bilinear observations, where actions affect both the state and future information. It compares open-loop, certainty-equivalent, and optimal control, and identifies performance regimes tied to information strength.

3 Linear-Gaussian Control With Bilinear Observation

  • The section introduces the setting, summarizes the performance regimes, and explains their underlying mechanisms.It also presents the bilinear-observation model, filtering, and CE and open-loop policies.Source: §3 · p. 5

3.1 Overview of the Main Results

  • The bilinear-observation model realizes all three regimes: optimal control and CE can have bounded or linear advantages over open-loop, and CE can miss a linear advantage.In the latter case, optimal control has an Ω(T) advantage while CE has an O(1) advantage.Source: §3.1 · pp. 5–6

3.2 Model and Kalman Filtering

  • The model is a linear-quadratic Gaussian control problem with bilinear, input-dependent observations.The Kalman-filter variant updates both its gain and covariance based on the input.Source: §3.2 · p. 6

3.3 Benchmark Policies

  • CE and open-loop use the same fully observed gains, applying them respectively to the observation-based state estimate and the deterministic mean prediction.The optimal policy must balance control against information gathering because actions affect future estimation uncertainty.Source: §3.3 · p. 7

3.4 Information Strength q

  • The instance-dependent parameter q measures information-feedback strength under CE and helps characterize when its advantage over open-loop is bounded or linear.Near a zero estimate and open-loop covariance, q also contributes to the local growth rate of the CE estimate’s second moment.Source: §3.4 · p. 8

4 Results

The results distinguish bounded from linear feedback advantages as information strength varies. A probing policy can outperform open-loop where CE’s advantage remains bounded, while CE has a linear advantage at sufficiently high information strength.

4.1 Regret decomposition

  • The regret decomposition separates a penalty for deviating from CE from the weighted reduction in next-step estimation uncertainty, capturing the cost–information tradeoff.The open-loop policy is the reference because it is optimal among policies that do not use observations.Source: §4.1 · pp. 8–9

4.2 Bounded Optimal-Control Advantage

  • When q < q1, no policy can improve on open-loop by more than a horizon-independent constant.In this regime, the weighted reduction in estimation uncertainty is dominated by state-and-action cost; sufficiently large measurement noise is one example.Source: §4.2 · p. 9

4.3 Bounded CE Advantage

  • When q < q3, CE’s advantage over open-loop is bounded because its estimate and the associated regret contributions decay geometrically under the stated condition.As the estimate decays, CE gradually loses the feedback that gave it an advantage.Source: §4.3 · p. 10

4.4 Linear CE Advantage

  • Under Proposition 3’s sufficient condition, CE spends a positive fraction of the horizon outside beliefs with a small estimate and near-open-loop uncertainty, yielding a linear advantage over open-loop.The high-information theorem gives a sufficient condition q > q4 for CE’s linear advantage, assuming μx ≠ 0 and D ≠ 0.Source: §4.4 · pp. 10–11

4.5 Probing Policy

  • The probing policy takes spaced exploratory actions when the estimate and retained uncertainty are small, and otherwise uses the CE action.Its purpose is to establish a linear advantage over open-loop in a range where CE’s advantage remains bounded.Source: §4.5 · p. 11
  • Around q2, probing begins to outperform open-loop, whereas CE’s advantage begins around q4; for small q probing’s information benefits do not offset its cost, and for large q CE and probing perform similarly.The figure normalizes advantages by T, so values bounded away from zero are consistent with linear advantage and values near zero with bounded advantage.Source: Figure 1 · p. 12

5 Conclusion

The conclusion identifies bounded and linear feedback-advantage regimes in the scalar bilinear-observation setting. It points to extending the theory beyond scalar systems, refining probing, and studying online learning of unknown dynamics or observation models.

5 Conclusion

  • In the scalar setting, information strength separates regimes where feedback has only bounded advantage, CE has linear advantage, or probing achieves linear advantage that CE does not realize.The conclusion names extensions beyond scalar systems, policy refinement, and adaptive online learning as future directions.Source: §5 · p. 13

A Dynamic programming and Policies

  • The appendix derives the Riccati recursion from the fully observed Bellman equation, obtains CE by substituting the conditional mean, and derives the open-loop policy from the deterministic mean trajectory.It also proves filtering results for the evolution of the belief state.Source: A Dynamic programming and Policies · p. 15

A.1 Riccati Recursion and Certainty-Equivalent Control

  • The finite-horizon Riccati recursion yields the CE action by applying the fully observed minimizing action to the conditional state mean.The stationary gain defines closed-loop dynamics through D = A + BK.Source: §A.1 · pp. 16–17

A.2 Optimal Open-loop Control

  • Open-loop optimization reduces to a deterministic linear-quadratic problem for the mean trajectory because the covariance contribution is independent of the action sequence.CE and open-loop use the same gain but apply it to different quantities: the conditional estimate versus the deterministic mean.Source: §A.2 · pp. 17–18

A.3 Riccati Equation Tools

  • The Riccati tools establish convergence of the finite-horizon matrix quantities toward stationary values as the horizon remaining grows.The appendix also relates Γt to the difference between Gt and Pt.Source: §A.3 · p. 18

A.4 Proof of Theorem 1

Under the stability assumption, the proof establishes a linear advantage of certainty-equivalent control over open-loop control. The appendix also notes that a similar result can hold for unstable systems under stabilizability and detectability assumptions.

A.4 Proof of Theorem 1

  • R_T(πCE, πOL) = Ω(T) under the proof's stated conditions.The proof assumes ρ(A) < 1; the stability assumption keeps open-loop covariance bounded.Source: §A.4 · pp. 20–21
  • The stability restriction is for clear comparison; under stabilizability and detectability, a similar result can hold for unstable systems.The text says unstable systems can exhibit a faster-growing advantage over open-loop control.Source: §A.4 · p. 21

Proof of Lemma 1

The lemma proof characterizes the normalized observation innovations and the resulting estimate recursion under certainty-equivalent control. The section then uses these filtering results in a regret decomposition relative to open-loop control.

Proof of Lemma 1

  • The normalized innovations Z_t are independent standard Gaussians, with each Z_t independent of the history F_t.The conditional distribution does not depend on F_t.Source: Proof of Lemma 1 · pp. 22–23
  • The estimate evolves as x̂_{t+1} = M_t x̂_t, with M_t conditionally distributed as D_t + q_t Z for independent standard Gaussian Z.The distribution statement is conditional on F_t.Source: Proof of Lemma 1 · p. 23

C Regret decomposition

  • The regret decomposition uses V_t = P_t x̂_t^2 + G_tΣ_t to separate a policy-independent cumulative cost from accumulated terms r_t.Under open-loop control, the accumulated r_t terms have zero expectation; covariance and uncertainty reductions yield the same total weighted benefit.Source: C Regret decomposition · p. 24

C.1 Proof of Proposition 1

The section develops regret decompositions relative to open-loop control and uses them to bound the advantages of feedback. When q < q1, no policy can improve on open-loop control by more than a horizon-independent constant.

C.1 Proof of Proposition 1

  • The proof of Proposition 1 uses a telescoping sum of conditional costs and an auxiliary value quantity V_t to express regret through accumulated terms r_t.For open-loop control, the expected accumulated r_t equals zero.Source: §C.1 · pp. 25–26

C.2 Alternate Regret Decomposition

  • The alternate decomposition shows regret accumulates linearly if either immediate covariance reduction b_t or retained information d_t stays bounded away from zero.This gives flexibility in deriving lower bounds.Source: §C.2 · pp. 26–27

C.3 Lemmas

  • The covariance update and estimate-variance recursion relate information gain F(Σ_t,u_t) to changes in the variance of the state estimate.The displayed identity is F(Σ_t,u_t) = Var(x̂_{t+1}) − A^2Var(x̂_t).Source: §C.3 · p. 28

D Bounded Optimal-Control Advantage

  • When q < q1, even the optimal policy improves on open-loop control by at most a constant independent of the horizon.The bound follows from a telescoping regret upper bound.Source: D Bounded Optimal-Control Advantage · p. 29

D.1 Proof of Theorem 3

The paper bounds the advantage of all policies over open-loop control for small q, and separately bounds certainty-equivalent control's advantage for q < q3. The certainty-equivalent bound follows from decay in the estimated state’s second moment.

D.1 Proof of Theorem 3

  • When q < q1, the regret of any policy over open-loop control is bounded by a constant independent of the horizon and policy.The proof obtains this bound by telescoping.Source: §D.2 · p. 29, §D.1 · p. 29

E Bounded CE Advantage

  • For q < q3, certainty-equivalent control achieves only a bounded advantage over open-loop control.The estimate’s second moment decays geometrically away from the horizon, making the regret sum convergent.Source: E Bounded CE Advantage · p. 30

E.1 Proof of Proposition 2

The E.1 proof analyzes a function under q < q3, while the F-section proof establishes linear CE advantage over open-loop control for q > q4. The latter derives this advantage from instability of a region where the estimate and covariance deviation are small.

F Linear CE Advantage

  • Under πCE, the region where the squared state estimate and covariance deviation are both small is unstable.The proof measures growth of the multiplicative state-estimate recursion on a logarithmic scale.Source: F Linear CE Advantage · p. 32
  • The drift argument shows the belief spends a linear expected number of steps outside that region, where either the estimate or covariance deviation yields a linear advantage over open-loop.The drift is positive inside the region under condition (4.8) and bounded below everywhere; as δ and ε approach zero, the condition converges to D2 + q > 2eγE.Source: F Linear CE Advantage · p. 32

F.1 Proof of Theorem 4

The proof establishes a linear CE advantage over open-loop for q > q4 and uses a probing policy to establish an optimal-control advantage for q > q2. Its lemmas support the drift and probe-block arguments behind these results.

F.1 Proof of Theorem 4

  • When q > q4, πCE achieves RT(πCE, πOL) = Ω(T), as the proof of Theorem 4 instantiates Proposition 3.The construction uses δ and ε independent of T, with µx ≠ 0 and D ≠ 0.Source: §F.1 · p. 33

F.2 Proof of Proposition 3

  • The result establishes that RT (πCE, πOL) = Ω(T), a linear-in-horizon lower bound for the comparison between πCE and πOL.Source: §F.2 · p. 34

F.3 Lemmas

  • The lemmas bound logarithmic growth and establish conditions that force the CE belief to leave the region where both the estimate and covariance deviation are small.These support the drift argument used to show CE's linear advantage.Source: §F.3 · pp. 34, 36, 37, 38

G Probing Policy

  • For q > q2, the probing policy achieves a linear advantage over open-loop, and its proof analyzes each probe together with the following L − 1 CE steps as a block.The probe cost is immediate, while its information benefit accrues through subsequent CE actions; the proof shows each block pays off in expectation.Source: G Probing Policy · p. 39

G.1 Proof of Theorem 5

  • Since the optimal policy can do no worse than the probing policy, the probing result implies an Ω(T) optimal-control advantage over open-loop when q > q2.The proof also invokes Proposition 2 for the other stated result, without specifying it in these passages.Source: §G.1 · p. 40

G.2 Proof of Proposition 4

  • The threshold comparison in this proof concludes that q1 < q2.Source: §G.2 · p. 40

G.3 Proof of Proposition 5

The proof establishes that probing yields a linear advantage over open-loop when q > q2, using positive expected payoff from probe blocks and advantages on intervening steps. The numerical illustration reports the predicted bounded-versus-linear regret patterns across q regimes.

G.4 Proof of Proposition 6

  • The threshold comparison concludes q1 < q2 by equating two expressions for K2N and solving for KS.Source: §G.4 · pp. 42–43

G.5 Lemmas

  • When q > q2, a finite block length can be chosen so that the probing block pays off; continuity extends the result from steady-state blocks to blocks starting near steady state.The proof then uses positive expected payoff per block together with advantages at steps outside Mδ.Source: §G.5 · pp. 45–47

G.3 Proof of Proposition 5

  • For q > q2, the selected probing-policy parameters make the expected payoff of each probe block positive, yielding RT(πP, πOL) = Ω(T).The parameters are chosen independently of T.Source: §G.3 · p. 41, §G.5 · p. 47

H.1 Regime visualization

  • At T = 800, the numerical sweep reports no significant CE or probing improvement for small q, bounded CE advantage and linear probing advantage for intermediate q, and linear advantages for both at large q.For q = 0.5, CE advantage remains bounded while probing advantage grows linearly; for q = 4, both grow linearly. Experiments use 2000 independent Monte Carlo trajectories per policy, with 95% normal confidence intervals.Source: §H.1 · p. 49

H.2 Multivariate dynamical system

In the multivariate example, probing gains a linear advantage over open-loop before CE as q increases, while CE eventually approaches probing at large q. The multivariate q is a convenient information-strength measure, and the scalar theoretical thresholds need not extend to this setting.

H.2 Multivariate dynamical system

  • The multivariate test uses p=n=3, with identity matrices for B, C, Q, R, and process-noise covariance, and S=0.Source: §H.2 · p. 50
  • Here q is a convenient information-strength measure, but the scalar theoretical thresholds q1–q4 need not extend to the multivariate setting.Source: §H.2 · p. 50
  • When the Eq. (4.10) probing conditions hold, πP takes the action K_t x̂_t + a·1_3, using the previous section’s probe parameters.The parameters are a=0.25, δ=0.03, L=5, and tP=20.Source: §H.2 · p. 50
  • As q increases, probing gains a linear advantage over open-loop before CE does; at large q, CE also gains a linear advantage and approaches probing.Figure 8 compares normalized advantages over open-loop and probing over CE.Source: §H.2 · p. 50, Figure 8 · p. 51

Nomenclature

  • Policy notation distinguishes the optimal, CE, open-loop, and probing policies; R_T(π,π′) is the cost advantage J_T(π′)−J_T(π).Source: Nomenclature · p. 52
  • Riccati and open-loop notation includes feedback gains, cost-to-go coefficients, variance-reduction weights, and the optimal open-loop state mean.Source: Nomenclature · p. 52
  • The notation defines q as information strength, q1–q4 as sufficient-regime thresholds, and γ as the CE second-moment contraction factor.Source: Nomenclature · p. 52
  • Probe notation covers probe size and block length, the probing region and timing, and expected payoff over a probe block.Source: Nomenclature · pp. 52–53

Related papers

Loading 2610.33412v1…