論文の概要: Optimism in the Face of Ambiguity Principle for Multi-Armed Bandits
- arxiv url: http://arxiv.org/abs/2409.20440v1
- Date: Mon, 30 Sep 2024 16:00:23 GMT
- ステータス: 処理完了
- システム内更新日: 2024-10-02 06:50:32.282526
- Title: Optimism in the Face of Ambiguity Principle for Multi-Armed Bandits
- Title（参考訳）: マルチアーマッドバンドにおけるあいまいさ原理の面における最適化
- Authors: Mengmeng Li, Daniel Kuhn, Bahar Taskesen,
- Abstract要約: FTRL (Follow-The-Regularized-Leader) アルゴリズムは、しばしば敵対的問題や盗賊問題に対して最適な後悔を味わう。
本稿では,逆方向と多重方向の両方の帯域に対して最適なポリシを生成する新しいFTPLアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 6.7310264583128445
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Follow-The-Regularized-Leader (FTRL) algorithms often enjoy optimal regret for adversarial as well as stochastic bandit problems and allow for a streamlined analysis. Nonetheless, FTRL algorithms require the solution of an optimization problem in every iteration and are thus computationally challenging. In contrast, Follow-The-Perturbed-Leader (FTPL) algorithms achieve computational efficiency by perturbing the estimates of the rewards of the arms, but their regret analysis is cumbersome. We propose a new FTPL algorithm that generates optimal policies for both adversarial and stochastic multi-armed bandits. Like FTRL, our algorithm admits a unified regret analysis, and similar to FTPL, it offers low computational costs. Unlike existing FTPL algorithms that rely on independent additive disturbances governed by a \textit{known} distribution, we allow for disturbances governed by an \textit{ambiguous} distribution that is only known to belong to a given set and propose a principle of optimism in the face of ambiguity. Consequently, our framework generalizes existing FTPL algorithms. It also encapsulates a broad range of FTRL methods as special cases, including several optimal ones, which appears to be impossible with current FTPL methods. Finally, we use techniques from discrete choice theory to devise an efficient bisection algorithm for computing the optimistic arm sampling probabilities. This algorithm is up to $10^4$ times faster than standard FTRL algorithms that solve an optimization problem in every iteration. Our results not only settle existing conjectures but also provide new insights into the impact of perturbations by mapping FTRL to FTPL.
- Abstract（参考訳）: FTRL(Follow-The-Regularized-Leader)アルゴリズムは、しばしば逆数や確率的バンディット問題に対して最適な後悔を味わう。
それでも、FTRLアルゴリズムは各イテレーションで最適化問題の解を必要とするため、計算的に困難である。
対照的に、Follow-The-Perturbed-Leader (FTPL)アルゴリズムは、腕の報酬の見積もりを摂動させることで計算効率を向上するが、その残念な分析は困難である。
本稿では,逆方向と確率方向の両方のマルチアームバンディットに対して最適なポリシを生成する新しいFTPLアルゴリズムを提案する。
FTRLと同様に、我々のアルゴリズムは再帰解析を統一しており、FTPLと同様、計算コストが低い。
既存の FTPL アルゴリズムは、独立な加法的外乱を \textit{known} 分布に支配しているのとは異なり、与えられた集合に属することしか知られていない \textit{ambiguous} 分布に支配される外乱を許容し、あいまいさに直面して楽観主義の原理を提案する。
その結果,既存のFTPLアルゴリズムを一般化した。
また、現在のFTPLメソッドでは不可能と思われるいくつかの最適なメソッドを含む、FTRLメソッドを特別なケースとしてカプセル化している。
最後に、離散選択理論の手法を用いて、楽観的なアームサンプリング確率を計算するための効率的な分岐アルゴリズムを考案する。
このアルゴリズムは、イテレーション毎に最適化問題を解く標準のFTRLアルゴリズムの最大10^4$倍高速である。
以上の結果から,FTRLからFTPLへの写像による摂動の影響に関する新たな知見が得られた。
関連論文リスト
- Making RL with Preference-based Feedback Efficient via Randomization [11.019088464664696]
人間のフィードバックから学習する強化学習アルゴリズムは、統計複雑性、計算複雑性、クエリ複雑性の点で効率的である必要がある。
提案するアルゴリズムは, サンプル効率のよいアルゴリズム(すなわち, ほぼ最適ケースの後悔境界)と実行時間(すなわち, 関連するパラメータに関して計算複雑性が最悪の場合)を提案する。
結果をより一般的な非線形関数近似に拡張するために、トンプソンサンプリングのアイデアに触発されたモデルベースランダム化アルゴリズムを設計する。
論文 参考訳（メタデータ） (2023-10-23T04:19:35Z) - Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳（メタデータ） (2023-10-18T10:29:58Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳（メタデータ） (2023-07-17T20:11:56Z) - Stability-penalty-adaptive follow-the-regularized-leader: Sparsity,
game-dependency, and best-of-both-worlds [46.30750729936261]
FTRL(Follow-the-regularized-leader)は近年,バンドイット問題における適応性獲得の最も有望なアプローチの1つである。
我々は3種類の適応性を持ついくつかのアルゴリズムを確立する:空間性、ゲーム依存性、およびベスト・オブ・ボス・ワールド(BOBW)である。
論文 参考訳（メタデータ） (2023-05-26T23:20:48Z) - Best-of-three-worlds Analysis for Linear Bandits with
Follow-the-regularized-leader Algorithm [11.80907528239756]
線形バンディット問題は、双方の相反する環境で長年研究されてきた。
citetLeeLWZ021は、損失タイプを積極的に検出し、特定の設定のために特別に設計された異なるアルゴリズムを切り替えるアルゴリズムを提案する。
FTRL(Follow-the-regularized-leader)は、異なる環境に適応可能な人気アルゴリズムの一種である。
論文 参考訳（メタデータ） (2023-03-13T02:50:59Z) - Improved Best-of-Both-Worlds Guarantees for Multi-Armed Bandits: FTRL
with General Regularizers and Multiple Optimal Arms [41.06668954462585]
本研究では,適応型マルチアームバンディットアルゴリズムを設計する際の課題について検討する。
FTRLには多種多様な正規化要因と新たな学習率スケジュールが不要であることを示す。
論文 参考訳（メタデータ） (2023-02-27T06:09:10Z) - Optimization-Based GenQSGD for Federated Edge Learning [12.371264770814097]
我々は、連合学習(FL)のための一般化された並列最小バッチ収束降下(SGD)アルゴリズムを提案する。
我々は,時間収束誤差の下でのエネルギーコストを最小限に抑えるために,アルゴリズムパラメータを最適化する。
その結果,既存のFLアルゴリズムよりも有意な利得が得られた。
論文 参考訳（メタデータ） (2021-10-25T14:25:11Z) - Learning Sampling Policy for Faster Derivative Free Optimization [100.27518340593284]
ランダムサンプリングではなく,ZO最適化における摂動を生成するためのサンプリングポリシを学習する,新たな強化学習ベースのZOアルゴリズムを提案する。
その結果,ZO-RLアルゴリズムはサンプリングポリシを学習することでZO勾配の分散を効果的に低減し,既存のZOアルゴリズムよりも高速に収束できることが示唆された。
論文 参考訳（メタデータ） (2021-04-09T14:50:59Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳（メタデータ） (2020-10-23T09:12:47Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。