論文の概要: Parallelizing Thompson Sampling

• arxiv url: http://arxiv.org/abs/2106.01420v1
• Date: Wed, 2 Jun 2021 18:51:57 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-05 06:16:22.524884
• Title: Parallelizing Thompson Sampling
• Title（参考訳）: 並列化トンプソンサンプリング
• Authors: Amin Karbasi, Vahab Mirrokni, Mohammad Shadravan
• Abstract要約: 我々は2つの標準オンライン意思決定問題に対してThompson Smplingフレームワークを導入する。 我々のポリシーは、O(log T)$のバッチクエリのみを実行しながら、完全にシーケンシャルなものと同じ(漸近的な)後悔境界を達成する。 また,動的バッチアロケーションが静的バッチアロケーションなどの自然なベースラインを劇的に上回ることを示す。
• 参考スコア（独自算出の注目度）: 38.13649699234982
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: How can we make use of information parallelism in online decision making problems while efficiently balancing the exploration-exploitation trade-off? In this paper, we introduce a batch Thompson Sampling framework for two canonical online decision making problems, namely, stochastic multi-arm bandit and linear contextual bandit with finitely many arms. Over a time horizon $T$, our \textit{batch} Thompson Sampling policy achieves the same (asymptotic) regret bound of a fully sequential one while carrying out only $O(\log T)$ batch queries. To achieve this exponential reduction, i.e., reducing the number of interactions from $T$ to $O(\log T)$, our batch policy dynamically determines the duration of each batch in order to balance the exploration-exploitation trade-off. We also demonstrate experimentally that dynamic batch allocation dramatically outperforms natural baselines such as static batch allocations.
• Abstract（参考訳）: 探索と探索のトレードオフを効率的にバランスしながら、オンライン意思決定問題において情報並列性をどのように活用できるか? 本稿では,2つの正準オンライン意思決定問題,すなわち,有限個のアームを持つ確率的多腕バンディットと線形文脈バンディットに対するバッチトンプソンサンプリングフレームワークを提案する。 時間軸の$T$、我々の \textit{batch} Thompson Sampling ポリシは、完全にシーケンシャルなものと同じ(漸近的な)後悔境界を達成すると同時に、$O(\log T)$バッチクエリのみを実行します。 この指数関数的縮小、すなわち相互作用の数を$t$から$o(\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)
• Langevin Thompson Sampling with Logarithmic Communication: Bandits and Reinforcement Learning [34.4255062106615]
  トンプソンサンプリング(TS)は、使用が容易で、経験的性能に訴えるため、シーケンシャルな意思決定に広く用いられている。 バッチ化された$textitLangevin Thompson Sampling$アルゴリズムを提案する。 アルゴリズムは計算効率が高く,MABでは$mathcalO(log T)$,RLでは$mathcalO(sqrtT)$と同じオーダー最適後悔保証を維持している。
  論文  参考訳（メタデータ） (2023-06-15T01:16:29Z)
• Batched Thompson Sampling [0.0]
  マルチアームバンディットに対する新しいバッチ・トンプソン・サンプリング・ポリシーを導入する。 このポリシーは、$O(log(T))$と$O(sqrtTlog(T))$のミニマックス後悔の問題を同時に達成することを示す。
  論文  参考訳（メタデータ） (2021-10-01T04:08:45Z)
• Asymptotic Performance of Thompson Sampling in the Batched Multi-Armed Bandits [0.0]
  我々は,トンプソンサンプリングがバッチで遅延フィードバックを受信しても,その性能を維持可能であることを示す。 同じ性能を維持しつつ,バッチ数を$Theta(log T)$に削減する適応型スキームを提案する。
  論文  参考訳（メタデータ） (2021-10-01T01:28:40Z)
• Markov Decision Process modeled with Bandits for Sequential Decision Making in Linear-flow [73.1896399783641]
  会員/加入者の獲得と保持では、複数のページを連続してマーケティングコンテンツを推奨する必要がある。 遷移確率行列をモデル化するためにBandits を用いた MDP としてこの問題を定式化することを提案する。 提案したMDPのBanditsアルゴリズムは,$epsilon$-greedyと$epsilon$-greedy,$epsilon$,IndependentBandits,InteractionBanditsでQ-learningを上回っている。
  論文  参考訳（メタデータ） (2021-07-01T03:54:36Z)
• Batched Neural Bandits [107.5072688105936]
  BatchNeuralUCBはニューラルネットワークと楽観性を組み合わせ、探索と探索のトレードオフに対処する。 BatchNeuralUCBは、完全なシーケンシャルバージョンと同じ後悔を達成しつつ、ポリシー更新の数を大幅に減らしています。
  論文  参考訳（メタデータ） (2021-02-25T17:36:44Z)
• 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)

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

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