論文の概要: Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity

• arxiv url: http://arxiv.org/abs/2609.38659v2
• Date: Thu, 01 Oct 2026 03:05:49 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-03 01:19:23.539605
• Title: Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity
• Title（参考訳）: 複数の最適アームを持つバンド:ミニマックスレグレットと非適応性
• Abstract要約: 我々は,複数の最適な腕を持つマルチアーム・バンディット(MAB)について検討し,実際的な意思決定問題の多くが複数の正解を許容しているという事実に動機づけられた。 たとえば$tildeOBig(fracK-AsqrtKAsqrtT Big)$ minimax regret, where $T$ is the total number of interaction and $tilde O(cdot)$ drops all constant and logarithmic factors。
• 参考スコア（独自算出の注目度）: 54.77408659142336
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study multi-armed bandits (MAB) with multiple optimal arms, motivated by the fact that many practical decision making problems admit multiple correct answers. For $K$-armed bandits with $A$ optimal arms, we first provide a sharper analysis of previous sub-sampling algorithms (De Heide et al., 2021; Zhu and Nowak, 2020), establishing a $\tilde{O}\Big(\frac{K-A}{\sqrt{KA}}\sqrt{T} \Big)$ minimax regret, where $T$ is the total number of interactions and $\tilde O(\cdot)$ drops all constant and logarithmic factors, improving the previous $\tilde{O}(\sqrt{KT/A})$ regret. We then provide a matching lower bound up to logarithmic factors, indicating that our established rate is nearly minimax-optimal. We further show that the knowledge of $A$ up to $\tilde{O}(1)$ factors is necessary to achieve near-optimal regret, as near-optimal algorithms for one number of optimal arms must incur substantially larger regret than optimal regret for a smaller number. Overall, our results provide a comprehensive minimax characterization of $K$-armed bandits with $A$ over the entire range of $1 \leq A \leq K-1$.
• Abstract（参考訳）: 我々は,複数の最適な腕を持つマルチアーム・バンディット(MAB)について検討し,実際的な意思決定問題の多くが複数の正解を許容しているという事実に動機づけられた。 A$の最適な腕を持つ$K$武装の盗賊に対しては、まず以前のサブサンプリングアルゴリズム(De Heide et al , 2021; Zhu and Nowak, 2020)のよりシャープな分析を行い、$\tilde{O}\Big(\frac{K-A}{\sqrt{KA}}\sqrt{T} \Big)$ minimax regret, where $T$ is the total number of interaction and $\tilde O(\cdot)$ drops all constant and logarithmic factors, improve the $\tilde{O}(\sqrt{KT/A})$ regretを設定します。 次に、対数的因子までの一致した下限を提示し、確立された速度が極小最適に近いことを示す。 A$から$\tilde{O}(1)までの知識は、1つの最適なアームのほぼ最適アルゴリズムが、より少ない数の最適後悔よりもはるかに大きな後悔を起こさなければならないため、ほぼ最適後悔を達成するために必要である。 全体として、我々の結果は、$K$の武器付きバンディットと$A$の全範囲の$1 \leq A \leq K-1$の包括的ミニマックス特性を提供する。

関連論文リスト

• Does 1/2-Tsallis-INF Also Work Well for Best-Arm Identification? [11.223878908981725]
  1/2$-Tsallis-INFは、標準的なFTRLアルゴリズムである。 盗賊の対数的擬似回帰を達成しつつ、敵の盗賊の最小限の後悔を保ちながら達成する。 これは自然な疑問を提起する:同じアルゴリズムは、追加の探索なしに、最高の腕を確実に特定できるのか?
  論文  参考訳（メタデータ） (2026-08-15T18:38:36Z)
• Regret Analysis of Sleeping Competing Bandits [0.2291770711277359]
  本稿では, 合理的な仮定の下で, $mathrmOleft(NKlog T_i/2right)$の後悔境界を同時に達成するアルゴリズムを提案する。 また、同じ仮定で$mathrmleft(N(K-N+1)log T_i/2 right)$の後悔の低い下界も提供する。
  論文  参考訳（メタデータ） (2026-03-20T07:11:28Z)
• p-Mean Regret for Stochastic Bandits [52.828710025519996]
  単純で統一された UCB ベースのアルゴリズムを導入し、新しい$p$-mean の後悔境界を実現する。 我々の枠組みは、特別な場合として、平均的な累積的後悔とナッシュ後悔の両方を包含する。
  論文  参考訳（メタデータ） (2024-12-14T08:38:26Z)
• 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)
• Bandits with many optimal arms [68.17472536610859]
  最適アームの割合は$p*$、最適アームとサブ最適化アームの間の最小平均ギャップは$Delta$と書きます。 我々は,累積的後悔設定と最良腕識別設定の両方において最適な学習率を特徴付ける。
  論文  参考訳（メタデータ） (2021-03-23T11:02:31Z)
• 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)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。