論文の概要: Achieving Near-Optimal Regret for Bandit Algorithms with Uniform
Last-Iterate Guarantee
- arxiv url: http://arxiv.org/abs/2402.12711v1
- Date: Tue, 20 Feb 2024 04:21:13 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-21 17:11:37.933307
- Title: Achieving Near-Optimal Regret for Bandit Algorithms with Uniform
Last-Iterate Guarantee
- Title(参考訳): 一様最終保証付き帯域アルゴリズムの準最適レグレを得る
- Authors: Junyan Liu, Yunfan Li, Lin Yang
- Abstract要約: 本稿では,バンドレートアルゴリズムの累積性能と即時性能を両立させる,より強力な性能尺度,ULI(Universal Last-iterate)の保証を提案する。
以上の結果から, ほぼ最適なULI保証は, 上記の性能指標にまたがって, ほぼ最適な累積性能を直接的に示唆することを示す。
- 参考スコア(独自算出の注目度): 10.159410396698929
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Existing performance measures for bandit algorithms such as regret, PAC
bounds, or uniform-PAC (Dann et al., 2017), typically evaluate the cumulative
performance, while allowing the play of an arbitrarily bad arm at any finite
time t. Such a behavior can be highly detrimental in high-stakes applications.
This paper introduces a stronger performance measure, the uniform last-iterate
(ULI) guarantee, capturing both cumulative and instantaneous performance of
bandit algorithms. Specifically, ULI characterizes the instantaneous
performance since it ensures that the per-round regret of the played arm is
bounded by a function, monotonically decreasing w.r.t. (large) round t,
preventing revisits to bad arms when sufficient samples are available. We
demonstrate that a near-optimal ULI guarantee directly implies near-optimal
cumulative performance across aforementioned performance measures. To examine
the achievability of ULI in the finite arm setting, we first provide two
positive results that some elimination-based algorithms and high-probability
adversarial algorithms with stronger analysis or additional designs, can attain
near-optimal ULI guarantees. Then, we also provide a negative result,
indicating that optimistic algorithms cannot achieve a near-optimal ULI
guarantee. Finally, we propose an efficient algorithm for linear bandits with
infinitely many arms, which achieves the ULI guarantee, given access to an
optimization oracle.
- Abstract(参考訳): 後悔、PACバウンダリ、均一PAC(Dann et al., 2017)のような既存のバンディットアルゴリズムのパフォーマンス測定は、一般に累積性能を評価し、任意の有限時間tでの任意に悪い腕の演奏を可能にする。
このような振る舞いは、高スループットアプリケーションでは極めて有害である。
本稿では,バンドレートアルゴリズムの累積性能と即時性能を両立させる,より強力な性能尺度,ULI保証を提案する。
特に、ULIは、演奏腕の丸ごとの後悔が機能によって束縛されていることを保証し、w.r.t.(大きな)ラウンドtを単調に減少させ、十分なサンプルが得られれば、悪い腕への再訪を防止するため、即時のパフォーマンスを特徴付ける。
以上の結果から, ほぼ最適ULI保証は, 上記の性能指標のほぼ最適累積性能を直接意味することを示す。
有限アーム設定におけるuliの到達可能性を調べるために,まず,削除に基づくアルゴリズムと,より強力な解析や追加設計を持つ高確率逆アルゴリズムの2つの正の結果を提示する。
さらに,楽観的アルゴリズムでは至近距離 uli 保証が達成できないことを示す負の結果も提示する。
最後に,最適化オラクルへのアクセスによってuli保証を実現する,無限個のアームを持つ線形バンディットに対する効率的なアルゴリズムを提案する。
関連論文リスト
- CONFIG: Constrained Efficient Global Optimization for Closed-Loop
Control System Optimization with Unmodeled Constraints [11.523746174066702]
OPTアルゴリズムは未知系の非モデル制約による閉ループ制御性能を最適化するために用いられる。
その結果,提案アルゴリズムは,最適性保証のないCEI (Constrained expecteded Improvement) アルゴリズムと競合する性能を達成できることが示唆された。
論文 参考訳(メタデータ) (2022-11-21T19:44:00Z) - Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time
Guarantees [56.848265937921354]
逆強化学習(IRL)は報酬関数と関連する最適ポリシーを回復することを目的としている。
IRLの多くのアルゴリズムは本質的にネスト構造を持つ。
我々は、報酬推定精度を損なわないIRLのための新しいシングルループアルゴリズムを開発した。
論文 参考訳(メタデータ) (2022-10-04T17:13:45Z) - A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian
Process Bandits [118.22458816174144]
そこで本稿では,エポックで動作するロバストな除去型アルゴリズムを提案し,探索と頻繁な切替を併用して,小さなアクションサブセットを選択し,各アクションを複数タイミングで実行する。
我々のアルゴリズムであるGP Robust Phased Elimination (RGP-PE) は、探索とエクスプロイトによる汚職に対するロバストネスのバランスに成功している。
GPバンディット設定におけるロバスト性の最初の実証的研究を行い,アルゴリズムが様々な敵攻撃に対してロバストであることを示す。
論文 参考訳(メタデータ) (2022-02-03T21:19:36Z) - Uniform-PAC Bounds for Reinforcement Learning with Linear Function
Approximation [92.3161051419884]
線形関数近似を用いた強化学習について検討する。
既存のアルゴリズムは、高い確率的後悔と/またはおよそ正当性(PAC)サンプルの複雑さの保証しか持たない。
我々はFLUTEと呼ばれる新しいアルゴリズムを提案し、高い確率で最適ポリシーへの均一PAC収束を享受する。
論文 参考訳(メタデータ) (2021-06-22T08:48:56Z) - Sparse PCA: Algorithms, Adversarial Perturbations and Certificates [9.348107805982604]
標準統計モデルにおけるスパースPCAの効率的なアルゴリズムについて検討する。
私たちのゴールは、小さな摂動に耐性を持ちながら、最適な回復保証を達成することです。
論文 参考訳(メタデータ) (2020-11-12T18:58:51Z) - Experimental Design for Regret Minimization in Linear Bandits [19.8309784360219]
オンライン・リニア・バンドレットにおける後悔を最小限に抑える設計に基づく新しいアルゴリズムを提案する。
我々は、現在最先端の有限時間後悔保証を提供し、このアルゴリズムが帯域幅と半帯域幅の両方のフィードバックシステムに適用可能であることを示す。
論文 参考訳(メタデータ) (2020-11-01T17:59:19Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳(メタデータ) (2020-10-23T09:12:47Z) - Lenient Regret for Multi-Armed Bandits [72.56064196252498]
エージェントが順番に行動を選択し、その行動に対する報酬を観察するマルチアーマッド・バンディット(MAB)問題を考察する。
アルゴリズムの大多数は、後悔、すなわち最高の行動の報酬とエージェントの行動の累積的な差を最小化しようとするが、この基準は望ましくない結果をもたらすかもしれない。
我々は、いくつかの$epsilon$よりも小さな最適性ギャップを無視した、より寛大で寛大で後悔すべき基準を提案する。
論文 参考訳(メタデータ) (2020-08-10T08:30:52Z) - Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
サンプルの複雑さが既知のインスタンス固有の下界と一致する単純なアルゴリズムを考案する。
既存のベストアーム識別戦略とは異なり、我々のアルゴリズムは武器の数に依存しない停止規則を用いる。
論文 参考訳(メタデータ) (2020-06-29T14:25:51Z) - Bandit algorithms to emulate human decision making using probabilistic
distortions [20.422725678982726]
報奨分布に歪んだ確率を持つ2つの多重武装バンディット問題を定式化する。
以上のような後悔の最小化の問題と、マルチアームバンディットのための最高の腕識別フレームワークについて考察する。
論文 参考訳(メタデータ) (2016-11-30T17:37:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。