PaperlayerView exact revision on arXiv

Source-linked AI summary

Block Optimism for Nonstationary Bandits with Latent Linear Dynamics

Taehyun Hwang, Hyunjun Choi, Heesang Ann, Min-hwan Oh

arXiv:2610.00911v1stat.MLcs.LG

TL;DR

Actions change future latent states, creating history-dependent rewards and a difficult long-horizon planning problem; explore-then-commit leaves a suboptimal exploration–exploitation trade-off. The paper uses cyclic approximation and adaptive optimistic block learning to improve the previous regret guarantee for this model.

  • Problem

    Actions affect future latent states as well as immediate rewards, making rewards history-dependent; explore-then-commit separates exploration from reward maximization and later plan revision.

    Source: §1 · pp. 1–2

  • Method

    Under stable dynamics, cyclic approximation reduces the infinite-memory problem to stationary block-level learning, where an optimistic algorithm selects blocks using a finite-memory proxy.

    Source: §1 · p. 2, §3.1 · p. 5

  • Results

    The paper reports a regret bound significantly improving over the previous e O(T 2/3) explore-then-commit guarantee for the same model.

    Source: §1 · p. 2, §5 · p. 10

  • Takeaways & Limitations

    The paper presents the first such regret guarantee for latent linear-dynamics bandits with bilinear rewards and action-controlled latent states.

    Source: §5 · p. 10

    The theoretical analysis assumes an exact offline maximization oracle for block selection.

    Source: §3.2 · p. 7

Abstract

from arXiv · show

We study an endogenous nonstationary stochastic bandit problem with latent linear dynamics, where actions affect both immediate rewards and the future evolution of an unobserved latent state. Rewards are bilinear in the current action and latent state, inducing history-dependent rewards and a nontrivial long-horizon planning problem. The existing explore-then-commit approach achieves $\tilde{O}(T^{2/3})$ regret by uniformly exploring to estimate the latent dynamics and then committing to an optimized open-loop action sequence. We show that this rate can be improved via adaptive block-level optimism. Our key step is a cyclic approximation: under stable dynamics, the infinite-memory reward process can be truncated, and the open-loop benchmark can be approximated by optimizing a finite-memory block-level proxy. Building on this reduction, we propose a UCB-based block algorithm that maintains confidence sets for the truncated dynamics parameters and selects blocks optimistically. We prove a regret bound of order $\tilde{O}(\sqrt T)$, significantly improving over the previous $\tilde{O}(T^{2/3})$ guarantee for the same model. To the best of our knowledge, this is the first $\tilde{O}(\sqrt T)$ regret guarantee for latent linear-dynamics bandits with bilinear reward observations and an open-loop action-sequence benchmark.

1 Introduction

The paper replaces explore-then-commit with adaptive block-level optimism for latent linear-dynamics bandits, improving the regret guarantee from e O(T^2/3) to e O(sqrt T). Stable dynamics enable a finite-memory cyclic approximation that supports this block-level learning approach.

1 Introduction

  • The model addresses action-induced changes across related actions through a latent state, unlike exogenous nonstationarity models and arm-level temporal-effect models.The prior latent linear-dynamics formulation [11] creates a coupled learning-and-planning problem because actions affect future rewards and observations are scalar and temporally correlated.Source: §1 · p. 1
  • The algorithm achieves e O(sqrt T) regret, improving on the e O(T^2/3) explore-then-commit guarantee for the same model.The authors identify this as the first guarantee of this order for latent linear-dynamics bandits with bilinear reward observations.Source: §1 · p. 2
  • Under stable latent dynamics, geometric decay lets the infinite-memory reward process be truncated, and the open-loop benchmark approximated by a cyclic block sequence.This extends the cyclic approximation principle for finite-memory bandits [5] to the latent linear-dynamics setting.Source: §1 · p. 2
  • Block-level UCB maintains confidence sets for truncated dynamics parameters, selects blocks optimistically, and updates estimates after each block instead of using a long uniform-exploration phase.This interleaves exploration and exploitation, unlike the prior explore-then-commit approach [11].Source: §1 · p. 2

1.1 Related Work

  • Unlike finite-memory bandits, the latent-state reward process has infinite memory; unlike dynamical linear bandits, bilinear rewards require a finite-horizon open-loop action-sequence benchmark.The dynamical linear bandit benchmark reduces to the best constant action [29], whereas the closest latent linear-dynamics model uses bilinear rewards [11].Source: §1.1 · p. 3
  • Compared with online control and nonstochastic control, this problem maximizes bandit rewards from scalar bilinear observations against an open-loop sequence, not a feedback controller.Unrolling the bilinear rewards creates pairwise interactions between current and past actions, unlike standard LQR/LQG or nonstochastic-control formulations.Source: §1.1 · p. 3

2 Preliminaries

The problem is a stochastic bandit with an unobserved, action-controlled latent state and bilinear rewards. The paper defines open-loop regret and states compact-action, stability, and light-tailed-noise assumptions for its analysis.

Problem setup

  • At each round, the learner observes a scalar reward but not the latent state, while actions affect both the current bilinear reward and the future state.The unknown system matrices are A, B, and C, with process and reward noise.Source: §2 · p. 3
  • The benchmark is the best deterministic open-loop action sequence, and pseudo-regret compares its mean-reward functional with that of the policy.For adaptive policies, pseudo-regret need not equal actual expected regret because actions may correlate with past process noise; the paper bounds this adaptation gap for its block-committed algorithm.Source: §2 · pp. 3–4

Assumptions

  • The action set is compact and actions have norm at most one; latent dynamics satisfy exponential stability, so past actions and noises decay geometrically.The stated stability condition is ||A^h||2 <= Mρρ^h for some ρ in (0, 1).Source: §2 · p. 4
  • Reward and process noises satisfy conditional sub-Gaussian assumptions, supporting the paper's high-probability least-squares and self-normalized concentration analysis.The process and reward noises are conditionally independent given the interaction history.Source: §2 · p. 4

3 Main Results

Under stable latent dynamics, the authors approximate the open-loop problem with a finite-memory block proxy and optimize it using adaptive optimism. The resulting guarantee improves on explore-then-commit for the same model.

3.1 Cyclic Approximation

  • Exponential stability permits truncating the infinite-memory reward process; a warm-up segment and informative suffix yield a linear block proxy whose cyclic repetition approximates the open-loop benchmark.The approximation incurs error 2T∆m + 2TmRm/(m + L).Source: §3.1 · pp. 4–6

3.2 Algorithm: Block-OFUL

  • Block-OFUL treats each block as a composite linear-bandit action, selects blocks by an optimistic proxy-reward score, and updates its estimate after every block.Every block contributes to exploration and exploitation, avoiding ETC’s initial exploration phase followed by a fixed plan.Source: §3.2 · p. 6

3.3 Regret Bound

  • Theorem 1 improves the actual expected regret guarantee over ETC’s eO(T^2/3) guarantee for the same model.The algorithm updates its confidence set after each block and chooses the next block optimistically, rather than using a long initial uniform-exploration phase.Source: §3.3 · pp. 7–8

3.4 Regret Analysis

  • Confidence-set construction must account for pre-block process-noise tails correlated with adaptively selected blocks; stability and a uniform tail bound make valid optimism possible.The analysis combines this bound with blockwise self-normalized martingale concentration for current-block noise.Source: §3.4 · pp. 8–9

4 Experiments

In two synthetic instances, Block-OFUL accumulates reward faster than ETC across both tested stability levels. The experiments compare a slower-decaying and a faster-decaying latent dynamic.

4 Experiments

  • Both instances use action dimension p = 3 and action set U = {−1, +1}p; they vary latent-dynamics persistence, and Gaussian reward and process noises have variance proxy 0.01.The transition matrices have spectral radii 0.95 and 0.3. ETC uses H = 120 in both instances; Block-OFUL uses (m, L) = (8, 36) at ρ(A) = 0.95 and (2, 24) at ρ(A) = 0.3.Source: §4 · p. 10
  • Across both stability regimes, Block-OFUL accumulates reward faster than ETC, while the random baseline remains close to zero.Figure 1 reports cumulative reward over the interaction horizon.Source: §4 · p. 10, Figure 1 · p. 10
  • For ρ(A) = 0.95, the performance gap between Block-OFUL and ETC grows over time; for ρ(A) = 0.3, Block-OFUL stays higher through most of the horizon.Both methods show more stable reward accumulation in the faster-decaying instance.Source: §4 · p. 10

5 Conclusion

The paper reduces the stable latent-dynamics problem to stationary block-level learning and applies optimism to learn truncated Markov parameters while selecting blocks. It establishes a tilde-O(sqrt T) regret guarantee, improving on the prior explore-then-commit guarantee.

5 Conclusion

  • Cyclic approximation reduces the infinite-memory problem under stable latent dynamics to stationary block-level learning, where an optimistic algorithm learns truncated Markov parameters while selecting blocks.Actions affect both immediate rewards and the future latent state.Source: §5 · p. 10
  • Regret tilde-O(sqrt T) significantly improves the previous tilde-O(T^(2/3)) explore-then-commit guarantee for the same model and, to our knowledge, is the first of that order for latent linear-dynamics bandits with bilinear rewards and action-controlled latent states.Source: §5 · p. 10
  • Future work includes efficient oracles for block-UCB maximization, adaptive or feedback benchmarks, and parameter-free methods for unknown stability and memory scales.Source: §5 · p. 10

A Proof of Proposition 1

The proof establishes geometric decay of finite-memory truncation error under the stated assumptions, then compares the original sequence with a cyclic block sequence to bound the approximation gap.

A Proof of Proposition 1

  • Under the stability condition, the finite-memory truncation error decays geometrically.The proposition invokes Assumptions 1 and 2 and uses Δm for the truncation error.Source: A Proof of Proposition 1 · p. 14
  • The proof partitions an arbitrary action sequence into blocks of length m + L and separates each block's informative suffix from its prefix.For suffix positions j ≥ m + 1, the truncated reward depends only on the previous m actions within that block.Source: A Proof of Proposition 1 · p. 14
  • It bounds the original and cyclic sequences using their suffix and prefix contributions, then transfers the comparison from truncated rewards to original rewards.The proof applies the same decomposition to the cyclic sequence and uses the finite-memory truncation-error lemma for the transfer.Source: A Proof of Proposition 1 · pp. 13, 15

B.1 Proof of Lemma 2

The lemma decomposes informative rewards within length-(m + L) blocks after unrolling the latent dynamics, identifying the recent within-block action history and the remaining terms.

B.1 Proof of Lemma 2

  • Each block Uτ has length m + L, with informative rewards rτ,j indexed by positions j = m + 1 through m + L.Source: §B.1 · p. 15
  • The proof unrolls the latent dynamics and reindexes the resulting sums to express their contributions at each time.It defines Gh = CA^hB and sets us and ws to zero for s ≤ 0.Source: §B.1 · p. 16
  • For informative position j, the previous m actions lie in the same block; the remaining terms are collected into ετ,j, ητ,j, and ζτ,j.Source: §B.1 · p. 16

B.2 Proof of Lemma 3

The proof writes informative rewards as a blockwise regression and controls estimation error through block-level noise concentration and a high-probability bias bound.

B.2 Proof of Lemma 3

  • The proof forms a block feature matrix and reward vector, then uses the reward decomposition to control the estimation error.It separates current-block noise from bias before deriving the confidence bound.Source: §B.2 · pp. 16–17
  • Current-block noise is conditionally sub-Gaussian at the block level, enabling a self-normalized concentration bound for the joint regression update.The L informative rewards enter jointly through Φτ rather than as independent scalar observations.Source: §B.2 · pp. 17–18
  • The action-tail bias and process-noise tail are bounded together with high probability across informative positions in every block.Lemma 7 bounds |ητ,j + ζτ,j| by the stated threshold; on the resulting event, the proof controls the bias term.Source: §B.2 · p. 18
  • Combining the concentration and bias controls yields the confidence radius chosen in Lemma 1.The proof also bounds accumulated feature norms using the elliptical-potential argument.Source: §B.2 · pp. 18–19

B.3 Proof of Lemma 1

The proof bounds Algorithm 1’s pseudo-regret by controlling statistical uncertainty, block-boundary error, and finite-memory truncation, then relates proxy regret to cumulative regret.

B.3 Proof of Lemma 1

  • The proof establishes a high-probability pseudo-regret bound for Algorithm 1 that simplifies when p and the stability parameter ρ are fixed.The bound is stated under Assumptions 1–3; its displayed rate is suppressed in the supplied passage.Source: §B.3 · pp. 19, 22
  • The within-block uncertainty is controlled using sequential Gram matrices and an elliptical-potential bound.The proof also controls the discrepancy between pre-block and within-block Gram matrices.Source: §B.3 · pp. 20–21
  • Finite-memory truncation and block decomposition relate the proxy regret to cumulative regret for Algorithm 1’s action sequence.The displayed relation includes a block-boundary contribution involving m, L, and Rm.Source: §B.3 · p. 21
  • Under Assumption 1, the lifted-feature quantity Sm is uniformly bounded in m by a problem-dependent constant.This bound is used when simplifying the regret bound for a specific choice of m and L.Source: §B.3 · p. 21
  • The proof combines the truncation error, block-boundary error, and statistical term to obtain the pseudo-regret bound.The confidence-radius and statistical terms are bounded separately before they are combined.Source: §B.3 · p. 22

B.4 Proof of Theorem 1

Theorem 1 converts Algorithm 1’s pseudo-regret guarantee into an actual expected-regret guarantee by bounding the adaptation gap for block-committed policies.

B.4 Proof of Theorem 1

  • Theorem 1 states an actual expected-regret guarantee for Algorithm 1 under the assumptions of Lemma 1.Its proof takes δ = T^-2 and substitutes the specified m, L, and λ choices.Source: §B.4 · pp. 22–23
  • For block-committed policies, pseudo-regret and actual expected regret differ by a boundary-noise term of order T/(m + L).The policy selects the whole block before its noises are revealed and does not adapt within the block.Source: §B.4 · p. 23
  • The adaptation-gap term is dominated by the leading block-boundary and statistical terms, up to logarithmic and problem-dependent factors.The theorem proof combines the blockwise adaptation-gap bound with the pseudo-regret guarantee.Source: §B.4 · p. 23

B.5.1 Proof of Lemma 5

  • The Lemma 5 proof bounds current-block noise by combining reward-noise and process-noise contributions under the block history.The selected block actions are fixed given the preceding history before current-block noise is revealed.Source: §B.5.1 · p. 24

B.5.2 Proof of Lemma 6

The supplied appendix material gives concentration and bias arguments, auxiliary inequalities, and experimental implementation details for Block-OFUL.

B.5.2 Proof of Lemma 6

  • A mixture-supermartingale argument yields a self-normalized concentration bound for the blockwise martingale sum.The proof uses the conditional sub-Gaussianity of Φτᵀv and Ville’s inequality.Source: §B.5.2 · pp. 24–25

B.5.3 Proof of Lemma 7

  • The bias proof handles adaptively selected actions by bounding a vector-valued process-noise tail rather than assuming the selected-action tail is centered.It uses a net and a union bound to obtain a high-probability bound.Source: §B.5.3 · pp. 26–27

B.5.4 Proof of Lemma 8

  • The adaptation-gap proof separates within-block process noise, whose conditional expectation is zero, from contributions generated before the block.It uses the martingale-difference property to control process-noise contributions across time indices.Source: §B.5.4 · pp. 28–29

C Auxiliary Lemmas

  • The auxiliary lemmas supply concentration and matrix inequalities used in the regret analysis, including self-normalized and Gram-matrix bounds.The appendix cites related results for the determinant-trace and Gram-matrix update inequalities.Source: C Auxiliary Lemmas · p. 29

D Experimental Details

D.1 Implementation of Block-OFUL

  • Block-OFUL restricts actions to hypercube vertices and uses multi-start local search because exhaustive block maximization is computationally prohibitive.Restarts sample blocks uniformly, apply improving single-coordinate sign flips, and retain the locally optimized block with the largest UCB objective.Source: §D.1 · p. 30

D.2 Additional Experiments

In delayed latent-dynamics environments, Block-OFUL achieves higher cumulative reward than ETC and random, with a larger advantage under longer delays and more persistent effects. The experiments vary delay and stability by changing latent block count and decay factor.

Environment

  • The delayed environment injects each action into the first latent block, propagates it sequentially with decay, and makes its effect reward-relevant only at the final block.Increasing D delays the effect, while increasing ρ makes it decay more slowly.Source: §D.2 · p. 30
  • Experiments use T = 1000, p = 2, D ∈{3, 6}, and ρ ∈{0.3, 0.95}, with Gaussian reward and process noise.The latent state has D blocks of dimension p, and the action set is U = {−1, +1}p.Source: §D.2 · p. 30

Results

  • Block-OFUL consistently achieves higher cumulative reward than ETC and the random baseline, with a larger advantage at larger D and ρ close to one.In that regime, useful reward information arrives later and past actions persist longer; Block-OFUL continues updating block decisions from observed rewards, unlike ETC's initial-estimate commitment.Source: Figure 2 · p. 30, §D.2 · p. 31

Related papers

Loading 2610.00911v1…