論文の概要: On Thompson Sampling with Langevin Algorithms

• arxiv url: http://arxiv.org/abs/2002.10002v2
• Date: Thu, 18 Jun 2020 02:02:30 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-29 09:30:32.151581
• Title: On Thompson Sampling with Langevin Algorithms
• Title（参考訳）: ランゲヴィンアルゴリズムを用いたトンプソンサンプリングについて
• Authors: Eric Mazumdar, Aldo Pacchiano, Yi-an Ma, Peter L. Bartlett, Michael I. Jordan
• Abstract要約: 多武装バンディット問題に対するトンプソンサンプリングは理論と実践の両方において良好な性能を享受する。 計算上のかなりの制限に悩まされており、反復ごとに後続分布からのサンプルを必要とする。 本稿では,この問題に対処するために,トンプソンサンプリングに適した2つのマルコフ連鎖モンテカルロ法を提案する。
• 参考スコア（独自算出の注目度）: 106.78254564840844
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Thompson sampling for multi-armed bandit problems is known to enjoy favorable performance in both theory and practice. However, it suffers from a significant limitation computationally, arising from the need for samples from posterior distributions at every iteration. We propose two Markov Chain Monte Carlo (MCMC) methods tailored to Thompson sampling to address this issue. We construct quickly converging Langevin algorithms to generate approximate samples that have accuracy guarantees, and we leverage novel posterior concentration rates to analyze the regret of the resulting approximate Thompson sampling algorithm. Further, we specify the necessary hyperparameters for the MCMC procedure to guarantee optimal instance-dependent frequentist regret while having low computational complexity. In particular, our algorithms take advantage of both posterior concentration and a sample reuse mechanism to ensure that only a constant number of iterations and a constant amount of data is needed in each round. The resulting approximate Thompson sampling algorithm has logarithmic regret and its computational complexity does not scale with the time horizon of the algorithm.
• Abstract（参考訳）: マルチアームバンディット問題に対するトンプソンサンプリングは理論と実践の両方において良好な性能を享受することが知られている。 しかし、これは計算上のかなりの制限に悩まされ、各イテレーションで後続分布からのサンプルが必要なためである。 本稿では,この問題を解決するためにトンプソンサンプリングに適した2つのマルコフ連鎖モンテカルロ法を提案する。 我々は,精度保証のある近似サンプルを生成するために,迅速に収束するランゲヴィンアルゴリズムを構築し,新しい後部濃度率を利用して,得られた近似トンプソンサンプリングアルゴリズムの遺残を分析する。 さらに,MCMC手順に必要なハイパーパラメータを規定し,計算量が少なく,最適なインスタンス依存頻繁な後悔を保証する。 特に,本アルゴリズムでは,後方集中とサンプル再利用機構を併用することにより,ラウンド毎に一定数の反復と一定量のデータが必要となることを保証する。 その結果得られた近似トンプソンサンプリングアルゴリズムは対数的後悔を持ち、その計算複雑性はアルゴリズムの時間軸と一致しない。

関連論文リスト

• Accelerating Approximate Thompson Sampling with Underdamped Langevin Monte Carlo [7.968641076961955]
  本稿では,Langevin Monte Carlo を用いた近似トンプソンサンプリング手法を提案する。 標準スムーズ性および対数凹凸性条件に基づき,加速後濃度およびサンプリングについて検討した。 提案アルゴリズムは,高次元バンディット問題における合成実験により実験的に検証される。
  論文  参考訳（メタデータ） (2024-01-22T02:54:58Z)
• Making RL with Preference-based Feedback Efficient via Randomization [11.019088464664696]
  人間のフィードバックから学習する強化学習アルゴリズムは、統計複雑性、計算複雑性、クエリ複雑性の点で効率的である必要がある。 提案するアルゴリズムは, サンプル効率のよいアルゴリズム(すなわち, ほぼ最適ケースの後悔境界)と実行時間(すなわち, 関連するパラメータに関して計算複雑性が最悪の場合)を提案する。 結果をより一般的な非線形関数近似に拡張するために、トンプソンサンプリングのアイデアに触発されたモデルベースランダム化アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2023-10-23T04:19:35Z)
• An Asymptotically Optimal Algorithm for the Convex Hull Membership Problem [21.312152185262]
  純粋な探査環境における凸船体構成問題について検討する。 我々はThompson-CHMというアルゴリズムを初めて提案し、そのモジュラー設計は停止規則とサンプリング規則から構成される。
  論文  参考訳（メタデータ） (2023-02-03T23:41:53Z)
• Langevin Monte Carlo for Contextual Bandits [72.00524614312002]
  Langevin Monte Carlo Thompson Sampling (LMC-TS) が提案されている。 提案アルゴリズムは,文脈的帯域幅の特別な場合において,最高のトンプソンサンプリングアルゴリズムと同じサブ線形残差を達成できることを示す。
  論文  参考訳（メタデータ） (2022-06-22T17:58:23Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。 SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。 本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。 ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
  論文  参考訳（メタデータ） (2021-09-13T18:10:52Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Analysis and Design of Thompson Sampling for Stochastic Partial Monitoring [91.22679787578438]
  部分モニタリングのためのトンプソンサンプリングに基づく新しいアルゴリズムを提案する。 局所可観測性を持つ問題の線形化変種に対して,新たなアルゴリズムが対数問題依存の擬似回帰$mathrmO(log T)$を達成することを証明した。
  論文  参考訳（メタデータ） (2020-06-17T05:48:33Z)
• MOTS: Minimax Optimal Thompson Sampling [89.2370817955411]
  トンプソンサンプリングがミニマックス下限の$Omega(sqrtKT)$と$K$の武器付きバンディット問題に一致するかどうかという未解決の問題のままである。 我々は,各タイミングで選択した腕のサンプリングインスタンスを適応的にクリップするMOTSと呼ばれるトンプソンサンプリングの変種を提案する。 我々は、この単純なトンプソンサンプリングの変種が、有限時間地平線に対して$O(sqrtKT)$のミニマックス最適後悔境界と、$T$が無限に近づくときのガウス報酬に対する最適後悔境界を達成することを証明した。
  論文  参考訳（メタデータ） (2020-03-03T21:24:39Z)

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

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