論文の概要: Trading Off Resource Budgets for Improved Regret Bounds
- arxiv url: http://arxiv.org/abs/2210.05789v1
- Date: Tue, 11 Oct 2022 21:13:48 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-13 13:10:26.462086
- Title: Trading Off Resource Budgets for Improved Regret Bounds
- Title（参考訳）: 資源予算のトレーディングオフと「後悔の限界」の改善
- Authors: Damon Falck and Thomas Orton
- Abstract要約: 対戦型オンライン学習問題に対するFPML(Follow the Perturbed Multiple Leaders)と呼ばれるアルゴリズムを提案する。
また, FPML は, 所要時間で $mathcalO(Tfrac1B+1ln(N)fracBB+1)$ となることを示す。
我々はFPMLがより強力なオラクルを必要とする線形プログラミングの新しいアルゴリズムにどのように導くかを示す。
- 参考スコア（独自算出の注目度）: 6.85316573653194
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this work we consider a variant of adversarial online learning where in
each round one picks $B$ out of $N$ arms and incurs cost equal to the
$\textit{minimum}$ of the costs of each arm chosen. We propose an algorithm
called Follow the Perturbed Multiple Leaders (FPML) for this problem, which we
show (by adapting the techniques of Kalai and Vempala [2005]) achieves expected
regret $\mathcal{O}(T^{\frac{1}{B+1}}\ln(N)^{\frac{B}{B+1}})$ over time horizon
$T$ relative to the $\textit{single}$ best arm in hindsight. This introduces a
trade-off between the budget $B$ and the single-best-arm regret, and we proceed
to investigate several applications of this trade-off. First, we observe that
algorithms which use standard regret minimizers as subroutines can sometimes be
adapted by replacing these subroutines with FPML, and we use this to generalize
existing algorithms for Online Submodular Function Maximization [Streeter and
Golovin, 2008] in both the full feedback and semi-bandit feedback settings.
Next, we empirically evaluate our new algorithms on an online black-box
hyperparameter optimization problem. Finally, we show how FPML can lead to new
algorithms for Linear Programming which require stronger oracles at the benefit
of fewer oracle calls.
- Abstract（参考訳）: この研究では、各ラウンドで$N$のアームから$B$を選び、選択した各アームのコストの$\textit{minimum}$に等しいコストを発生させる、対戦型オンライン学習のバリエーションについて検討する。
この問題に対してFollow the Perturbed Multiple Leaders (FPML) というアルゴリズムを提案するが、これは(Kalai と Vempala [2005] のテクニックを適応させることで)期待された後悔の $\mathcal{O}(T^{\frac{1}{B+1}}\ln(N)^{\frac{B}{B+1}})$ over time horizon $T$ を、後向きの $\textit{single}$ best arm in hindsight に比例して示している。
このことは、B$の予算とシングルベストアームの後悔のトレードオフを導入し、このトレードオフのいくつかの応用を調査します。
まず,これらのサブルーチンをFPMLに置き換えることで,標準的な後悔最小化器をサブルーチンとして利用するアルゴリズムが適用可能であることを考察し,オンラインサブモジュール関数最大化(Streeter and Golovin, 2008)のための既存のアルゴリズムを,完全なフィードバックと半帯域フィードバックの両方で一般化する。
次に,オンラインブラックボックスハイパーパラメータ最適化問題において,新たなアルゴリズムを経験的に評価する。
最後に、FPMLがより強力なオラクルを必要とする線形プログラミングのための新しいアルゴリズムにどのように導くかを示す。
関連論文リスト
- Improved Projection-free Online Continuous Submodular Maximization [35.324719857218014]
単調かつ連続DR-サブモジュラー報酬関数を用いたオンライン学習の問題点について検討する。
従来の研究では、$O(T)$グラデーション評価を用いたMono-Frank-Wolfe (Mono-FW)と呼ばれる効率的なプロジェクションフリーアルゴリズムが提案されている。
同じ計算量を維持しつつ, 後悔を$O(T3/4)$に抑える改良されたプロジェクションフリーアルゴリズム(POBGA)を提案する。
論文 参考訳（メタデータ） (2023-05-29T02:54:31Z) - Logarithmic Switching Cost in Reinforcement Learning beyond Linear MDPs [31.673857053336352]
本稿では,時間ホリゾン$H$において,エピソード数と線形数に切り替えコストの対数性を持たせることで,ほぼ最適の後悔を実現するアルゴリズムを提案する。
また、ELEANOR-LowSwitchingで使われる「二重化トリック」を一般化線形関数近似にさらに活用できることを示す。
論文 参考訳（メタデータ） (2023-02-24T05:14:27Z) - A Framework for Adapting Offline Algorithms to Solve Combinatorial
Multi-Armed Bandit Problems with Bandit Feedback [27.192028744078282]
離散オフライン近似アルゴリズムをサブ線形$alpha$-regretに適応するためのフレームワークを提供する。
提案手法は準モジュラー地平線における多種多様な応用に適用できる。
論文 参考訳（メタデータ） (2023-01-30T23:18:06Z) - Towards Painless Policy Optimization for Constrained MDPs [46.12526917024248]
我々は、無限の地平線における政策最適化、$gamma$-discounted constrained Markov decision process (CMDP)について研究する。
我々の目標は、小さな制約違反で大きな期待された報酬を達成する政策を返却することである。
本稿では,任意のアルゴリズムに対して,報酬の準最適性と制約違反を拘束できる汎用的原始双対フレームワークを提案する。
論文 参考訳（メタデータ） (2022-04-11T15:08:09Z) - Corralling a Larger Band of Bandits: A Case Study on Switching Regret
for Linear Bandits [99.86860277006318]
本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。
Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。
この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
論文 参考訳（メタデータ） (2022-02-12T21:55:44Z) - New Projection-free Algorithms for Online Convex Optimization with
Adaptive Regret Guarantees [21.30065439295409]
オンライン凸最適化(OCO)のための効率的なテキストプロジェクションフリーアルゴリズムを提案する。
提案アルゴリズムは,テキストインファシブルプロジェクション(textitinfeasible projections)と呼ばれる新しい,効率的なアプローチによるテクスタイトライン勾配降下アルゴリズムに基づいている。
我々は、全体として$O(T)$コールを使用して分離オラクルを呼び出し、$O(sqrtT)$アダプティブな後悔と$O(T3/4)$アダプティブな期待された後悔を保証します。
論文 参考訳（メタデータ） (2022-02-09T20:56:16Z) - Efficient and Optimal Algorithms for Contextual Dueling Bandits under
Realizability [59.81339109121384]
我々は,学習者が文脈情報を用いて2つの決定を下す連続的な決定設定であるK$コンテキストデュエルバンディット問題について検討するが,一方の判断が他方よりも優れていることを示唆する強調基準に基づくフィードバックのみを観察する。
提案手法は, 最善応答後悔という新たな概念に対して, 最善応答後悔に対する最適後悔率を実現するアルゴリズムである。
論文 参考訳（メタデータ） (2021-11-24T07:14:57Z) - Online Apprenticeship Learning [58.45089581278177]
見習い学習(AL)では、コスト関数にアクセスせずにマルコフ決定プロセス(MDP)が与えられます。
目標は、事前に定義されたコスト関数のセットで専門家のパフォーマンスに一致するポリシーを見つけることです。
ミラー下降型ノンレグレットアルゴリズムを2つ組み合わせることで,OAL問題を効果的に解くことができることを示す。
論文 参考訳（メタデータ） (2021-02-13T12:57:51Z) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-20T04:29:18Z) - A Provably Efficient Algorithm for Linear Markov Decision Process with
Low Switching Cost [53.968049198926444]
スイッチングコストの低い線形MDPのための最初のアルゴリズムを提案する。
このアルゴリズムは$widetildeoleft(sqrtd3h4kright)$ regretをほぼ最適の$oleft(d hlog kright)$グローバルスイッチングコストで達成する。
論文 参考訳（メタデータ） (2021-01-02T18:41:27Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。