論文の概要: Block Optimism for Nonstationary Bandits with Latent Linear Dynamics

• arxiv url: http://arxiv.org/abs/2610.00911v1
• Date: Thu, 01 Oct 2026 01:43:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-03 01:19:23.842994
• Title: Block Optimism for Nonstationary Bandits with Latent Linear Dynamics
• Title（参考訳）: 遅延線形ダイナミクスをもつ非定常帯域に対するブロック最適化
• Abstract要約: 潜在線形力学を用いた内因性非定常バンドイット問題について検討する。 適応的ブロックレベルの最適化により、このレートを改善できることが示される。 我々は、以前の$tildeO(T2/3)$保証よりも大幅に改善された$tildeO(sqrt T)$の遺言境界を証明した。
• 参考スコア（独自算出の注目度）: 33.79708176601716
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.
• Abstract（参考訳）: 本研究では,潜在線形力学を用いた内因性非定常確率的バンドイット問題について検討する。 報酬は現在の行動と潜伏状態において双線形であり、歴史に依存した報酬を誘導し、非自明な長期計画問題を引き起こす。 既存のExplore-then-commitアプローチは、潜在力学を均一に推定し、最適化されたオープンループアクションシーケンスにコミットすることで、$\tilde{O}(T^{2/3})$ regretを達成する。 適応的ブロックレベルの最適化により、このレートを改善できることが示される。 我々の重要なステップは循環近似であり、安定な力学の下では無限メモリの報酬プロセスが切り離され、オープンループベンチマークは有限メモリのブロックレベルプロキシを最適化することで近似することができる。 この削減を前提として,乱れた動的パラメータに対する信頼セットを維持し,楽観的にブロックを選択するUPBベースのブロックアルゴリズムを提案する。 我々は、前回の$\tilde{O}(T^{2/3})$よりも大幅に改善された$\tilde{O}(T^{2/3})$の残差を証明した。 我々の知る限り、これは双線型報酬観測とオープンループアクションシーケンスベンチマークを備えた潜在線形力学の帯域に対する、最初の$\tilde{O}(\sqrt T)$残念な保証である。

関連論文リスト

• A Unified Optimism-Agnostic Framework for Linear Bandits over Spherical Action Sets [3.7851234061033856]
  線形帯域は、決定変数に線形なノイズのある報酬を持つ逐次決定問題をモデル化する。 上位信頼境界(UCB)とトンプソンサンプリング(TS)の2つの顕著なアルゴリズムファミリーは、時間をかけて探索と搾取のバランスを取る。 UCB と TS の変種は推定および濃度特性を満足し、最適の後悔率を享受することを示した。
  論文  参考訳（メタデータ） (2026-09-26T02:10:59Z)
• A Perturbation Approach to Unconstrained Linear Bandits [48.45987210959519]
  我々は、制約のない帯域線形最適化(uBLO)の文脈で、Abernethy et al. (2008) の標準摂動に基づくアプローチを再考する。 制約のない環境では、バンド線形最適化(BLO)を標準オンライン線形最適化(OLO)問題に効果的に還元することを示す。
  論文  参考訳（メタデータ） (2026-03-30T09:17:46Z)
• Explore-then-Commit for Nonstationary Linear Bandits with Latent Dynamics [21.224078346005655]
  報酬が行動と潜伏状態の両方に依存する非定常バンドイット問題について検討する。 有限地平線$T$に対する探索列コミットアルゴリズムを提案する。 提案アルゴリズムは, $tildemathcalO(T2/3)$ regret を実現する。
  論文  参考訳（メタデータ） (2025-10-17T20:41:14Z)
• Optimistically Optimistic Exploration for Provably Efficient Infinite-Horizon Reinforcement and Imitation Learning [13.429541377715296]
  無限水平割引線形マルコフ決定過程において, 速度-最適後悔保証を実現するための計算効率のよいアルゴリズムを提案する。 正規化された近似的動的プログラミングスキームと組み合わせると、結果のアルゴリズムは、$tildemathcalO (sqrtd3 (1 - gamma)- 7 / 2 T)$, $T$ はサンプル遷移の総数、$gamma in (0,1)$ は割引係数、$d$ は特徴次元を後悔する。
  論文  参考訳（メタデータ） (2025-02-19T17:32:35Z)
• Non-stationary Delayed Online Convex Optimization: From Full-information to Bandit Setting [71.82716109461967]
  遅延勾配が利用できる全情報ケースに対して Mild-OGD というアルゴリズムを提案する。 ミルド-OGDのダイナミックな後悔は、順番の仮定の下で$O(sqrtbardT(P_T+1))$で自動的に束縛されることを示す。 Mild-OGDのバンディット版も開発し,損失値の遅れのみを考慮に入れた,より困難なケースについて検討した。
  論文  参考訳（メタデータ） (2023-05-20T07:54:07Z)
• Autoregressive Bandits [58.46584210388307]
  本稿では,オンライン学習環境であるAutoregressive Banditsを提案する。 報酬プロセスの軽微な仮定の下では、最適ポリシーを便利に計算できることが示される。 次に、新しい楽観的後悔最小化アルゴリズム、すなわちAutoRegressive Upper Confidence Bound (AR-UCB)を考案し、$widetildemathcalO left( frac(k+1)3/2sqrtnT (1-G)のサブ線形後悔を被る。
  論文  参考訳（メタデータ） (2022-12-12T21:37:36Z)
• Efficient Optimistic Exploration in Linear-Quadratic Regulators via Lagrangian Relaxation [107.06364966905821]
  線形2次レギュレータ(LQR)設定における探索・探索ジレンマについて検討した。 有限 MDP に対する楽観的アルゴリズムで用いられる拡張値反復アルゴリズムに着想を得て,Oulq の楽観的最適化を緩和することを提案する。 我々は、少なくとも$Obig(log (1/epsilon)big)$ Riccati方程式を解くことで、$epsilon$-OptimisticControllerを効率的に計算できることを示した。
  論文  参考訳（メタデータ） (2020-07-13T16:30:47Z)
• Optimistic Policy Optimization with Bandit Feedback [70.75568142146493]
  我々は,事前の報奨を後悔する$tilde O(sqrtS2 A H4 K)を定め,楽観的な信頼領域ポリシー最適化(TRPO)アルゴリズムを提案する。 我々の知る限り、この2つの結果は、未知の遷移と帯域幅フィードバックを持つポリシー最適化アルゴリズムにおいて得られた最初のサブ線形後悔境界である。
  論文  参考訳（メタデータ） (2020-02-19T15:41:18Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。