論文の概要: Bandit algorithms: Letting go of logarithmic regret for statistical robustness

• arxiv url: http://arxiv.org/abs/2006.12038v1
• Date: Mon, 22 Jun 2020 07:18:47 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-18 04:44:16.104493
• Title: Bandit algorithms: Letting go of logarithmic regret for statistical robustness
• Title（参考訳）: Banditアルゴリズム:統計的堅牢性に対する対数的後悔の排除
• Authors: Kumar Ashutosh (IIT Bombay), Jayakrishnan Nair (IIT Bombay), Anmol Kagrecha (IIT Bombay), Krishna Jagannathan (IIT Madras)
• Abstract要約: 我々は,多武器の盗賊設定における後悔について研究し,アルゴリズムによる後悔と統計的堅牢性の間に基本的なトレードオフを確立する。 対数的後悔を伴う帯域学習アルゴリズムは常に矛盾しており、一貫した学習アルゴリズムは常に超対数的後悔に苦しむことを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study regret minimization in a stochastic multi-armed bandit setting and establish a fundamental trade-off between the regret suffered under an algorithm, and its statistical robustness. Considering broad classes of underlying arms' distributions, we show that bandit learning algorithms with logarithmic regret are always inconsistent and that consistent learning algorithms always suffer a super-logarithmic regret. This result highlights the inevitable statistical fragility of all `logarithmic regret' bandit algorithms available in the literature---for instance, if a UCB algorithm designed for $\sigma$-subGaussian distributions is used in a subGaussian setting with a mismatched variance parameter, the learning performance could be inconsistent. Next, we show a positive result: statistically robust and consistent learning performance is attainable if we allow the regret to be slightly worse than logarithmic. Specifically, we propose three classes of distribution oblivious algorithms that achieve an asymptotic regret that is arbitrarily close to logarithmic.
• Abstract（参考訳）: 本研究では, 確率的多腕バンディット設定における後悔の最小化と, アルゴリズムによる後悔と統計的ロバスト性との根本的なトレードオフの確立について検討した。 両腕の分布の幅広いクラスを考慮すると、対数的後悔を伴う帯域学習アルゴリズムは常に矛盾しており、一貫した学習アルゴリズムは常に超対数的後悔に苦しむことを示す。 例えば、$\sigma$-subgaussian分布向けに設計されたucbアルゴリズムが、ミスマッチした分散パラメータを持つサブガウシアン設定で使用される場合、学習性能は矛盾する可能性がある。 統計的にロバストで一貫性のある学習性能が得られるのは、後悔が対数よりも少し悪い場合です。 具体的には,任意に対数に近い漸近的後悔を実現する3種類の分布オブリビングアルゴリズムを提案する。

関連論文リスト

• Local Anti-Concentration Class: Logarithmic Regret for Greedy Linear Contextual Bandit [8.087699764574788]
  本研究では,線形文脈帯域問題に対する探索自由グリードアルゴリズムの性能保証について検討する。 提案手法では,テキストローカルアンチ集中(LAC)条件という新しい条件を導入し,グリーディバンディットアルゴリズムを有効活用する。
  論文  参考訳（メタデータ） (2024-11-19T21:53:06Z)
• Semi-Bandit Learning for Monotone Stochastic Optimization [20.776114616154242]
  モノトーン」問題のクラスに対して汎用的なオンライン学習アルゴリズムを提供する。 我々のフレームワークは、預言者、Pandoraのボックスナップサック、不等式マッチング、部分モジュラー最適化など、いくつかの基本的な最適化問題に適用できる。
  論文  参考訳（メタデータ） (2023-12-24T07:46:37Z)
• The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret and Policy Switches [84.54669549718075]
  漸進的強化学習(RL)における後悔の最小化問題について検討する。 一般関数クラスと一般モデルクラスで学ぶことに集中する。 対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
  論文  参考訳（メタデータ） (2022-03-03T02:55:55Z)
• Breaking the Moments Condition Barrier: No-Regret Algorithm for Bandits with Super Heavy-Tailed Payoffs [27.636407641546914]
  実験的な中央値列の経験的平均を計算し,確率変数を推定する,新しい頑健な統計推定器を提案する。 非常に重みのある雑音であっても, 後悔の限界がほぼ最適であることを示す。
  論文  参考訳（メタデータ） (2021-10-26T17:30:44Z)
• Extreme Bandits using Robust Statistics [12.6543086847761]
  我々は,古典的バンディット設定における期待値とは対照的に,極端な値のみが関心を持つ状況に動機づけられたマルチアームバンディット問題を考える。 本研究では,ロバストな統計量を用いた分布自由アルゴリズムを提案し,統計特性を特徴付ける。
  論文  参考訳（メタデータ） (2021-09-09T17:24:15Z)
• Meta-learning with Stochastic Linear Bandits [120.43000970418939]
  我々は、よく知られたOFULアルゴリズムの正規化バージョンを実装するバンディットアルゴリズムのクラスを考える。 我々は,タスク数の増加とタスク分散の分散が小さくなると,タスクを個別に学習する上で,我々の戦略が大きな優位性を持つことを理論的および実験的に示す。
  論文  参考訳（メタデータ） (2020-05-18T08:41:39Z)
• Efficient improper learning for online logistic regression [68.8204255655161]
  サンプル数 n の対数的後悔を持つ任意の正則アルゴリズムは、必然的に B の指数乗法定数を損なうことが知られている。 本研究では、対数的後悔を保ちながら、この指数定数を回避する効率的な不適切なアルゴリズムを設計する。 シュロゲート損失を伴う正規化経験的リスク最小化に基づく新しいアルゴリズムは、O(B log(Bn))として、オーダーO(d2)の1回あたりの時間複雑度で、後悔のスケーリングを満足させる。
  論文  参考訳（メタデータ） (2020-03-18T09:16:14Z)
• Adversarial Online Learning with Changing Action Sets: Efficient Algorithms with Approximate Regret Bounds [48.312484940846]
  睡眠の専門家やバンドイットによるオンライン学習の問題を再考する。 各タイムステップにおいて、アルゴリズムが選択できるアクションのサブセットのみが利用可能である。 我々は、一般的な睡眠専門家/バンド問題に対して、アポキシマ-レグレット保証を提供するアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2020-03-07T02:13:21Z)
• Model Selection in Contextual Stochastic Bandit Problems [51.94632035240787]
  基本アルゴリズムを選択できるメタアルゴリズムを開発した。 基本アルゴリズムの1つが$O(sqrtT)$後悔している場合でも、一般的には$Omega(sqrtT)$後悔よりも良いものを得ることはできません。
  論文  参考訳（メタデータ） (2020-03-03T18:46:34Z)
• Thompson Sampling Algorithms for Mean-Variance Bandits [97.43678751629189]
  我々は平均分散MABのためのトンプソンサンプリング型アルゴリズムを開発した。 我々はまた、ガウシアンとベルヌーイの盗賊に対する包括的後悔の分析も提供する。 我々のアルゴリズムは、全てのリスク許容度に対して既存のLCBベースのアルゴリズムを著しく上回っている。
  論文  参考訳（メタデータ） (2020-02-01T15:33:50Z)

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

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