論文の概要: Forced-exploration free Strategies for Unimodal Bandits
- arxiv url: http://arxiv.org/abs/2006.16569v1
- Date: Tue, 30 Jun 2020 07:06:16 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-15 05:10:22.862790
- Title: Forced-exploration free Strategies for Unimodal Bandits
- Title(参考訳): ユニモーダルバンディットの強制爆発自由戦略
- Authors: Hassan Saber (SEQUEL), Pierre M\'enard (SEQUEL), Odalric-Ambrym
Maillard (SEQUEL)
- Abstract要約: 単調構造を利用した最初の強制探索自由戦略であるIMED-UBを紹介する。
次に, IMED-UBのKLUCBバージョンであるKLUCB-UBを導出する。
数値実験により、IMED-UBとKLUCB-UBはどちらも同様の性能を示し、最先端のアルゴリズムよりも優れていた。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider a multi-armed bandit problem specified by a set of Gaussian or
Bernoulli distributions endowed with a unimodal structure. Although this
problem has been addressed in the literature (Combes and Proutiere, 2014), the
state-of-the-art algorithms for such structure make appear a forced-exploration
mechanism. We introduce IMED-UB, the first forced-exploration free strategy
that exploits the unimodal-structure, by adapting to this setting the Indexed
Minimum Empirical Divergence (IMED) strategy introduced by Honda and Takemura
(2015). This strategy is proven optimal. We then derive KLUCB-UB, a KLUCB
version of IMED-UB, which is also proven optimal. Owing to our proof technique,
we are further able to provide a concise finite-time analysis of both
strategies in an unified way. Numerical experiments show that both IMED-UB and
KLUCB-UB perform similarly in practice and outperform the state-of-the-art
algorithms.
- Abstract(参考訳): 我々は、一様構造を持つガウス分布やベルヌーイ分布によって特定される多腕バンディット問題を考える。
この問題は文献(combes and proutiere, 2014)では解決されているが、そのような構造に対する最先端のアルゴリズムは強制爆発のメカニズムとなっている。
本稿では,本多と竹村(2015)が導入したIMED(Indexed Minimum Empirical Divergence)戦略に適応して,この不定形構造を利用した最初の強制探索自由戦略であるIMED-UBを紹介する。
この戦略は最適である。
次に, IMED-UBのKLUCBバージョンであるKLUCB-UBを導出する。
証明手法により,両戦略の簡潔な有限時間解析を統一的に行うことが可能となった。
数値実験により、IMED-UBとKLUCB-UBはどちらも同様の性能を示し、最先端のアルゴリズムよりも優れていた。
関連論文リスト
- Prior-Dependent Allocations for Bayesian Fixed-Budget Best-Arm
Identification in Structured Bandits [5.362453227879925]
本研究では, ベイジアン固定予算ベストアーム識別(BAI)の問題について検討する。
本稿では,事前情報と環境構造に基づく固定割当を用いたアルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-02-08T18:13:26Z) - Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳(メタデータ) (2023-12-19T13:17:43Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳(メタデータ) (2023-12-13T11:08:25Z) - Online Learning with Adversaries: A Differential-Inclusion Analysis [52.43460995467893]
我々は,完全に非同期なオンラインフェデレート学習のための観察行列ベースのフレームワークを提案する。
我々の主な結果は、提案アルゴリズムがほぼ確実に所望の平均$mu.$に収束することである。
新たな差分包摂型2時間スケール解析を用いて,この収束を導出する。
論文 参考訳(メタデータ) (2023-04-04T04:32:29Z) - On Kernelized Multi-Armed Bandits with Constraints [16.102401271318012]
一般に未知の報酬関数と一般未知の制約関数を併用した帯域幅問題について検討する。
本稿では,アルゴリズムの性能解析のための一般的なフレームワークを提案する。
本稿では,数値実験により提案アルゴリズムの優れた性能を示す。
論文 参考訳(メタデータ) (2022-03-29T14:02:03Z) - Indexed Minimum Empirical Divergence for Unimodal Bandits [0.0]
単調構造を最適に活用するアルゴリズムであるIMED-UBを導入する。
IMED-UBは最先端のアルゴリズムと競合することを示す。
論文 参考訳(メタデータ) (2021-12-02T17:48:37Z) - Misspecified Gaussian Process Bandit Optimization [59.30399661155574]
カーネル化されたバンディットアルゴリズムは、この問題に対して強い経験的および理論的性能を示した。
本稿では、未知関数を$epsilon$-一様近似で近似できるエンフェミス特定カーネル化帯域設定を、ある再生カーネルヒルベルト空間(RKHS)において有界ノルムを持つ関数で導入する。
提案アルゴリズムは,不特定性に関する事前知識を伴わず,$epsilon$への最適依存を実現する。
論文 参考訳(メタデータ) (2021-11-09T09:00:02Z) - Towards Gradient-based Bilevel Optimization with Non-convex Followers
and Beyond [37.89147034158937]
Bi-LevelLOcation (BLO)は、学習コミュニティとビジョンコミュニティの両方から大きな注目を集めている。
我々はAuxiliaryization and Pessimy Truncated Gradient (IAPTT-GM)という新しいBLOのクラスを提案する。
特に,最適化力学を導く補助的手法を導入し,トラルン演算を設計することにより,元のBLO LLCの信頼性の高い近似バージョンを構築する。
論文 参考訳(メタデータ) (2021-10-01T14:41:17Z) - Improved Branch and Bound for Neural Network Verification via Lagrangian
Decomposition [161.09660864941603]
ニューラルネットワークの入出力特性を公式に証明するためのブランチとバウンド(BaB)アルゴリズムのスケーラビリティを改善します。
活性化に基づく新しい分岐戦略とBaBフレームワークであるブランチとデュアルネットワーク境界(BaDNB)を提案する。
BaDNBは、従来の完全検証システムを大きなマージンで上回り、対数特性で平均検証時間を最大50倍に削減した。
論文 参考訳(メタデータ) (2021-04-14T09:22:42Z) - Sharp Analysis of Smoothed Bellman Error Embedding [17.296084954104415]
バッチモード強化学習におけるSBEEDの理論的挙動について検討する。
使用済み関数クラスの表現力に依存するほぼ最適性能を保証する。
論文 参考訳(メタデータ) (2020-07-07T19:27:09Z) - The Simulator: Understanding Adaptive Sampling in the
Moderate-Confidence Regime [52.38455827779212]
エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。
適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。
我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
論文 参考訳(メタデータ) (2017-02-16T23:42:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。