論文の概要: 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 を用いたマルチアーマッドバンド
- 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} の利点の完全な評価を与える。
関連論文リスト
- Breaking the Total Variance Barrier: Sharp Sample Complexity for Linear Heteroscedastic Bandits with Fixed Action Set [93.03556214432615]
本稿では,学習過程を通じて動作セットをプレフィックスするヘテロセシダスティックノイズによる線形帯域問題を再検討する。
本稿では,情報ゲインを最大化するアクションを積極的に探求する,大規模アクション集合のための分散適応アルゴリズムのtexttVAEEを提案する。
音素平均依存率が避けられないことを示す固定作用集合に対して、ほぼ一致する下界を確立する。
論文 参考訳（メタデータ） (2026-07-26T14:24:34Z) - Batched Stochastic Linear Bandits with 1-Bit Communication Constraints [27.994941928937802]
制限なしの線形バンディットに対するミニマックスの後悔にほぼ一致するように、バッチ毎のフィードバックは1ビットに1つしかありません。
我々は、$G$-elimination設計と1ビット平均推定に基づく2つの位相除去アルゴリズムを開発した。
論文 参考訳（メタデータ） (2026-05-29T08:17:31Z) - Tighter Regret Bounds for Contextual Action-Set Reinforcement Learning [17.131069269126776]
固定報酬と遷移関数を用いて,エピソード依存の許容アクションセットを用いて,エピソード強化学習について検討した。
エピソードごとの最適値に対して累積後悔(sum_k=1K[V*,Mk - Vk,Mk]$)で評価する。
MVPアルゴリズムが自然にこのフレームワークに拡張され、強力な理論的保証を享受していることを示す。
論文 参考訳（メタデータ） (2026-05-15T07:28:42Z) - Follow-the-Perturbed-Leader Approaches Best-of-Both-Worlds for the m-Set Semi-Bandit Problems [18.74680577173648]
我々は、学習者が$m$の腕から$m$の腕を正確に選択する、$m$セット半帯域問題の一般的な場合を考える。
また, Fr'echet 摂動を持つFTPL は, 対向的な設定で, $mathcalO(sqrtnm(sqrtdlog(d)+m5/6)$ をほぼ最適に再現できることを示す。
論文 参考訳（メタデータ） (2025-04-09T22:07:01Z) - 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) - Sleeping Combinatorial Bandits [15.004764451770441]
睡眠帯域設定においてよく知られたCUCBアルゴリズムを適用し,それをCSUCBと呼ぶ。
穏やかな条件下では、CSUCBアルゴリズムが$O(sqrtT log (T)$ instance-dependent regret guaranteeを達成することを証明します。
我々の結果は極めて一般的なものであり、非付加的な報酬関数、揮発性アームの可用性、引くべきベースアームの変動数など、実用的な応用によって生じる一般的な環境下で維持されます。
論文 参考訳（メタデータ） (2021-06-03T06:49:44Z) - 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) - Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy [71.17938026619068]
我々は、腕の総数が膨大であることができるトップ$ k$極端な文脈的包帯問題を研究します。
まず,Inverse Gap Weighting戦略を用いて,非極端に実現可能な設定のアルゴリズムを提案する。
我々のアルゴリズムは、$O(ksqrt(A-k+1)T log (|mathcalF|T))$である。
論文 参考訳（メタデータ） (2021-02-15T19:10:52Z) - Adversarial Dueling Bandits [85.14061196945599]
本稿では,反逆デュエルバンドにおける後悔の問題を紹介する。
学習者は、繰り返し一対のアイテムを選択し、このペアに対する相対的な二項利得フィードバックのみを観察しなければならない。
我々の主な成果は、EmphBorda-winnerの1組の$K$アイテムと比較して、T$ラウンド後悔するアルゴリズムです。
論文 参考訳（メタデータ） (2020-10-27T19:09:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。