論文の概要: Multi-Armed Bandits With Best-Action Queries

• arxiv url: http://arxiv.org/abs/2605.08287v1
• Date: Fri, 08 May 2026 08:14:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-12 23:28:49.532654
• Title: Multi-Armed Bandits With Best-Action Queries
• Title（参考訳）: Best-Action Queries を用いたマルチアーマッドバンド
• Authors: Francesco Bacchiocchi, Matteo Castiglioni, Alberto Marchesi, Francesco Emanuele Stradi,
• Abstract要約: Emphbest-action queryを併用したEmphmulti-armed bandits(MABs)の検討 ベストアクションクエリは、最適な$widetildemathcalO(sqrtT)後悔を$widetildemathcalO(minT/k,sqrtT)$に還元する。
• 参考スコア（独自算出の注目度）: 29.740898640511336
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study \emph{multi-armed bandits} (MABs) augmented with \emph{best-action queries}, in which the learner may additionally query an oracle that reveals the best arm in the current round. This setting was recently characterized by Russo et al. [2024] in the \emph{full-feedback} model, where the learner observes the rewards of all arms after each round. They show that, in both \emph{stochastic} and \emph{adversarial} environments, $k$ best-action queries reduce the optimal $\widetilde{\mathcal{O}}(\sqrt{T})$ regret to $\widetilde{\mathcal{O}}(\min\{T/k,\sqrt{T}\})$. Whether this improvement extends to the more realistic \emph{bandit-feedback} model -- where the learner observes only the reward of the played arm -- was left as an open problem. We fully resolve this question. When rewards are stochastic but correlated among arms, we show that the full-feedback result does not carry over: any algorithm must incur regret at least $Ω(\sqrt{T-k})$. This lower bound directly extends to adversarial environments. On the positive side, we show that $\widetilde{\mathcal{O}}(\min\{T/k,\sqrt{T-k}\})$ regret is still achievable when rewards are stochastic and i.i.d., and establish a matching lower bound, up to logarithmic factors. Together, these results provide a complete characterization of the benefits of \emph{best-action queries} in the \emph{bandit-feedback} model.
• Abstract（参考訳）: そこで,本研究では,学習者が現在のラウンドで最高の腕を明らかにするオラクルに問い合わせることのできる,‘emph{best-action query} を付加した 'emph{multi-armed bandits} (MABs) について検討する。 この設定は、学習者が各ラウンド後のすべての腕の報酬を観察する 'emph{full-feedback} モデルでRusso et al [2024] によって最近特徴づけられた。 それらは、 \emph{stochastic} と \emph{adversarial} の両方の環境で、$k$ ベストアクションクエリは最適な $\widetilde{\mathcal{O}}(\sqrt{T})$ regret to $\widetilde{\mathcal{O}}(\min\{T/k,\sqrt{T}\})$ を減少させる。 この改善がより現実的な 'emph{bandit-feedback} モデルにまで拡大するかどうか – 学習者はプレーアームの報酬のみを観察する – がオープンな問題として残された。 私たちはこの問題を完全に解決する。 報酬が確率的だが腕の間で相関している場合、全フィードバックの結果は継続しない:任意のアルゴリズムは少なくとも$Ω(\sqrt{T-k})$を後悔しなければならない。 この下界は直接敵の環境に広がる。 正の面では、$\widetilde{\mathcal{O}}(\min\{T/k,\sqrt{T-k}\})$ regret は、報酬が確率的、すなわち、対数的要因まで一致する下界を確立するときにも達成可能であることを示す。 これらの結果と共に、これらの結果は \emph{bandit-feedback} モデルにおける \emph{best-action query} の利点の完全な評価を与える。

関連論文リスト

• Adversarial Combinatorial Semi-bandits with Graph Feedback [5.922488908114023]
  セミバンドにおいて、学習者は、決定されたアームセットから繰り返し選択し、実現された報酬の合計を受信し、選択された個々のアームの報酬をフィードバックとして観察する。 時間的地平線上での最適後悔は$T$が$widetildeTheta(SsqrtT+sqrtalpha ST)$としてスケールすることを示します。
  論文  参考訳（メタデータ） (2025-02-26T05:01:11Z)
• Communication-Constrained Bandits under Additive Gaussian Noise [111.06688156723018]
  クライアントが学習者にコミュニケーション制約のあるフィードバックを提供する分散マルチアームバンディットについて検討する。 我々は、この下限を小さな加法係数にマッチさせるマルチフェーズ帯域幅アルゴリズム、$mathtUEtext-UCB++$を提案する。
  論文  参考訳（メタデータ） (2023-04-25T09:31:20Z)
• Near-Optimal $\Phi$-Regret Learning in Extensive-Form Games [85.78272987312343]
  我々は、効率よく非結合な学習力学を確立し、各プレイヤーのトリガー後悔は、プレイの繰り返しの後に$O(log T)$として成長する。 これにより、これまでよく知られていた$O(T1/4)$よりも指数関数的に改善される。
  論文  参考訳（メタデータ） (2022-08-20T20:48:58Z)
• Uncoupled Learning Dynamics with $O(\log T)$ Swap Regret in Multiplayer Games [121.50979258049135]
  我々は、すべてのプレイヤーが、時空不変の学習速度で我々のダイナミクスに従うとき、時間$T$までの時空二階パス長は、$O(log T)$で有界であることを示す。 提案する学習力学は, 直観的正規化学習と, 自己一致障壁を併用した新しい学習手法である。
  論文  参考訳（メタデータ） (2022-04-25T03:20:16Z)
• 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)
• Adversarial Dueling Bandits [85.14061196945599]
  本稿では,反逆デュエルバンドにおける後悔の問題を紹介する。 学習者は、繰り返し一対のアイテムを選択し、このペアに対する相対的な二項利得フィードバックのみを観察しなければならない。 我々の主な成果は、EmphBorda-winnerの1組の$K$アイテムと比較して、T$ラウンド後悔するアルゴリズムです。
  論文  参考訳（メタデータ） (2020-10-27T19:09:08Z)

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

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