論文の概要: Only Pay for What Is Uncertain: Variance-Adaptive Thompson Sampling

• arxiv url: http://arxiv.org/abs/2303.09033v1
• Date: Thu, 16 Mar 2023 02:07:29 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-17 17:13:32.006217
• Title: Only Pay for What Is Uncertain: Variance-Adaptive Thompson Sampling
• Title（参考訳）: 不確実性のみを支払う - 分散適応型トンプソンサンプリング
• Authors: Aadirupa Saha and Branislav Kveton
• Abstract要約: ほとんどのバンディットアルゴリズムは、報酬の分散または上限が知られていると仮定する。 分散過大評価は通常安全かつ健全であるが、後悔を増す。 このことは、分散対応の頻繁なアルゴリズムに関する先行研究を動機付けている。
• 参考スコア（独自算出の注目度）: 30.99407659584871
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Most bandit algorithms assume that the reward variance or its upper bound is known. While variance overestimation is usually safe and sound, it increases regret. On the other hand, an underestimated variance may lead to linear regret due to committing early to a suboptimal arm. This motivated prior works on variance-aware frequentist algorithms. We lay foundations for the Bayesian setting. In particular, we study multi-armed bandits with known and \emph{unknown heterogeneous reward variances}, and develop Thompson sampling algorithms for both and bound their Bayes regret. Our regret bounds decrease with lower reward variances, which make learning easier. The bound for unknown reward variances captures the effect of the prior on learning reward variances and is the first of its kind. Our experiments show the superiority of variance-aware Bayesian algorithms and also highlight their robustness.
• Abstract（参考訳）: ほとんどのバンディットアルゴリズムは報酬の分散または上限が知られていると仮定する。 分散過大評価は通常安全かつ健全であるが、後悔を増す。 一方、過小評価された分散は、最適下腕に早期にコミットするため、線形後悔を引き起こす可能性がある。 このことは、分散対応の頻繁なアルゴリズムに関する先行研究を動機付けている。 我々はベイズ設定の基礎を築いた。 特に, 既知および未知不均一報酬分散を用いたマルチアームバンドについて検討し, ベイズを後悔する双方に対するトンプソンサンプリングアルゴリズムを開発した。 私たちの後悔は報酬のばらつきを減らし、学習を楽にする。 未知の報酬分散に対するバウンドは、前者の学習報酬分散に対する影響を捉え、その種類の最初のものである。 実験では分散認識ベイズアルゴリズムの優越性を示し,その頑健性を強調する。

関連論文リスト

• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
  本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。 我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。 また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-21T00:17:24Z)
• A Regret-Variance Trade-Off in Online Learning [14.41667013062914]
  予測の分散が学習にどのように活用できるかを示す。 損失の減少を伴うオンライン予測では, 後悔に対する汚職の影響は大きなばらつきによって補うことができることを示す。 我々はその結果をオンライン線形回帰の設定にまで拡張する。
  論文  参考訳（メタデータ） (2022-06-06T14:50:19Z)
• The price of unfairness in linear bandits with biased feedback [62.25313751895011]
  線形帯域フィードバックによる逐次意思決定の問題点について検討する。 その結果,不偏フィードバック下で得られたdT 1/2 log(T) の後悔率よりも最悪の後悔率が高いことがわかった。 興味深いことに、ギャップ依存率によって、問題はバイアスのないものほど難しくない非自明なインスタンスの存在が明らかになる。
  論文  参考訳（メタデータ） (2022-03-18T08:03:20Z)
• Bayes Optimal Algorithm is Suboptimal in Frequentist Best Arm Identification [3.096615629099617]
  頻繁な単純後悔は任意の固定パラメータに対して指数関数的に$T$に小さいことが知られているが、ベイズ的単純後悔は連続的な先行よりも$Theta(T-1)$である。 本稿では,ベイズ的単純後悔を最小限に抑えるベイズ最適アルゴリズムが,いくつかのパラメータに対して指数関数的単純後悔を伴わないことを示す。
  論文  参考訳（メタデータ） (2022-02-10T17:50:26Z)
• Algorithms for Adaptive Experiments that Trade-off Statistical Analysis with Reward: Combining Uniform Random Assignment and Reward Maximization [50.725191156128645]
  トンプソンサンプリングのようなマルチアームバンディットアルゴリズムは適応的な実験を行うのに利用できる。 統計的解析のための一様ランダム化の利点を組み合わせた2つのアルゴリズムを探索する2つのアーム実験のシミュレーションを提案する。
  論文  参考訳（メタデータ） (2021-12-15T22:11:58Z)
• Risk-Aware Algorithms for Combinatorial Semi-Bandits [7.716156977428555]
  半帯域フィードバック下でのマルチアームバンディット問題について検討する。 本稿では,最悪の場合の報酬のみを考慮したリスク尺度であるCVaR(Conditional Value-at-Risk)の最大化の問題を検討する。 本稿では,バンディットのスーパーアームから得られる報酬のCVaRを最大化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-12-02T11:29:43Z)
• Breaking the Moments Condition Barrier: No-Regret Algorithm for Bandits with Super Heavy-Tailed Payoffs [27.636407641546914]
  実験的な中央値列の経験的平均を計算し,確率変数を推定する,新しい頑健な統計推定器を提案する。 非常に重みのある雑音であっても, 後悔の限界がほぼ最適であることを示す。
  論文  参考訳（メタデータ） (2021-10-26T17:30:44Z)
• On Slowly-varying Non-stationary Bandits [25.305949034527202]
  我々は、ゆっくりと変化する性質を持つ非定常包帯の動的後悔を考察する。 我々は、ゆっくりと変化する非定常帯域に対して、最初のインスタンス依存後悔上限を確立する。 我々のアルゴリズムは基本的にミニマックス最適であることを示す。
  論文  参考訳（メタデータ） (2021-10-25T12:56:19Z)
• Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
  本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。 逆汚染レベルに適応する分散認識アルゴリズムをC$で提案する。
  論文  参考訳（メタデータ） (2021-10-25T02:53:24Z)
• The Price of Incentivizing Exploration: A Characterization via Thompson Sampling and Sample Complexity [83.81297078039836]
  インセンティブ付き探索(Incentivized Exploring)は、武器の選択を自給自足エージェントによって制御するマルチアーム・バンディットのバージョンである。 我々は、インセンティブの価格に焦点を合わせ、インセンティブの適合性のために、広く解釈された、パフォーマンスの喪失が引き起こされる。
  論文  参考訳（メタデータ） (2020-02-03T04:58:51Z)
• Thompson Sampling Algorithms for Mean-Variance Bandits [97.43678751629189]
  我々は平均分散MABのためのトンプソンサンプリング型アルゴリズムを開発した。 我々はまた、ガウシアンとベルヌーイの盗賊に対する包括的後悔の分析も提供する。 我々のアルゴリズムは、全てのリスク許容度に対して既存のLCBベースのアルゴリズムを著しく上回っている。
  論文  参考訳（メタデータ） (2020-02-01T15:33:50Z)

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

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