論文の概要: Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learning

• arxiv url: http://arxiv.org/abs/2110.00871v1
• Date: Sat, 2 Oct 2021 20:10:40 GMT
• ステータス: 処理完了
• システム内更新日: 2021-10-05 15:43:58.626066
• Title: Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learning
• Title（参考訳）: 文脈帯域と強化学習のためのフェルゴードトンプソンサンプリング
• Authors: Tong Zhang
• Abstract要約: 我々はトンプソンサンプリングの理論解析を行い、頻繁な後悔境界に焦点をあてる。 我々は、トンプソンサンプリングが新しい行動の探索に十分な積極的ではないことを示し、悲観的な状況下では準最適性をもたらすことを示した。 理論的枠組みは、標準的なトンプソンサンプリングに対するベイズ的後悔境界と、Feel-Good Thompson Samplingに対する頻繁な後悔境界を導出するのに利用できることを示す。
• 参考スコア（独自算出の注目度）: 17.860102738896096
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Thompson Sampling has been widely used for contextual bandit problems due to the flexibility of its modeling power. However, a general theory for this class of methods in the frequentist setting is still lacking. In this paper, we present a theoretical analysis of Thompson Sampling, with a focus on frequentist regret bounds. In this setting, we show that the standard Thompson Sampling is not aggressive enough in exploring new actions, leading to suboptimality in some pessimistic situations. A simple modification called Feel-Good Thompson Sampling, which favors high reward models more aggressively than the standard Thompson Sampling, is proposed to remedy this problem. We show that the theoretical framework can be used to derive Bayesian regret bounds for standard Thompson Sampling, and frequentist regret bounds for Feel-Good Thompson Sampling. It is shown that in both cases, we can reduce the bandit regret problem to online least squares regression estimation. For the frequentist analysis, the online least squares regression bound can be directly obtained using online aggregation techniques which have been well studied. The resulting bandit regret bound matches the minimax lower bound in the finite action case. Moreover, the analysis can be generalized to handle a class of linearly embeddable contextual bandit problems (which generalizes the popular linear contextual bandit model). The obtained result again matches the minimax lower bound. Finally we illustrate that the analysis can be extended to handle some MDP problems.
• Abstract（参考訳）: トンプソンサンプリングは、モデリング能力の柔軟性のため、文脈的バンディット問題に広く使われている。 しかし、頻繁な設定におけるこの種の手法の一般的な理論はいまだに欠落している。 本稿では,トンプソンサンプリングの理論的解析を行い,頻繁な後悔の限界に着目した。 この設定では、トンプソンサンプリングは新たな行動の探索に十分な積極的ではないことが示され、悲観的な状況では準最適となる。 標準的なトンプソンサンプリングよりも積極的に高い報酬モデルを好むFeel-Good Thompson Smplingと呼ばれる簡単な修正が提案されている。 理論的枠組みは、標準的なトンプソンサンプリングに対するベイズ的後悔境界と、Feel-Good Thompson Samplingに対する頻繁な後悔境界を導出するのに利用できることを示す。 いずれの場合においても,オンライン最小二乗回帰推定にバンディットの後悔問題を低減できることが示されている。 頻繁な分析のために、オンライン最小二乗回帰境界は、よく研究されているオンライン集約技術を用いて直接得られる。 結果として生じるバンディット後悔境界は、有限アクションの場合のミニマックス下限と一致する。 さらに、解析を一般化して、線形埋め込み可能なコンテキストバンディット問題(一般的な線形コンテキストバンディットモデルを一般化する)のクラスを扱うことができる。 得られた結果は、再びminimax下界と一致する。 最後に,MDP問題に対処するために解析を拡張可能であることを示す。

関連論文リスト

• Neural Dueling Bandits [58.90189511247936]
  ニューラルネットワークを用いて、予め選択した腕の好みフィードバックを用いて報酬関数を推定する。 次に、理論結果を二項フィードバックによる文脈的帯域幅問題に拡張し、それはそれ自体は自明な寄与ではない。
  論文  参考訳（メタデータ） (2024-07-24T09:23:22Z)
• Thompson Exploration with Best Challenger Rule in Best Arm Identification [66.33448474838342]
  本稿では,バンドイットフレームワークにおける固定信頼度最良腕識別問題について検討する。 我々は、トンプソンサンプリングと、ベストチャレンジャールールとして知られる計算効率の良いアプローチを組み合わせた新しいポリシーを提案する。
  論文  参考訳（メタデータ） (2023-10-01T01:37:02Z)
• Analysis of Thompson Sampling for Partially Observable Contextual Multi-Armed Bandits [1.8275108630751844]
  我々は、部分的に観測可能なコンテキスト多重武装バンディットのためのトンプソンサンプリングアルゴリズムを提案する。 提示された政策の後悔は、時間と武器の数に応じて対数的にスケールし、寸法と直線的にスケールすることを示す。
  論文  参考訳（メタデータ） (2021-10-23T08:51:49Z)
• A Unifying Theory of Thompson Sampling for Continuous Risk-Averse Bandits [91.3755431537592]
  本稿では,多腕バンディット問題に対するリスク-逆トンプソンサンプリングアルゴリズムの解析を統一する。 大規模偏差理論における収縮原理を用いることで、連続リスク汎関数に対する新しい濃度境界が証明される。 リスク関数の幅広いクラスと「ニセ」関数が連続性条件を満たすことを示す。
  論文  参考訳（メタデータ） (2021-08-25T17:09:01Z)
• On the Suboptimality of Thompson Sampling in High Dimensions [7.198362232890585]
  我々は、トンプソンサンプリングが半帯域の準最適であることを実証する。 トンプソンサンプリングは、高次元において非常に低性能であることを示す。
  論文  参考訳（メタデータ） (2021-02-10T15:44:43Z)
• Analysis and Design of Thompson Sampling for Stochastic Partial Monitoring [91.22679787578438]
  部分モニタリングのためのトンプソンサンプリングに基づく新しいアルゴリズムを提案する。 局所可観測性を持つ問題の線形化変種に対して,新たなアルゴリズムが対数問題依存の擬似回帰$mathrmO(log T)$を達成することを証明した。
  論文  参考訳（メタデータ） (2020-06-17T05:48:33Z)
• Latent Bandits Revisited [55.88616813182679]
  潜伏盗賊問題は、学習エージェントが未知の離散潜伏状態に条件付けられた腕の報酬分布を知知する問題である。 本稿では, 上位信頼境界(UCB)とトンプソンサンプリング(Thompson sample)の両方に基づいて, この設定のための一般的なアルゴリズムを提案する。 我々はアルゴリズムの統一的な理論的解析を行い、遅延状態の数がアクションよりも小さい場合、古典的なバンディットポリシーよりも後悔度が低い。
  論文  参考訳（メタデータ） (2020-06-15T19:24:02Z)
• Thompson Sampling for Linearly Constrained Bandits [18.477962150017095]
  我々はLinConTSについて述べる。LinConTSは、各ラウンドで報酬を得る確率に線形制約を課すバンディットのアルゴリズムである。 また,LinConTSでは,過度な制約違反と累積的制約違反はO(log T)で上限づけられていることを示す。
  論文  参考訳（メタデータ） (2020-04-20T13:06:35Z)
• MOTS: Minimax Optimal Thompson Sampling [89.2370817955411]
  トンプソンサンプリングがミニマックス下限の$Omega(sqrtKT)$と$K$の武器付きバンディット問題に一致するかどうかという未解決の問題のままである。 我々は,各タイミングで選択した腕のサンプリングインスタンスを適応的にクリップするMOTSと呼ばれるトンプソンサンプリングの変種を提案する。 我々は、この単純なトンプソンサンプリングの変種が、有限時間地平線に対して$O(sqrtKT)$のミニマックス最適後悔境界と、$T$が無限に近づくときのガウス報酬に対する最適後悔境界を達成することを証明した。
  論文  参考訳（メタデータ） (2020-03-03T21:24:39Z)
• On Thompson Sampling for Smoother-than-Lipschitz Bandits [6.929312022493406]
  我々はトンプソン・サンプリングの弱い条件下での連続的な武装バンディットに対する後悔に関する最初の境界を提供する。 我々の境界は、可溶性次元の分析によって実現される。 我々は、リプシッツ微分を持つ函数の類に対するユーラダー次元の新しい境界を導出する。
  論文  参考訳（メタデータ） (2020-01-08T00:46:13Z)

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

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