論文の概要: Improved Algorithms for Stochastic Linear Bandits Using Tail Bounds for
Martingale Mixtures
- arxiv url: http://arxiv.org/abs/2309.14298v2
- Date: Wed, 27 Sep 2023 09:32:01 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-28 10:24:03.138873
- Title: Improved Algorithms for Stochastic Linear Bandits Using Tail Bounds for
Martingale Mixtures
- Title(参考訳): タイル境界を用いた確率線形帯域のMartingale混合に対する改良アルゴリズム
- Authors: Hamish Flynn, David Reeb, Melih Kandemir, Jan Peters
- Abstract要約: 線形バンディット問題に対する最悪の後悔の保証を施した改良アルゴリズムを提案する。
我々は、我々の信頼シーケンスが、経験的にも理論的にも、競合よりも厳密であることを示す。
- 参考スコア(独自算出の注目度): 26.683757807252675
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present improved algorithms with worst-case regret guarantees for the
stochastic linear bandit problem. The widely used "optimism in the face of
uncertainty" principle reduces a stochastic bandit problem to the construction
of a confidence sequence for the unknown reward function. The performance of
the resulting bandit algorithm depends on the size of the confidence sequence,
with smaller confidence sets yielding better empirical performance and stronger
regret guarantees. In this work, we use a novel tail bound for adaptive
martingale mixtures to construct confidence sequences which are suitable for
stochastic bandits. These confidence sequences allow for efficient action
selection via convex programming. We prove that a linear bandit algorithm based
on our confidence sequences is guaranteed to achieve competitive worst-case
regret. We show that our confidence sequences are tighter than competitors,
both empirically and theoretically. Finally, we demonstrate that our tighter
confidence sequences give improved performance in several hyperparameter tuning
tasks.
- Abstract(参考訳): 確率線形バンディット問題に対する最悪の後悔の保証を伴う改良アルゴリズムを提案する。
広く使われている「不確実性に直面した最適主義」原理は、確率的バンディット問題を未知の報酬関数に対する信頼シーケンスの構築に還元する。
結果として得られたbanditアルゴリズムのパフォーマンスは、信頼性シーケンスのサイズに依存するが、より小さな信頼セットは、よりよい経験的パフォーマンスとより強い後悔の保証をもたらす。
本研究では,適応マルティンゲール混合のための新しいテールバインドを用いて,確率的バンドイットに適した信頼度列を構築する。
これらの信頼シーケンスは凸プログラミングによる効率的な行動選択を可能にする。
信頼性シーケンスに基づく線形バンディットアルゴリズムは、競合する最悪の最悪の後悔を実現することが保証されている。
我々は、我々の信頼シーケンスが、経験的にも理論的にも競合より厳密であることを示す。
最後に,より厳密な信頼シーケンスにより,複数のハイパーパラメータチューニングタスクの性能が向上することを示す。
関連論文リスト
- Tighter Confidence Bounds for Sequential Kernel Regression [3.683202928838613]
我々は、シーケンシャルカーネル回帰のための新しい信頼境界を確立するために、マーチンゲールテール不等式を使用する。
私たちの信頼境界は円錐プログラムを解くことで計算できるが、この素バージョンはすぐに非現実的になる。
信頼性境界が既存のものを置き換えると、KernelUCBアルゴリズムはより優れた経験的性能、最悪のパフォーマンス保証、それに匹敵する計算コストが得られます。
論文 参考訳(メタデータ) (2024-03-19T13:47:35Z) - Binary Classification with Confidence Difference [100.08818204756093]
本稿では,信頼性差分法 (ConfDiff) という,弱教師付き二項分類問題について考察する。
本稿では,この問題に対処するためのリスク一貫性のあるアプローチを提案し,推定誤差が最適収束率と一致することを示す。
また,整合性や収束率も証明されたオーバーフィッティング問題を緩和するためのリスク補正手法も導入する。
論文 参考訳(メタデータ) (2023-10-09T11:44:50Z) - Huber-Robust Confidence Sequences [37.16361789841549]
信頼シーケンスは、逐次追跡可能な信頼区間であり、任意のデータ依存の停止時間で有効である。
非逐次的設定で達成された最適幅を達成するために,結果の信頼性シーケンスが得られたことを示す。
信頼シーケンスは、A/B/nテストやバンドイットで使用される一般的なツールであるため、これらの結果は、外れ値や敵の腐敗に対して堅牢なシーケンシャルな実験への扉を開く。
論文 参考訳(メタデータ) (2023-01-23T17:29:26Z) - SmoothMix: Training Confidence-calibrated Smoothed Classifiers for
Certified Robustness [61.212486108346695]
自己混合によるスムーズな分類器のロバスト性を制御するためのトレーニングスキームSmoothMixを提案する。
提案手法は, 厳密性に制限された原因として, 信頼性の低い, オフクラスに近いサンプルを効果的に同定する。
提案手法はスムーズな分類器の検証値である$ell$-robustnessを大幅に改善できることを示す。
論文 参考訳(メタデータ) (2021-11-17T18:20:59Z) - Open Problem: Tight Online Confidence Intervals for RKHS Elements [57.363123214464764]
我々は、RKHS設定におけるオンライン信頼区間の質問を形式化し、既存の結果を概観する。
準最適後悔境界がこれらのアルゴリズムの根本的な欠点なのか、あるいは証明の成果物なのかは定かではない。
論文 参考訳(メタデータ) (2021-10-28T22:36:20Z) - Off-policy Confidence Sequences [33.749904615295485]
文脈的バンディット設定において,オフポリシー評価に一定時間をかけて保持する信頼度境界を開発する。
計算効率と統計効率のバランスを良くする信頼度列を計算するためのアルゴリズムを提供する。
論文 参考訳(メタデータ) (2021-02-18T18:40:30Z) - Upper Confidence Bounds for Combining Stochastic Bandits [52.10197476419621]
バンディットアルゴリズムを結合する簡単な手法を提案する。
私たちのアプローチは、個々のbanditアルゴリズムのそれぞれを、より高いレベルのn$-armed bandit問題のアームとして扱う"meta-ucb"手順に基づいています。
論文 参考訳(メタデータ) (2020-12-24T05:36:29Z) - Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
サンプルの複雑さが既知のインスタンス固有の下界と一致する単純なアルゴリズムを考案する。
既存のベストアーム識別戦略とは異なり、我々のアルゴリズムは武器の数に依存しない停止規則を用いる。
論文 参考訳(メタデータ) (2020-06-29T14:25:51Z) - Near-Optimal Confidence Sequences for Bounded Random Variables [5.901337162013615]
オンライン推論の根本的な問題は、成長する無限小サンプルサイズに対して均一に有効である信頼区間のシーケンスを提供することである。
我々は,ベンツクスの濃度値を利用して,有界確率変数のほぼ最適確率列を提供する。
得られた信頼性シーケンスは、合成カバレッジ問題と適応停止アルゴリズムへの応用の両方において好適であることが確認された。
論文 参考訳(メタデータ) (2020-06-09T02:50:01Z) - Robustness Guarantees for Mode Estimation with an Application to Bandits [131.21717367564963]
平均ではなく報酬分布のモードを値とするマルチアームバンディットの理論を導入する。
我々は,我々のアルゴリズムが逆雑音列による腕の摂動に頑健であることを示すシミュレーションで示す。
論文 参考訳(メタデータ) (2020-03-05T21:29:27Z) - Bandit algorithms to emulate human decision making using probabilistic
distortions [20.422725678982726]
報奨分布に歪んだ確率を持つ2つの多重武装バンディット問題を定式化する。
以上のような後悔の最小化の問題と、マルチアームバンディットのための最高の腕識別フレームワークについて考察する。
論文 参考訳(メタデータ) (2016-11-30T17:37:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。