論文の概要: Batched Thompson Sampling

• arxiv url: http://arxiv.org/abs/2110.00202v1
• Date: Fri, 1 Oct 2021 04:08:45 GMT
• ステータス: 処理完了
• システム内更新日: 2021-10-04 14:31:55.366743
• Title: Batched Thompson Sampling
• Title（参考訳）: Batched Thompson サンプリング
• Authors: Cem Kalkanli and Ayfer Ozgur
• Abstract要約: マルチアームバンディットに対する新しいバッチ・トンプソン・サンプリング・ポリシーを導入する。 このポリシーは、$O(log(T))$と$O(sqrtTlog(T))$のミニマックス後悔の問題を同時に達成することを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce a novel anytime Batched Thompson sampling policy for multi-armed bandits where the agent observes the rewards of her actions and adjusts her policy only at the end of a small number of batches. We show that this policy simultaneously achieves a problem dependent regret of order $O(\log(T))$ and a minimax regret of order $O(\sqrt{T\log(T)})$ while the number of batches can be bounded by $O(\log(T))$ independent of the problem instance over a time horizon $T$. We also show that in expectation the number of batches used by our policy can be bounded by an instance dependent bound of order $O(\log\log(T))$. These results indicate that Thompson sampling maintains the same performance in this batched setting as in the case when instantaneous feedback is available after each action, while requiring minimal feedback. These results also indicate that Thompson sampling performs competitively with recently proposed algorithms tailored for the batched setting. These algorithms optimize the batch structure for a given time horizon $T$ and prioritize exploration in the beginning of the experiment to eliminate suboptimal actions. We show that Thompson sampling combined with an adaptive batching strategy can achieve a similar performance without knowing the time horizon $T$ of the problem and without having to carefully optimize the batch structure to achieve a target regret bound (i.e. problem dependent vs minimax regret) for a given $T$.
• Abstract（参考訳）: 我々は,複数腕のバンディットに対して,エージェントが自身の行動の報酬を観察し,少数のバッチの終了時にのみ方針を調整できる,新たなanytime batched thompson sampling policyを導入する。 我々は、このポリシーが同時に問題依存の後悔である、順序 $o(\log(t))$ と順序 $o(\sqrt{t\log(t)})$ の最小後悔を同時に達成することを示し、一方、バッチの数を時間軸 $t$ 上で問題インスタンスから独立して$o(\log(t))$ で制限できることを示す。 また、我々のポリシーで使用されるバッチの数は、オーダー$O(\log\log(T))$のインスタンス依存のバウンダリによってバウンド可能であることも示しています。 これらの結果から、トンプソンサンプリングは、各アクション後に即時フィードバックが利用できる場合と同様、最小限のフィードバックを必要としながら、バッチ環境で同じ性能を維持することが示唆された。 これらの結果は、トンプソンサンプリングが、最近提案されたバッチ設定に適したアルゴリズムと競合することを示す。 これらのアルゴリズムは、与えられた時間軸$t$のバッチ構造を最適化し、実験の最初に探索を優先し、副最適アクションを排除する。 我々は,トンプソンサンプリングと適応的バッチ処理戦略を組み合わせることで,時間的地平線を把握せず,また,与えられたT$に対して,目的の後悔境界(すなわち問題依存対ミニマックス後悔)を達成するために,バッチ構造を慎重に最適化する必要がないことを示す。

関連論文リスト

• Efficient and Adaptive Posterior Sampling Algorithms for Bandits [5.050520326139362]
  我々は,有界報酬を持つ帯域幅に対するトンプソンサンプリングに基づくアルゴリズムについて検討する。 本稿では2つのパラメータ化トンプソンサンプリングに基づくアルゴリズムを提案する。 両方のアルゴリズムが$O left(Klnalpha+1(T)/Delta right)$ regret bound, ここで$K$はアームの数、$T$は有限学習地平線、$Delta$はサブ最適アームを引っ張る際のラウンドパフォーマンス損失を表す。
  論文  参考訳（メタデータ） (2024-05-02T05:24:28Z)
• Provably Efficient High-Dimensional Bandit Learning with Batched Feedbacks [93.00280593719513]
  本稿では,オンラインインタラクションのT$ステップをバッチに分割したバッチフィードバックによる高次元マルチアームコンテキストバンドレットについて検討する。 具体的には、各バッチは以前のバッチに依存するポリシーに従ってデータを収集し、その報酬はバッチの最後にのみ明らかにする。 我々のアルゴリズムは,$mathcalO( log T)$ バッチで完全に逐次的に設定されたものに匹敵する後悔の限界を達成している。
  論文  参考訳（メタデータ） (2023-11-22T06:06:54Z)
• Instance-optimal PAC Algorithms for Contextual Bandits [20.176752818200438]
  この作業では、$(epsilon,delta)$-$textitPAC$設定における帯域幅の問題に焦点を当てます。 最良腕識別のための最小限の後悔最小化とインスタンス依存のPACを同時に行うアルゴリズムは存在しないことを示す。
  論文  参考訳（メタデータ） (2022-07-05T23:19:43Z)
• Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits [88.21288104408556]
  本研究では,指数関数族バンドイットに対するトンプソンサンプリング (TS) アルゴリズムの遺残について検討する。 最適な腕の過小評価を避けるために,新しいサンプリング分布を用いたトンプソンサンプリング(Expulli)を提案する。
  論文  参考訳（メタデータ） (2022-06-07T18:08:21Z)
• Asymptotic Performance of Thompson Sampling in the Batched Multi-Armed Bandits [0.0]
  我々は,トンプソンサンプリングがバッチで遅延フィードバックを受信しても,その性能を維持可能であることを示す。 同じ性能を維持しつつ,バッチ数を$Theta(log T)$に削減する適応型スキームを提案する。
  論文  参考訳（メタデータ） (2021-10-01T01:28:40Z)
• Parallelizing Thompson Sampling [38.13649699234982]
  我々は2つの標準オンライン意思決定問題に対してThompson Smplingフレームワークを導入する。 我々のポリシーは、O(log T)$のバッチクエリのみを実行しながら、完全にシーケンシャルなものと同じ(漸近的な)後悔境界を達成する。 また,動的バッチアロケーションが静的バッチアロケーションなどの自然なベースラインを劇的に上回ることを示す。
  論文  参考訳（メタデータ） (2021-06-02T18:51:57Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)
• Analysis and Design of Thompson Sampling for Stochastic Partial Monitoring [91.22679787578438]
  部分モニタリングのためのトンプソンサンプリングに基づく新しいアルゴリズムを提案する。 局所可観測性を持つ問題の線形化変種に対して,新たなアルゴリズムが対数問題依存の擬似回帰$mathrmO(log T)$を達成することを証明した。
  論文  参考訳（メタデータ） (2020-06-17T05:48:33Z)
• An Efficient Algorithm For Generalized Linear Bandit: Online Stochastic Gradient Descent and Thompson Sampling [83.48992319018147]
  プレイヤーが過去の観測結果に基づいて逐次意思決定を行い、累積報酬を最大化する文脈的帯域幅問題を考える。 この問題を解決する自然な方法は、ステップごとの時間とメモリの複雑さを一定に抑えるために、オンライン勾配降下(SGD)を適用することである。 本研究では,オンラインSGDが一般化線形帯域問題に適用可能であることを示す。 過去の情報を活用するためにシングルステップのSGD更新を利用するSGD-TSアルゴリズムは、全時間複雑度で$tildeO(sqrtT)$ regretを達成する。
  論文  参考訳（メタデータ） (2020-06-07T01:12:39Z)
• MOTS: Minimax Optimal Thompson Sampling [89.2370817955411]
  トンプソンサンプリングがミニマックス下限の$Omega(sqrtKT)$と$K$の武器付きバンディット問題に一致するかどうかという未解決の問題のままである。 我々は,各タイミングで選択した腕のサンプリングインスタンスを適応的にクリップするMOTSと呼ばれるトンプソンサンプリングの変種を提案する。 我々は、この単純なトンプソンサンプリングの変種が、有限時間地平線に対して$O(sqrtKT)$のミニマックス最適後悔境界と、$T$が無限に近づくときのガウス報酬に対する最適後悔境界を達成することを証明した。
  論文  参考訳（メタデータ） (2020-03-03T21:24:39Z)

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

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