Fugu-MT 論文翻訳(概要): A Tight Lower Bound for Non-stochastic Multi-armed Bandits with Expert Advice

論文の概要: A Tight Lower Bound for Non-stochastic Multi-armed Bandits with Expert Advice

arxiv url: http://arxiv.org/abs/2511.00257v1
Date: Fri, 31 Oct 2025 21:01:53 GMT
ステータス: 翻訳完了
システム内更新日: 2025-11-05 16:37:26.695099
Title: A Tight Lower Bound for Non-stochastic Multi-armed Bandits with Expert Advice
Title（参考訳）: エキスパートアドバイザを用いた非確率的マルチアームバンドのタイトな下界
Authors: Zachary Chase, Shinji Ito, Idan Mehalel,
Abstract要約: 古典的非確率的マルチアームバンディットにおけるミニマックス最適後悔を専門的助言問題で決定する。ここで、$K$は腕の数、$N$は専門家の数、$T$は時間軸である。
参考スコア（独自算出の注目度）: 28.32015131406357
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We determine the minimax optimal expected regret in the classic non-stochastic multi-armed bandit with expert advice problem, by proving a lower bound that matches the upper bound of Kale (2014). The two bounds determine the minimax optimal expected regret to be $\Theta\left( \sqrt{T K \log (N/K) } \right)$, where $K$ is the number of arms, $N$ is the number of experts, and $T$ is the time horizon.
Abstract（参考訳）: 我々は、Kale (2014) の上界と一致する下界を証明し、古典的な非確率的マルチアームバンディットにおける最小限の最適後悔を専門家のアドバイス問題で決定する。 2つの境界は、ミニマックス最適後悔を$\Theta\left( \sqrt{T K \log (N/K) } \right)$と決定する。

関連論文リスト

Improved Regret Bounds for Bandits with Expert Advice [16.699381591572163]
我々は、最悪のケースの後悔に対して$sqrtK T ln(N/K)$の下位境界を証明し、そこでは$K$はアクションの数、$N>K$はエキスパートの数、$T$はタイムホライズである。これは、前述した同じ順序の上界と一致し、$sqrtK T (ln N) / (ln K)$の最良の下界を改善する。
論文参考訳（メタデータ） (2024-06-24T17:14:31Z)
Near-optimal Per-Action Regret Bounds for Sleeping Bandits [8.261117235807607]
睡眠中の包帯に対して, 行動毎のほぼ最適な後悔境界を導出する。合計で$K$、最大で$A$の武器が各ラウンドで$T$以上の場合、最もよく知られている上限は$O(KsqrtTAlnK)$である。本研究は睡眠専門家のアドバイスで盗賊の設定まで拡張し,その過程でEXP4を一般化する。
論文参考訳（メタデータ） (2024-03-02T21:22:46Z)
Borda Regret Minimization for Generalized Linear Dueling Bandits [65.09919504862496]
本稿では,ボルダスコアが最も高い項目を識別することを目的とした,デュエルバンディットに対するボルダ後悔最小化問題について検討する。本稿では,多くの既存モデルをカバーする一般化線形デュエルバンドモデルのリッチクラスを提案する。我々のアルゴリズムは$tildeO(d2/3 T2/3)$ regretを達成し、これも最適である。
論文参考訳（メタデータ） (2023-03-15T17:59:27Z)
Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaR [58.40575099910538]
本研究は,リスク許容度が$tau$のCVaR(Conditional Value at Risk)の目的に着目し,リスクに敏感な強化学習(RL)について検討する。ミニマックスCVaRの後悔率は$Omega(sqrttau-1AK)$で、$A$はアクションの数、$K$はエピソード数である。我々は,このアルゴリズムが連続性仮定の下で$widetilde O(tau-1sqrtSAK)$の最適後悔を達成し,一般に近似することを示す。
論文参考訳（メタデータ） (2023-02-07T02:22:31Z)
Online Learning and Bandits with Queried Hints [28.270453093780382]
従来のオンライン学習とマルチアーム・バンディット(MAB)の問題について考察する。残差が指数関数的に時間的地平線に依存するアルゴリズムを導出する。オンライン線形および凸最適化のための時間非依存の後悔境界を達成するために,$k=2$ suffices を用いて探索を行うことが示される。
論文参考訳（メタデータ） (2022-11-04T18:41:08Z)
Nonstochastic Bandits with Infinitely Many Experts [1.7188280334580197]
無限に多くの専門家と非確率的盗賊の問題を考察する。有限個の専門家に対して、正しい専門家ランキングの推測を可能にするExp4.Pの変種を提案する。そして、この変種を無限に多くの専門家に作用するメタアルゴリズムに組み込む。
論文参考訳（メタデータ） (2021-02-09T22:42:36Z)
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)
Adversarial Dueling Bandits [85.14061196945599]
本稿では,反逆デュエルバンドにおける後悔の問題を紹介する。学習者は、繰り返し一対のアイテムを選択し、このペアに対する相対的な二項利得フィードバックのみを観察しなければならない。我々の主な成果は、EmphBorda-winnerの1組の$K$アイテムと比較して、T$ラウンド後悔するアルゴリズムです。
論文参考訳（メタデータ） (2020-10-27T19:09:08Z)
Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文参考訳（メタデータ） (2020-06-17T22:32:19Z)

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