論文の概要: Bandits with Probing: Optimal Regret and the Limits of Winner Feedback
- arxiv url: http://arxiv.org/abs/2609.15248v1
- Date: Mon, 14 Sep 2026 09:07:54 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-16 07:15:06.202147
- Title: Bandits with Probing: Optimal Regret and the Limits of Winner Feedback
- Title（参考訳）: 探索によるバンド:最適回帰と勝者フィードバックの限界
- Abstract要約: アサンプリングは各ラウンドで最大$k$$$n$のアームをプローブし、報酬の最大値を[0,1]$で受け取り、最高の固定アームと競合する。
2つのミニマックス法則を定める。
- 参考スコア（独自算出の注目度）: 0.9915938571870905
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A learner probes at most $k$ of $n$ arms each round, receives the maximum of their rewards in $[0,1]$, and competes with the best fixed arm. When does the probing advantage pay for learning? We determine two minimax laws. Under independent stochastic rewards with winner feedback (the maximum and a winning label), or on arbitrary fixed sequences given a single signed contrast between block maxima, the minimax regret has order $Φ_{n,k}(T)=\min\{\frac{n-k}{n}T,\frac{n-k}{k}\}$, $2\le k<n$. Under winner feedback, both arbitrary joint i.i.d. rewards and fixed sequences have minimax regret of order $R_{n,k}(T)=\frac{n-k}{n}\min\{T,\frac{n+T}{k},\sqrt{\frac{nT}{k}}\}$. Both laws have universal constants and anytime upper bounds. The first reduces regret to a pure coverage cost: same-round contrasts absorb the stability cost, and independence permits exact resampling whose gains fund sample advancement. The second adds a learning cost that becomes comparable to coverage at horizon $n$; beyond $nk$, numerical maxima improve over labels alone. The lower bound allows every adaptive action size.
- Abstract（参考訳）: 学習者は各ラウンドで最大$k$$$n$のアームをプローブし、報酬の最大値を[0,1]$で受け取り、最高の固定アームと競合する。
探索的優位性はいつ学習に役立ちますか?
2つのミニマックス法則を定める。
勝者のフィードバック(最大値と入賞ラベル)を持つ独立した確率的報酬、またはブロックの最大値に1つの符号付きコントラストが与えられた任意の固定列の下では、ミニマックスの後悔は、次の順序を持つ:$\_{n,k}(T)=\min\{\frac{n-k}{n}T,\frac{n-k}{k}\}$, $2\le k<n$。
勝者のフィードバックの下では、任意の結合 i.d. 報酬と固定列は、位数$R_{n,k}(T)=\frac{n-k}{n}\min\{T,\frac{n+T}{k},\sqrt{\frac{nT}{k}}\}$ のミニマックス後悔を持つ。
どちらの法則も普遍定数と任意の上限を持つ。
1つ目は純粋なカバーコストに対する後悔を減らし、同ラウンドのコントラストは安定性のコストを吸収し、独立はファンドのサンプルの進歩を得られる正確な再サンプリングを許可する。
2つめは、水平線$n$のカバレッジに匹敵する学習コストを追加し、$nk$を超えると、ラベルのみよりも数値的な最大値が向上する。
下位境界は、すべての適応的なアクションサイズを許容する。
関連論文リスト
- Adversarial Combinatorial Semi-bandits with Graph Feedback [5.922488908114023]
セミバンドにおいて、学習者は、決定されたアームセットから繰り返し選択し、実現された報酬の合計を受信し、選択された個々のアームの報酬をフィードバックとして観察する。
時間的地平線上での最適後悔は$T$が$widetildeTheta(SsqrtT+sqrtalpha ST)$としてスケールすることを示します。
論文 参考訳（メタデータ） (2025-02-26T05:01:11Z) - Best of Both Worlds: Regret Minimization versus Minimax Play [57.68976579579758]
この結果から,悪用可能な相手からOmega(T)$を得ることができながら,少なくともO(1)$損失のリスクを保証できることが分かる。
論文 参考訳（メタデータ） (2025-02-17T11:04:01Z) - Low-rank Matrix Bandits with Heavy-tailed Rewards [55.03293214439741]
アンダーライン重み付きアンダーラインリワード(LowHTR)を用いたアンダーラインローランク行列バンディットの問題点について検討する。
観測されたペイオフに対するトランケーションと動的探索を利用して,LOTUSと呼ばれる新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-04-26T21:54:31Z) - Adversarial Combinatorial Bandits with Switching Costs [55.2480439325792]
本稿では,各ラウンドで選択したアームのスイッチに対して,切替コストが$lambda$の逆帯域問題について検討する。
ミニマックスの後悔とそれにアプローチするための設計アルゴリズムの限界を低くする。
論文 参考訳（メタデータ） (2024-04-02T12:15:37Z) - Near-optimal Per-Action Regret Bounds for Sleeping Bandits [8.261117235807607]
睡眠中の包帯に対して, 行動毎のほぼ最適な後悔境界を導出する。
合計で$K$、最大で$A$の武器が各ラウンドで$T$以上の場合、最もよく知られている上限は$O(KsqrtTAlnK)$である。
本研究は睡眠専門家のアドバイスで盗賊の設定まで拡張し,その過程でEXP4を一般化する。
論文 参考訳（メタデータ） (2024-03-02T21:22:46Z) - Nearly Minimax Optimal Submodular Maximization with Bandit Feedback [12.28389976959093]
我々は、最大$f(S_*)$と$|S_*| = k$との近似について学習者の後悔を最小限に抑える。
この作業では、$tildeOmega(min_L le k(T2/3 + sqrtn choose k - LT)$ のようにスケールするこの設定に対して、最初の minimax lower bound を確立する。
わずかに制限されたアルゴリズムクラスに対して、$tildeOmega(min_L)の強い後悔の低い境界を証明する。
論文 参考訳（メタデータ） (2023-10-27T20:19:03Z) - BanditQ: Fair Bandits with Guaranteed Rewards [10.74025233418392]
古典的な非レグレットなマルチアームバンディットアルゴリズムは本質的に不公平である。
我々は、後悔と目標レート違反を容認しつつ、目標報酬率を達成する、BanditQと呼ばれる新しいオンラインポリシーを提案する。
提案手法は効率的で,公正な予測問題から標準逆MAB問題へのブラックボックス削減を許容する。
論文 参考訳（メタデータ） (2023-04-11T13:39:47Z) - 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) - Revisiting Simple Regret Minimization in Multi-Armed Bandits [33.88679679593314]
単純な後悔は、最高の腕や$epsilon$-good腕を欠く確率よりもあまり一般的ではない。
本稿では,データ豊かさ (Tge n$) とデータ貧弱さ (T le n$) の両面において,単純な後悔の上限を改良した。
より困難なデータ・ポーア・レシエーションのために、少なくとも1回は各腕をサンプリングすることなく、同じ改善を享受できるブラッケティングSH(BSH)を提案する。
論文 参考訳（メタデータ） (2022-10-30T18:31:03Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。