論文の概要: Explore-then-Commit for Nonstationary Linear Bandits with Latent Dynamics

• arxiv url: http://arxiv.org/abs/2510.16208v1
• Date: Fri, 17 Oct 2025 20:41:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-25 00:56:38.898357
• Title: Explore-then-Commit for Nonstationary Linear Bandits with Latent Dynamics
• Title（参考訳）: 潜時ダイナミクスを用いた非定常線形帯域探索
• Authors: Sunmook Choi, Yahya Sattar, Yassir Jedra, Maryam Fazel, Sarah Dean,
• Abstract要約: 報酬が行動と潜伏状態の両方に依存する非定常バンドイット問題について検討する。 有限地平線$T$に対する探索列コミットアルゴリズムを提案する。 提案アルゴリズムは, $tildemathcalO(T2/3)$ regret を実現する。
• 参考スコア（独自算出の注目度）: 21.224078346005655
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study a nonstationary bandit problem where rewards depend on both actions and latent states, the latter governed by unknown linear dynamics. Crucially, the state dynamics also depend on the actions, resulting in tension between short-term and long-term rewards. We propose an explore-then-commit algorithm for a finite horizon $T$. During the exploration phase, random Rademacher actions enable estimation of the Markov parameters of the linear dynamics, which characterize the action-reward relationship. In the commit phase, the algorithm uses the estimated parameters to design an optimized action sequence for long-term reward. Our proposed algorithm achieves $\tilde{\mathcal{O}}(T^{2/3})$ regret. Our analysis handles two key challenges: learning from temporally correlated rewards, and designing action sequences with optimal long-term reward. We address the first challenge by providing near-optimal sample complexity and error bounds for system identification using bilinear rewards. We address the second challenge by proving an equivalence with indefinite quadratic optimization over a hypercube, a known NP-hard problem. We provide a sub-optimality guarantee for this problem, enabling our regret upper bound. Lastly, we propose a semidefinite relaxation with Goemans-Williamson rounding as a practical approach.
• Abstract（参考訳）: 我々は、報酬が行動と潜伏状態の両方に依存し、後者は未知の線形力学によって支配される非定常帯域問題を研究する。 重要なことに、状態のダイナミクスは行動にも依存し、短期と長期の報酬の間に緊張をもたらす。 有限地平線$T$に対する探索列コミットアルゴリズムを提案する。 探索段階では、ランダムなラデマッハ動作により、リニアダイナミクスのマルコフパラメータの推定が可能となり、アクション-リワード関係が特徴づけられる。 コミットフェーズでは、アルゴリズムは推定パラメータを使用して、長期的な報酬のために最適化されたアクションシーケンスを設計する。 提案アルゴリズムは, $\tilde{\mathcal{O}}(T^{2/3})$ regret を実現する。 我々の分析は、時間的に相関した報酬から学習することと、最適な長期報酬でアクションシーケンスを設計することの2つの主要な課題に対処する。 両線形報酬を用いたシステム識別において、ほぼ最適サンプルの複雑さとエラー境界を提供することで、最初の課題に対処する。 2つ目の課題は、既知のNPハード問題であるハイパーキューブ上の不定2次最適化と等価性を証明することである。 我々はこの問題に対する準最適保証を提供し、後悔の上限を許容する。 最後に,Goemans-Williamsonラウンドリングによる半有限緩和を実践的アプローチとして提案する。

関連論文リスト

• 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)
• Bridging Discrete and Backpropagation: Straight-Through and Beyond [62.46558842476455]
  本稿では,離散潜在変数の生成に関わるパラメータの勾配を近似する新しい手法を提案する。 本稿では,Hunの手法とODEを解くための2次数値法を統合することで,2次精度を実現するReinMaxを提案する。
  論文  参考訳（メタデータ） (2023-04-17T20:59:49Z)
• Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPs [60.40452803295326]
  線形マルコフ決定過程(MDP)を学習するための新たな報酬なしアルゴリズムを提案する。 我々のアルゴリズムの核心は、探索駆動の擬似回帰を用いた不確実性重み付き値目標回帰である。 我々のアルゴリズムは$tilde O(d2varepsilon-2)$ episodesを探索するだけで、$varepsilon$-optimal policyを見つけることができる。
  論文  参考訳（メタデータ） (2023-03-17T17:53:28Z)
• Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time Guarantees [56.848265937921354]
  逆強化学習(IRL)は報酬関数と関連する最適ポリシーを回復することを目的としている。 IRLの多くのアルゴリズムは本質的にネスト構造を持つ。 我々は、報酬推定精度を損なわないIRLのための新しいシングルループアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-10-04T17:13:45Z)
• Break your Bandit Routine with LSD Rewards: a Last Switch Dependent Analysis of Satiation and Seasonality [6.146046338698175]
  そこで本研究では,腕が最後に動作を切り替えて以降の時間経過によって,腕の期待される報酬が完全に決定される,新たな非定常バンディット問題を導入する。 我々のモデルは、遅延依存報酬の概念を一般化し、報酬関数に関するほとんどの仮定を緩和する。 我々はアルゴリズムを証明し、最適な非定常ポリシーに関してその後悔を証明した。
  論文  参考訳（メタデータ） (2021-10-22T14:53:13Z)
• Anti-Concentrated Confidence Bonuses for Scalable Exploration [57.91943847134011]
  固有の報酬は、探検と探検のトレードオフを扱う上で中心的な役割を果たす。 楕円ボーナスを効率的に近似するためのエンファンティ集中型信頼境界を導入する。 我々は,Atariベンチマーク上での現代固有の報酬と競合する,深層強化学習のための実用的な変種を開発する。
  論文  参考訳（メタデータ） (2021-10-21T15:25:15Z)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  マルコフ決定過程における純粋探索問題について検討する。 エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
  論文  参考訳（メタデータ） (2021-06-05T09:16:28Z)

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

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