論文の概要: Scale Free Adversarial Multi Armed Bandits
- arxiv url: http://arxiv.org/abs/2106.04700v1
- Date: Tue, 8 Jun 2021 21:26:57 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-11 09:45:29.820224
- Title: Scale Free Adversarial Multi Armed Bandits
- Title（参考訳）: スケールフリーの対向型多武装バンディット
- Authors: Sudeep Raja Putta, Shipra Agrawal
- Abstract要約: 本稿では,MAB(Scale-Free Adversarial Multi Armed Bandit)問題について考察する。
我々はFTRLアルゴリズムを設計するが、これはMABに対する最初の無スケールな後悔の保証が伴う。
また,Bregman Divergencesの局所ノルム下界を求める新しい手法を開発した。
- 参考スコア（独自算出の注目度）: 13.757095663704858
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the Scale-Free Adversarial Multi Armed Bandit(MAB) problem, where
the player only knows the number of arms $n$ and not the scale or magnitude of
the losses. It sees bandit feedback about the loss vectors $l_1,\dots, l_T \in
\mathbb{R}^n$. The goal is to bound its regret as a function of $n$ and
$l_1,\dots, l_T$. We design a Follow The Regularized Leader(FTRL) algorithm,
which comes with the first scale-free regret guarantee for MAB. It uses the log
barrier regularizer, the importance weighted estimator, an adaptive learning
rate, and an adaptive exploration parameter. In the analysis, we introduce a
simple, unifying technique for obtaining regret inequalities for FTRL and
Online Mirror Descent(OMD) on the probability simplex using Potential Functions
and Mixed Bregmans. We also develop a new technique for obtaining local-norm
lower bounds for Bregman Divergences, which are crucial in bandit regret
bounds. These tools could be of independent interest.
- Abstract（参考訳）: 我々は、プレイヤーが損失の規模や大きさではなく、腕数n$しか知らない、スケールフリーのマルチアームバンド(MAB)問題を考える。
損失ベクトルは l_1,\dots, l_T \in \mathbb{R}^n$ である。
その目的は、後悔を$n$と$l_1,\dots,l_t$の関数に縛ることである。
規則化リーダ(ftrl)アルゴリズムに従うように設計し,mabに対する最初のスケールフリーな後悔保証を提供する。
ログバリア正規化器、重み付き推定器の重要性、適応学習率、適応探索パラメータを使用する。
本稿では,FTRL と Online Mirror Descent (OMD) の残差不等式を,ポテンシャル関数と混合ブレグマンを用いた確率的単純度に基づいて簡易に統一する手法を提案する。
また,Bregman Divergencesの局所ノルム下限を求める新たな手法を開発した。
これらのツールは独立したものかもしれない。
関連論文リスト
- Tangential Randomization in Linear Bandits (TRAiL): Guaranteed Inference and Regret Bounds [1.03590082373586]
本稿では,線形帯域探索アルゴリズムTRAiLの提案と解析を行う。
TraiLは、設計(回帰器)行列の最小固有値によって測定された推論品質の$Omega(sqrtT)$成長を保証する。
我々は,期待された後悔に対して,任意のアルゴリズムに対して$Omega(sqrtT)$ minimax小境界を特徴付ける。
論文 参考訳（メタデータ） (2024-11-19T01:08:13Z) - Linear bandits with polylogarithmic minimax regret [8.97780713904412]
本研究では,未知ベクトルに近づいた単位球上での動作を選択すると,サブガウス雑音パラメータが線形に消滅する線形帯域の雑音モデルについて検討する。
我々は,この問題に対するアルゴリズムを導入し,この最小限の後悔のスケーリングを,時間軸で$log3(T)$,時間軸で$T$として示す。
論文 参考訳（メタデータ） (2024-02-19T10:56:47Z) - Fixed-Budget Best-Arm Identification in Sparse Linear Bandits [69.6194614504832]
固定予算設定下での疎線形包帯のベストアーム識別問題について検討した。
我々は2相アルゴリズムであるLassoとOptimal-Design-(Lasso-OD)をベースとした線形ベストアーム識別を設計する。
我々はラッソODが指数においてほぼ極小であることを示す。
論文 参考訳（メタデータ） (2023-11-01T12:32:17Z) - Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。
トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
論文 参考訳（メタデータ） (2023-03-30T02:51:00Z) - Revisiting Weighted Strategy for Non-stationary Parametric Bandits [82.1942459195896]
本稿では,非定常パラメトリックバンディットの重み付け戦略を再考する。
より単純な重みに基づくアルゴリズムを生成する改良された分析フレームワークを提案する。
我々の新しいフレームワークは、他のパラメトリックバンディットの後悔の限界を改善するのに使える。
論文 参考訳（メタデータ） (2023-03-05T15:11:14Z) - Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Arms [59.8188496313214]
半帯域 (CMAB) について検討し, 半帯域 (CMAB) におけるバッチサイズ (K$) の依存性の低減に着目した。
まず,確率的に引き起こされるアーム(CMAB-T)を用いたCMABの設定に対して,分散を考慮した信頼区間を持つBCUCB-Tアルゴリズムを提案する。
次に,独立アームを用いた非トリガ型CMABの設定に対して,TPVM条件の非トリガ型を利用したSESCBアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-31T13:09:39Z) - Minimax-Optimal Multi-Agent RL in Zero-Sum Markov Games With a
Generative Model [50.38446482252857]
2人プレイのゼロサムマルコフゲームは多エージェント強化学習においておそらく最も基本的な設定である。
我々は,$$ widetildeObiggを用いて,$varepsilon$-approximate Markov NEポリシーを学習する学習アルゴリズムを開発した。
我々は、分散型量の役割を明確にするFTRLに対する洗練された後悔境界を導出する。
論文 参考訳（メタデータ） (2022-08-22T17:24:55Z) - An Experimental Design Approach for Regret Minimization in Logistic
Bandits [26.674062544226636]
ロジスティックな盗賊の最大の課題は、潜在的に大きな問題に依存する定数$kappa$への依存を減らすことである。
そこで本研究では,新しいウォームアップサンプリングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-02-04T21:56:40Z) - Stochastic Bandits with Vector Losses: Minimizing $\ell^\infty$-Norm of
Relative Losses [21.085722900446257]
マルチアームバンディットは、クリック率の最大化を目標とするレコメンデーションシステムに広く適用されている。
本稿では、この状況を複数の損失を伴って、$K$の武器付きバンディットの問題としてモデル化する。
論文 参考訳（メタデータ） (2020-10-15T23:03:35Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。