論文の概要: Finite-Time Regret Analysis of Retry-Aware Bandits

• arxiv url: http://arxiv.org/abs/2605.20854v1
• Date: Wed, 20 May 2026 07:44:43 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-21 19:19:56.5574
• Title: Finite-Time Regret Analysis of Retry-Aware Bandits
• Title（参考訳）: Retry-Aware Banditsの有限時間レギュレット解析
• Authors: Bingkui Tong, Junpei Komiyama, Soichiro Nishimori, Paavo Parmas,
• Abstract要約: 複数の試行において最良の結果を評価するために,再試行を意識した目的によって動機付けられた帯域幅アルゴリズムについて検討する。 後部の腕の値が与えられた場合、ReMaxはサンプリング分布を選択し、後部の最大報酬を$M$仮想引き数で最大化する。
• 参考スコア（独自算出の注目度）: 8.812244373657764
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study a stochastic bandit algorithm motivated by retry-aware objectives that value the best outcome among multiple attempts, such as pass@$k$ and max@$k$. Given a posterior over arm values, ReMax chooses a sampling distribution that maximizes the posterior expected maximum reward over $M$ virtual draws. Although this objective was introduced in reinforcement learning as an exploration mechanism under uncertainty, its regret properties in bandit problems have remained unclear. For Gaussian rewards and the first nontrivial case $M=2$, we characterize the optimal ReMax distribution through an expected-improvement balance condition and prove the first sublinear regret bound for ReMax. Our analysis separates the usual saturation behavior of suboptimal arms from a ReMax-specific underestimation effect, in which the optimal arm may be sampled too rarely after an unfavorable estimate. This explains why ReMax can be more exploitative than Thompson sampling (TS) and why its regret analysis is technically delicate. Experiments support this picture: ReMax often outperforms KL-UCB and Thompson sampling under mild underestimation, while posterior-variance scaling empirically mitigates severe underestimation.
• Abstract（参考訳）: 本稿では,pass@$k$ や max@$k$ など,複数の試行において最高の結果が期待できる確率的帯域幅アルゴリズムについて検討する。 後部の腕の値が与えられた場合、ReMaxはサンプリング分布を選択し、後部の最大報酬を$M$仮想引き数で最大化する。 この目的は, 不確実性下での探索機構として強化学習に導入されたが, バンドイット問題における後悔の特性はいまだに不明である。 ガウスの報奨と最初の非自明な$M=2$の場合、期待される改善バランス条件を通して最適なReMax分布を特徴づけ、ReMaxに対する最初の部分線型後悔を証明します。 本分析では, 最適腕の飽和挙動をReMax比の過小評価効果と区別し, 好ましくない推定の後, 最適な腕の標本化はめったに行われないことを示した。 このことは、なぜReMaxがトンプソンサンプリング(TS)よりも悪用できるのか、またその後悔の分析が技術的に繊細なのかを説明する。 ReMaxはKL-UCBとトンプソンサンプリングを軽度の過小評価で上回り、後方分散スケーリングは重度の過小評価を実証的に軽減する。

関連論文リスト

• Theoretical Limits of Language Model Alignment [9.45142272392467]
  言語モデル(LM)アライメントは、ベースモデルの能力を保ちながら、人間の好みを反映するモデル出力を改善する。 最も一般的なアライメントアプローチは、(i)強化学習であり、KL分割制約の下で期待される報酬を最大化する。 固定KL分割予算に対する最大期待報酬利得を導出することにより、KL正規化アライメントの情報理論的限界を特徴づける。
  論文  参考訳（メタデータ） (2026-05-08T01:32:22Z)
• Reinforcement Learning from Multi-Source Imperfect Preferences: Best-of-Both-Regimes Regret [71.69884486156359]
  我々は, 累積的不完全化予算を用いて, エンフルティソースの不完全性選好からエピソードRLを考察した。 我々は,最良な登録行動を示す,後悔$tildeO(sqrtK/M+)$の統一アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-03-20T19:34:53Z)
• Decision from Suboptimal Classifiers: Excess Risk Pre- and Post-Calibration [52.70324949884702]
  バッチ二分決定における近似的後続確率を用いた余剰リスクの定量化を行う。 我々は、再校正のみが後悔のほとんどに対処する体制と、後悔が集団的損失に支配される体制を識別する。 NLP実験では、これらの量によって、より高度なポストトレーニングの期待値が運用コストに値するかどうかが分かる。
  論文  参考訳（メタデータ） (2025-03-23T10:52:36Z)
• Continuous K-Max Bandits [54.21533414838677]
  我々は、連続的な結果分布と弱い値-インデックスフィードバックを持つ、$K$-Maxのマルチアームバンディット問題について検討する。 この設定は、レコメンデーションシステム、分散コンピューティング、サーバスケジューリングなどにおいて重要なアプリケーションをキャプチャします。 我々の重要な貢献は、適応的な離散化とバイアス補正された信頼境界を組み合わせた計算効率の良いアルゴリズムDCK-UCBである。
  論文  参考訳（メタデータ） (2025-02-19T06:37:37Z)
• Combinatorial Bandits for Maximum Value Reward Function under Max Value-Index Feedback [9.771002043127728]
  本稿では,最大値報酬関数に対する最大値と指数フィードバックに基づくマルチアームバンディット問題を考察する。 有限なサポートを持つ任意の分布にしたがって、アーム結果を持つ問題インスタンスに対して、アルゴリズムを提案し、後悔の束縛を与える。 我々のアルゴリズムは、$O(((k/Delta)log(T))$ distribution-dependent と $tildeO(sqrtT)$ distribution-independent regret を達成する。
  論文  参考訳（メタデータ） (2023-05-25T14:02:12Z)
• Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits [88.21288104408556]
  本研究では,指数関数族バンドイットに対するトンプソンサンプリング (TS) アルゴリズムの遺残について検討する。 最適な腕の過小評価を避けるために,新しいサンプリング分布を用いたトンプソンサンプリング(Expulli)を提案する。
  論文  参考訳（メタデータ） (2022-06-07T18:08:21Z)
• Online nonparametric regression with Sobolev kernels [99.12817345416846]
  我々は、ソボレフ空間のクラス上の後悔の上限を$W_pbeta(mathcalX)$, $pgeq 2, beta>fracdp$ とする。 上界は minimax regret analysis で支えられ、$beta> fracd2$ または $p=infty$ の場合、これらの値は(本質的に)最適である。
  論文  参考訳（メタデータ） (2021-02-06T15:05:14Z)
• Optimal Algorithms for Stochastic Multi-Armed Bandits with Heavy Tailed Rewards [24.983866845065926]
  我々は、重い尾の報酬を持つマルチアームのバンディットを考えており、そのp$-thのモーメントは、定数$nu_p$が1pleq2$である。 本稿では,従来の情報として$nu_p$を必要としない新しいロバストな推定器を提案する。 提案した推定器の誤差確率は指数関数的に高速に減衰することを示す。
  論文  参考訳（メタデータ） (2020-10-24T10:44:02Z)
• Lenient Regret for Multi-Armed Bandits [72.56064196252498]
  エージェントが順番に行動を選択し、その行動に対する報酬を観察するマルチアーマッド・バンディット(MAB)問題を考察する。 アルゴリズムの大多数は、後悔、すなわち最高の行動の報酬とエージェントの行動の累積的な差を最小化しようとするが、この基準は望ましくない結果をもたらすかもしれない。 我々は、いくつかの$epsilon$よりも小さな最適性ギャップを無視した、より寛大で寛大で後悔すべき基準を提案する。
  論文  参考訳（メタデータ） (2020-08-10T08:30:52Z)
• A General Theory of the Stochastic Linear Bandit and Its Applications [8.071506311915398]
  本稿では,線形バンディット問題に対する一般解析フレームワークとアルゴリズム群を紹介する。 予測における最適化という新たな概念は、OFULの過剰探索問題を減少させるSieeved greedy(SG)と呼ばれる新しいアルゴリズムを生み出します。 SGが理論的に最適であることを示すことに加えて、実験シミュレーションにより、SGはgreedy、OFUL、TSといった既存のベンチマークよりも優れていることが示された。
  論文  参考訳（メタデータ） (2020-02-12T18:54:41Z)

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

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