論文の概要: Asymptotic Performance of Thompson Sampling in the Batched Multi-Armed Bandits

• arxiv url: http://arxiv.org/abs/2110.00158v1
• Date: Fri, 1 Oct 2021 01:28:40 GMT
• ステータス: 処理完了
• システム内更新日: 2021-10-04 14:32:18.696522
• Title: Asymptotic Performance of Thompson Sampling in the Batched Multi-Armed Bandits
• Title（参考訳）: Batched Multi-Armed Banditsにおけるトンプソンサンプリングの漸近性
• Authors: Cem Kalkanli and Ayfer Ozgur
• Abstract要約: 我々は,トンプソンサンプリングがバッチで遅延フィードバックを受信しても,その性能を維持可能であることを示す。 同じ性能を維持しつつ,バッチ数を$Theta(log T)$に削減する適応型スキームを提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the asymptotic performance of the Thompson sampling algorithm in the batched multi-armed bandit setting where the time horizon $T$ is divided into batches, and the agent is not able to observe the rewards of her actions until the end of each batch. We show that in this batched setting, Thompson sampling achieves the same asymptotic performance as in the case where instantaneous feedback is available after each action, provided that the batch sizes increase subexponentially. This result implies that Thompson sampling can maintain its performance even if it receives delayed feedback in $\omega(\log T)$ batches. We further propose an adaptive batching scheme that reduces the number of batches to $\Theta(\log T)$ while maintaining the same performance. Although the batched multi-armed bandit setting has been considered in several recent works, previous results rely on tailored algorithms for the batched setting, which optimize the batch structure and prioritize exploration in the beginning of the experiment to eliminate suboptimal actions. We show that Thompson sampling, on the other hand, is able to achieve a similar asymptotic performance in the batched setting without any modifications.
• Abstract（参考訳）: 我々は,トンプソンサンプリングアルゴリズムにおいて,時間軸のT$をバッチに分割し,各バッチの終了までその動作の報奨を観察できないような,バッチ化されたマルチアームバンディット設定における漸近的性能について検討した。 このバッチ化環境では、トンプソンサンプリングは、各アクション後に即時フィードバックが利用できる場合と同様の漸近的性能を達成し、バッチサイズが指数関数的に増加することを示す。 この結果は、トンプソンサンプリングが$\omega(\log t)$バッチで遅延フィードバックを受信しても、そのパフォーマンスを維持することができることを示唆している。 さらに,同じ性能を維持しながら,バッチ数を$\theta(\log t)$に削減する適応バッチ方式を提案する。 バッチ化されたマルチアームのバンディット設定は、近年のいくつかの研究で検討されているが、以前の結果は、バッチ構造を最適化し、実験開始時の探索を優先してサブオプティカルアクションを排除するバッチ設定のための調整されたアルゴリズムに依存している。 一方、トンプソンサンプリングは、バッチ設定で同様の漸近的性能を、何の変更もせずに達成できることが示されている。

関連論文リスト

• Finite-Time Frequentist Regret Bounds of Multi-Agent Thompson Sampling on Sparse Hypergraphs [11.024467775280193]
  マルチエージェントマルチアーム・バンドイット(MAMAB)問題について検討し,$m$エージェントを$rho$オーバーラップするグループに分解する。 そこで本稿では,MATS の効率的な変種として$epsilon$-exploring Multi-Agent Thompson Sampling (epsilon$-MATS) アルゴリズムを提案する。 我々は、$epsilon$-MATSが、時間地平線と局所アームサイズの両方においてサブ線形である最悪の頻繁な後悔境界を達成することを証明した。
  論文  参考訳（メタデータ） (2023-12-24T21:41:01Z)
• Provably Efficient High-Dimensional Bandit Learning with Batched Feedbacks [93.00280593719513]
  本稿では,オンラインインタラクションのT$ステップをバッチに分割したバッチフィードバックによる高次元マルチアームコンテキストバンドレットについて検討する。 具体的には、各バッチは以前のバッチに依存するポリシーに従ってデータを収集し、その報酬はバッチの最後にのみ明らかにする。 我々のアルゴリズムは,$mathcalO( log T)$ バッチで完全に逐次的に設定されたものに匹敵する後悔の限界を達成している。
  論文  参考訳（メタデータ） (2023-11-22T06:06:54Z)
• Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits [88.21288104408556]
  本研究では,指数関数族バンドイットに対するトンプソンサンプリング (TS) アルゴリズムの遺残について検討する。 最適な腕の過小評価を避けるために,新しいサンプリング分布を用いたトンプソンサンプリング(Expulli)を提案する。
  論文  参考訳（メタデータ） (2022-06-07T18:08:21Z)
• Batched Thompson Sampling [0.0]
  マルチアームバンディットに対する新しいバッチ・トンプソン・サンプリング・ポリシーを導入する。 このポリシーは、$O(log(T))$と$O(sqrtTlog(T))$のミニマックス後悔の問題を同時に達成することを示す。
  論文  参考訳（メタデータ） (2021-10-01T04:08:45Z)
• Parallelizing Thompson Sampling [38.13649699234982]
  我々は2つの標準オンライン意思決定問題に対してThompson Smplingフレームワークを導入する。 我々のポリシーは、O(log T)$のバッチクエリのみを実行しながら、完全にシーケンシャルなものと同じ(漸近的な)後悔境界を達成する。 また,動的バッチアロケーションが静的バッチアロケーションなどの自然なベースラインを劇的に上回ることを示す。
  論文  参考訳（メタデータ） (2021-06-02T18:51:57Z)
• Asymptotic Convergence of Thompson Sampling [0.0]
  トンプソンサンプリングは、様々なオンライン学習タスクにおいて効果的なポリシーであることが示されている。 我々は、準線形ベイズ的後悔を仮定して、トンプソンサンプリングの収束結果を証明した。 この結果はトンプソンサンプリングに固有のマーチンゲール構造に依存している。
  論文  参考訳（メタデータ） (2020-11-08T07:36:49Z)
• 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)
• On Thompson Sampling with Langevin Algorithms [106.78254564840844]
  多武装バンディット問題に対するトンプソンサンプリングは理論と実践の両方において良好な性能を享受する。 計算上のかなりの制限に悩まされており、反復ごとに後続分布からのサンプルを必要とする。 本稿では,この問題に対処するために,トンプソンサンプリングに適した2つのマルコフ連鎖モンテカルロ法を提案する。
  論文  参考訳（メタデータ） (2020-02-23T22:35:29Z)

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

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