Fugu-MT 論文翻訳(概要): Adaptation to the Range in $K$-Armed Bandits

論文の概要: Adaptation to the Range in $K$-Armed Bandits

arxiv url: http://arxiv.org/abs/2006.03378v3
Date: Wed, 15 Jun 2022 10:34:03 GMT
ステータス: 処理完了
システム内更新日: 2022-11-25 04:18:34.760376
Title: Adaptation to the Range in $K$-Armed Bandits
Title（参考訳）: k$-armed banditsにおける範囲への適応
Authors: H\'edi Hadiji, Gilles Stoltz
Abstract要約: 我々は、[m,M]$の範囲でサポートされている有界分布に付随する$K$アームの帯域問題を考える。分布依存型と分布非依存型との新たなトレードオフが発生し、典型的な$ln T$と$sqrtT$バウンドを同時に達成することができない。
参考スコア（独自算出の注目度）: 1.14219428942199
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We consider stochastic bandit problems with $K$ arms, each associated with a bounded distribution supported on the range $[m,M]$. We do not assume that the range $[m,M]$ is known and show that there is a cost for learning this range. Indeed, a new trade-off between distribution-dependent and distribution-free regret bounds arises, which prevents from simultaneously achieving the typical $\ln T$ and $\sqrt{T}$ bounds. For instance, a $\sqrt{T}$}distribution-free regret bound may only be achieved if the distribution-dependent regret bounds are at least of order $\sqrt{T}$. We exhibit a strategy achieving the rates for regret indicated by the new trade-off.
Abstract（参考訳）: 我々は,$k$ arms の確率的バンドイット問題を考察し,それぞれ$[m,m]$ の範囲でサポートされている境界分布に関連付ける。私たちは、$[m,M]$が知られていると仮定せず、この範囲を学ぶのにコストがかかることを示す。実際、分布依存と分布なしの後悔の境界の間の新たなトレードオフが発生し、典型的な$\ln t$と$\sqrt{t}$バウンドを同時に達成することを防ぐ。例えば、$\sqrt{T}$}distribution-free regret bound は、分布依存後悔境界が少なくとも位数$\sqrt{T}$であるときのみ達成できる。我々は、新たなトレードオフによって示される後悔の利率を達成する戦略を示す。

関連論文リスト

Near-optimal Per-Action Regret Bounds for Sleeping Bandits [8.261117235807607]
睡眠中の包帯に対して, 行動毎のほぼ最適な後悔境界を導出する。合計で$K$、最大で$A$の武器が各ラウンドで$T$以上の場合、最もよく知られている上限は$O(KsqrtTAlnK)$である。本研究は睡眠専門家のアドバイスで盗賊の設定まで拡張し,その過程でEXP4を一般化する。
論文参考訳（メタデータ） (2024-03-02T21:22:46Z)
Combinatorial Bandits for Maximum Value Reward Function under Max Value-Index Feedback [9.771002043127728]
本稿では,最大値報酬関数に対する最大値と指数フィードバックに基づくマルチアームバンディット問題を考察する。有限なサポートを持つ任意の分布にしたがって、アーム結果を持つ問題インスタンスに対して、アルゴリズムを提案し、後悔の束縛を与える。我々のアルゴリズムは、$O(((k/Delta)log(T))$ distribution-dependent と $tildeO(sqrtT)$ distribution-independent regret を達成する。
論文参考訳（メタデータ） (2023-05-25T14:02:12Z)
First- and Second-Order Bounds for Adversarial Linear Contextual Bandits [22.367921675238318]
我々は,K$の腕に付随する損失関数を制限なく時間とともに変化させることができる,逆線形文脈帯域設定を考える。 V_T$ または $L_T*$ は$T$ よりもかなり小さい可能性があるため、環境が比較的良心的であれば、最悪の場合の後悔よりも改善される。
論文参考訳（メタデータ） (2023-05-01T14:00:15Z)
Variance-Aware Sparse Linear Bandits [64.70681598741417]
余分な線形包帯に対する最悪のミニマックスは$widetildeThetaleft(sqrtdTright)$である。ノイズがなく、アクションセットが単位球面である良性設定では、ディビジョン・アンド・コンカーを使用して、$widetildemathcal O(1)$ regretを達成することができる。我々は,任意の分散対応線形帯域幅アルゴリズムを分散対応線形帯域幅アルゴリズムに変換する汎用フレームワークを開発した。
論文参考訳（メタデータ） (2022-05-26T15:55:44Z)
An Experimental Design Approach for Regret Minimization in Logistic Bandits [26.674062544226636]
ロジスティックな盗賊の最大の課題は、潜在的に大きな問題に依存する定数$kappa$への依存を減らすことである。そこで本研究では,新しいウォームアップサンプリングアルゴリズムを提案する。
論文参考訳（メタデータ） (2022-02-04T21:56:40Z)
On Submodular Contextual Bandits [92.45432756301231]
作用が基底集合の部分集合であり、平均報酬が未知の単調部分モジュラ函数によってモデル化されるような文脈的包帯の問題を考える。 Inverse Gap Weighting 戦略により,提案アルゴリズムは推定関数の局所的最適度を効率よくランダム化することを示す。
論文参考訳（メタデータ） (2021-12-03T21:42:33Z)
Bandit Phase Retrieval [45.12888201134656]
この問題におけるminimax累積後悔は$smashtilde Theta(d sqrtn)$であることを証明する。また、minimax の単純な後悔は $smashtilde Theta(d / sqrtn)$ であり、これは適応アルゴリズムによってのみ達成可能であることを示す。
論文参考訳（メタデータ） (2021-06-03T08:04:33Z)
Combinatorial Bandits without Total Order for Arms [52.93972547896022]
セット依存報酬分布を捕捉し、武器の合計順序を仮定しない報酬モデルを提案する。我々は、新しい後悔分析を開発し、$Oleft(frack2 n log Tepsilonright)$ gap-dependent regret boundと$Oleft(k2sqrtn T log Tright)$ gap-dependent regret boundを示す。
論文参考訳（メタデータ） (2021-03-03T23:08:59Z)
Variance-Aware Confidence Set: Variance-Dependent Bound for Linear Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
線形バンドイットと線形混合決定プロセス(mdp)に対する分散認識信頼セットの構築方法を示す。線形バンドイットに対しては、$d を特徴次元とする$widetildeo(mathrmpoly(d)sqrt1 + sum_i=1ksigma_i2) が成り立つ。線形混合 MDP に対し、$widetildeO(mathrmpoly(d)sqrtK)$ regret bound を得る。
論文参考訳（メタデータ） (2021-01-29T18:57:52Z)
Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals [49.60752558064027]
ガウス境界の下では、半空間とReLUを不可知的に学習する基本的な問題について検討する。我々の下限は、これらのタスクの現在の上限が本質的に最良のものであるという強い証拠を与える。
論文参考訳（メタデータ） (2020-06-29T17:10:10Z)
Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文参考訳（メタデータ） (2020-06-17T22:32:19Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。