論文の概要: MOTS: Minimax Optimal Thompson Sampling

• arxiv url: http://arxiv.org/abs/2003.01803v3
• Date: Thu, 1 Oct 2020 06:12:11 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-26 22:35:31.138067
• Title: MOTS: Minimax Optimal Thompson Sampling
• Title（参考訳）: MOTS: Minimax Optimal Thompson サンプリング
• Authors: Tianyuan Jin, Pan Xu, Jieming Shi, Xiaokui Xiao, and Quanquan Gu
• Abstract要約: トンプソンサンプリングがミニマックス下限の$Omega(sqrtKT)$と$K$の武器付きバンディット問題に一致するかどうかという未解決の問題のままである。 我々は,各タイミングで選択した腕のサンプリングインスタンスを適応的にクリップするMOTSと呼ばれるトンプソンサンプリングの変種を提案する。 我々は、この単純なトンプソンサンプリングの変種が、有限時間地平線に対して$O(sqrtKT)$のミニマックス最適後悔境界と、$T$が無限に近づくときのガウス報酬に対する最適後悔境界を達成することを証明した。
• 参考スコア（独自算出の注目度）: 89.2370817955411
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Thompson sampling is one of the most widely used algorithms for many online decision problems, due to its simplicity in implementation and superior empirical performance over other state-of-the-art methods. Despite its popularity and empirical success, it has remained an open problem whether Thompson sampling can match the minimax lower bound $\Omega(\sqrt{KT})$ for $K$-armed bandit problems, where $T$ is the total time horizon. In this paper, we solve this long open problem by proposing a variant of Thompson sampling called MOTS that adaptively clips the sampling instance of the chosen arm at each time step. We prove that this simple variant of Thompson sampling achieves the minimax optimal regret bound $O(\sqrt{KT})$ for finite time horizon $T$, as well as the asymptotic optimal regret bound for Gaussian rewards when $T$ approaches infinity. To our knowledge, MOTS is the first Thompson sampling type algorithm that achieves the minimax optimality for multi-armed bandit problems.
• Abstract（参考訳）: トンプソンサンプリングは、実装の単純さと他の最先端手法よりも経験的性能が優れているため、多くのオンライン決定問題において最も広く使われているアルゴリズムの1つである。 その人気と実証的な成功にもかかわらず、トンプソンサンプリングが$k$-armed bandit問題のminimax下限$\omega(\sqrt{kt})$にマッチできるかは、まだ未解決のままである。 本稿では,選択したアームのサンプリングインスタンスを各ステップ毎に適応的にクリップするmotsと呼ばれるトンプソンサンプリングの変種を提案することにより,この長いオープン問題を解く。 この単純なトンプソンサンプリングの変種は、有限時間地平線に対して$O(\sqrt{KT})$のミニマックス最適リピートと、$T$が無限に近づくときのガウス報酬に対する漸近最適リピートを達成することを証明している。 我々の知る限り、MOTSはマルチアームバンディット問題に対する最小限の最適化を実現する最初のトンプソンサンプリング型アルゴリズムである。

関連論文リスト

• Optimal Exploration is no harder than Thompson Sampling [14.726673043806391]
  a pure exploration linear bandit problem to return $argmax_zin mathcalZ ztoptheta_ast with $xtoptheta_ast with $xin mathcalXsubset mathbbRd$。 この複雑さは、後続サンプリングとargmaxオラクルへのアクセスを必要とするだけであり、$mathcalZ$を列挙する必要がない、後悔の最小化のために人気で単純なトンプソンサンプリングと矛盾する。
  論文  参考訳（メタデータ） (2023-10-09T18:21:39Z)
• Thompson Exploration with Best Challenger Rule in Best Arm Identification [66.33448474838342]
  本稿では,バンドイットフレームワークにおける固定信頼度最良腕識別問題について検討する。 我々は、トンプソンサンプリングと、ベストチャレンジャールールとして知られる計算効率の良いアプローチを組み合わせた新しいポリシーを提案する。
  論文  参考訳（メタデータ） (2023-10-01T01:37:02Z)
• Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits [88.21288104408556]
  本研究では,指数関数族バンドイットに対するトンプソンサンプリング (TS) アルゴリズムの遺残について検討する。 最適な腕の過小評価を避けるために,新しいサンプリング分布を用いたトンプソンサンプリング(Expulli)を提案する。
  論文  参考訳（メタデータ） (2022-06-07T18:08:21Z)
• Maillard Sampling: Boltzmann Exploration Done Optimally [11.282341369957216]
  この論文は、$K$武装バンディット問題に対するランダム化アルゴリズムを示す。 メイラードサンプリング(MS)は、各アームを閉じた形で選択する確率を計算する。 最適性を失わずに$sqrtKTlogK$に制限された最小値を改善するMS$+$というMSの変種を提案する。
  論文  参考訳（メタデータ） (2021-11-05T06:50:22Z)
• Batched Thompson Sampling [0.0]
  マルチアームバンディットに対する新しいバッチ・トンプソン・サンプリング・ポリシーを導入する。 このポリシーは、$O(log(T))$と$O(sqrtTlog(T))$のミニマックス後悔の問題を同時に達成することを示す。
  論文  参考訳（メタデータ） (2021-10-01T04:08:45Z)
• Thompson Sampling for Unimodal Bandits [21.514495320038712]
  本稿では, 半順序の腕に対して期待される報酬が一様であるアンフンモダル・バンディットに対するトンプソンサンプリングアルゴリズムを提案する。 ガウスの報酬に対して、我々のアルゴリズムの後悔は$mathcalO(log T)$であり、標準的なトンプソンサンプリングアルゴリズムよりもはるかに優れている。
  論文  参考訳（メタデータ） (2021-06-15T14:40:34Z)
• 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)
• On Thompson Sampling with Langevin Algorithms [106.78254564840844]
  多武装バンディット問題に対するトンプソンサンプリングは理論と実践の両方において良好な性能を享受する。 計算上のかなりの制限に悩まされており、反復ごとに後続分布からのサンプルを必要とする。 本稿では,この問題に対処するために,トンプソンサンプリングに適した2つのマルコフ連鎖モンテカルロ法を提案する。
  論文  参考訳（メタデータ） (2020-02-23T22:35:29Z)

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

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