論文の概要: Optimal Batched Linear Bandits

• arxiv url: http://arxiv.org/abs/2406.04137v1
• Date: Thu, 6 Jun 2024 14:57:52 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-07 14:30:04.828712
• Title: Optimal Batched Linear Bandits
• Title（参考訳）: 最適バッチリニアバンド
• Authors: Xuanfei Ren, Tianyuan Jin, Pan Xu,
• Abstract要約: 本稿では,探索・推定・探索の枠組みを取り入れたバッチ線形バンドイト問題に対するE$4$アルゴリズムを提案する。 探索速度の適切な選択により、E$4$は、$O(loglog T)$バッチのみで有限時間ミニマックス最適後悔を達成する。 探索レートの別の選択で、E$4$は、少なくとも$O(log T)$バッチを必要とするインスタンス依存の後悔境界を達成することを示す。
• 参考スコア（独自算出の注目度）: 9.795531604467406
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce the E$^4$ algorithm for the batched linear bandit problem, incorporating an Explore-Estimate-Eliminate-Exploit framework. With a proper choice of exploration rate, we prove E$^4$ achieves the finite-time minimax optimal regret with only $O(\log\log T)$ batches, and the asymptotically optimal regret with only $3$ batches as $T\rightarrow\infty$, where $T$ is the time horizon. We further prove a lower bound on the batch complexity of linear contextual bandits showing that any asymptotically optimal algorithm must require at least $3$ batches in expectation as $T\rightarrow\infty$, which indicates E$^4$ achieves the asymptotic optimality in regret and batch complexity simultaneously. To the best of our knowledge, E$^4$ is the first algorithm for linear bandits that simultaneously achieves the minimax and asymptotic optimality in regret with the corresponding optimal batch complexities. In addition, we show that with another choice of exploration rate E$^4$ achieves an instance-dependent regret bound requiring at most $O(\log T)$ batches, and maintains the minimax optimality and asymptotic optimality. We conduct thorough experiments to evaluate our algorithm on randomly generated instances and the challenging \textit{End of Optimism} instances \citep{lattimore2017end} which were shown to be hard to learn for optimism based algorithms. Empirical results show that E$^4$ consistently outperforms baseline algorithms with respect to regret minimization, batch complexity, and computational efficiency.
• Abstract（参考訳）: 本稿では,探索・推定・消去・探索の枠組みを取り入れたバッチ線形バンドイット問題に対するE$^4$アルゴリズムを提案する。 探索レートの適切な選択により、E$^4$は、O(\log\log T)$バッチのみで有限時間ミニマックス最適後悔を達成し、漸近的に最適な後悔は、$T\rightarrow\infty$としてわずか$3$のバッチでしか達成しない。 さらに、任意の漸近的最適アルゴリズムは、少なくとも$T\rightarrow\infty$として3$のバッチを必要とすることを示し、E$^4$は後悔とバッチの複雑さを同時に漸近的最適性を達成することを示す。 我々の知る限り、E$^4$は、対応する最適バッチ複素量に後悔してミニマックスと漸近最適性を同時に達成する線形バンディットの最初のアルゴリズムである。 さらに、探索レートの別の選択により、E$^4$は、最大$O(\log T)$バッチを必要とするインスタンス依存の後悔境界を達成し、極小最適性と漸近最適性を維持することを示す。 我々は、ランダムに生成されたインスタンス上でアルゴリズムを評価するための徹底的な実験を行い、最適化に基づくアルゴリズムの学習が困難であることが判明した、挑戦的な \textit{End of Optimism} インスタンス \citep{lattimore2017end} について検討した。 実験結果によると、E$^4$は、後悔の最小化、バッチの複雑さ、計算効率に関して、ベースラインアルゴリズムを一貫して上回っている。

関連論文リスト

• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization [37.300102993926046]
  リプシッツの目的の滑らかな点も凸点も生成しない点の複雑さについて検討する。 私たちの分析は単純だが強力だ。 Goldstein-subdifferential set, これは最近の進歩を可能にする。 非滑らかな非最適化
  論文  参考訳（メタデータ） (2023-07-10T11:56:04Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary Dueling Bandits [27.279654173896372]
  我々は,非定常的あるいは時間的に異なる選好の下で,$K$のDueling Banditsにおける空力的後悔の最小化問題について検討した。 これは、エージェントが各ラウンドで一対のアイテムを選択し、このペアに対する相対的な二項のウィンロスフィードバックのみを観察するオンライン学習設定である。
  論文  参考訳（メタデータ） (2021-11-06T16:46:55Z)
• Almost Optimal Batch-Regret Tradeoff for Batch Linear Contextual Bandits [45.43968161616453]
  バッチ線形文脈帯域に対する最適バッチ-regretトレードオフについて検討する。 時間的地平線が成長するにつれて2相表現を特徴とする後悔の保証を証明します。 また, 動的上界に依存した新しい行列不等式濃度を証明した。
  論文  参考訳（メタデータ） (2021-10-15T12:32:33Z)
• Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
  有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。 O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。 さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
  論文  参考訳（メタデータ） (2021-10-15T00:54:04Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
  現在の実用的なBOアルゴリズムは、$mathcalO(fraclogNsqrtN)$から$mathcalO(e-sqrtN)$まで、$N$は評価の数である。 本稿では,boと木に基づく楽観的楽観化の概念を絡み合うことにより,無音環境における後悔を改善できる可能性について検討する。 次数$mathcal O(N-sqrt)で指数的再帰を達成できる最初の実践的手法であるBOOアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-10T13:07:44Z)

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

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