論文の概要: On the Benefits of Free Exploration for Regret Minimization in Multi-Armed Bandits

• arxiv url: http://arxiv.org/abs/2605.25789v1
• Date: Mon, 25 May 2026 12:36:43 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-26 19:50:20.043205
• Title: On the Benefits of Free Exploration for Regret Minimization in Multi-Armed Bandits
• Title（参考訳）: マルチアーマッドバンドにおけるレギュレット最小化のための自由探索のメリットについて
• Authors: Yunlong Hou, Zixin Zhong, Vincent Y. F. Tan,
• Abstract要約: 我々は,後悔が蓄積する前に,エージェントに自由な探査予算が与えられる,多武装の盗賊問題について検討する。 我々は、この後悔の最小化を自由探索問題で定式化し、自由探査予算が時間軸と対数的にスケールする興味深い体制を特定する。 本稿では,二相保存アルゴリズムUFE-KLUCB-Hを提案する。
• 参考スコア（独自算出の注目度）: 54.384522012368556
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study a stochastic multi-armed bandit problem where an agent is granted a free exploration budget before regret accumulates, a setting not captured by the classic regret minimization or pure exploration paradigms. The goal is to design an adaptive policy that strategically explores the bandit instance in the initial free exploration phase and minimizes the cumulative regret in the subsequent phase. We formalize this regret minimization with free exploration problem and identify an interesting regime where the free exploration budget scales logarithmically with the time horizon. To quantify the amount of regret saved with high probability as a result of the availability of the free exploration phase, we introduce a novel set of policies known as $(α,β)$-probably saving policies. We propose a two-phase, probably saving algorithm, UFE-KLUCB-H, which consists of a principled free exploration policy, UFE, and a history-aware regret minimization policy KLUCB-H. Instance-dependent upper bounds on UFE-KLUCB-H are derived, showing that UFE-KLUCB-H accumulates strictly less regret than policies that do not have access to a free exploration phase. Complementarily, we derive instance-dependent lower bounds based on novel multi-instance perturbation arguments tailored to the free-exploration setting, demonstrating the near-optimality of UFE-KLUCB-H for two-valued bandits. Our upper and lower bounds reveal sharp phase transitions in the accumulated regret depending on the amount of available free exploration. Simulations are conducted to demonstrate that forced exploration and adaptivity in the algorithm lead to greater regret savings.
• Abstract（参考訳）: 本研究では, 後悔が蓄積する前に, エージェントが自由な探索予算を付与される確率的マルチアームバンディット問題, 過去の後悔の最小化や純粋な探索パラダイムによって捉えられていない設定について検討する。 目標は,初期自由探索段階におけるバンドイットのインスタンスを戦略的に探索し,その後の段階における累積的後悔を最小限に抑える適応政策を設計することである。 我々は、この後悔の最小化を自由探索問題で定式化し、自由探査予算が時間軸と対数的にスケールする興味深い体制を特定する。 自由探索フェーズが利用可能になった結果,高い確率で保存された後悔の量を定量化するために,$(α,β)$-probably Saving Policyと呼ばれる新しいポリシーのセットを導入する。 本稿では,二相保存アルゴリズムUFE-KLUCB-Hを提案する。 UFE-KLUCB-Hのインスタンス依存上界が導出され、UFE-KLUCB-Hは自由な探査段階に到達できない政策よりも、完全に後悔の度合いが低いことが示されている。 同時に,2値のバンディットに対するUFE-KLUCB-Hの最適性を示す,新しいマルチインスタンス摂動論に基づいて,インスタンス依存の下位境界を導出する。 我々の上と下の境界は、利用可能な自由探索の量に応じて、蓄積された後悔の中で急激な位相遷移を示す。 シミュレーションにより、アルゴリズムにおける強制的な探索と適応性が、より大きな後悔の節約につながることを示す。

関連論文リスト

• Improved Bounds for Reward-Agnostic and Reward-Free Exploration [5.120675183010349]
  エピソード有限水平マルコフ決定過程における報酬フリーおよび報酬非依存探索について検討する。 Reward-free Exploringは、探索後に明らかになった報酬に対して$$-optimal Policyを有効にすることを目的としており、報奨非依存な探索は、小さな有限クラスから引き出された報酬に対して$-optimalityをターゲットとしている。
  論文  参考訳（メタデータ） (2026-02-18T11:04:15Z)
• EUBRL: Epistemic Uncertainty Directed Bayesian Reinforcement Learning [22.84927928856004]
  疫学的な不確実性は、限られた知識による体系的な不確実性を反映している。 本稿では,ベイジアン強化学習アルゴリズムである$texttEUBRL$を提案する。
  論文  参考訳（メタデータ） (2025-12-17T12:55:05Z)
• Catoni-Style Change Point Detection for Regret Minimization in Non-Stationary Heavy-Tailed Bandits [31.212504858546232]
  ヘビーテールの片側定常バンディット問題に対処する。 重み付き分布に適した新しいカタニスタイル変化点検出戦略を提案する。 本稿では,この変化点検出戦略と楽観的アルゴリズムを組み合わせたロバストCPD-UCBを提案する。
  論文  参考訳（メタデータ） (2025-05-26T14:40:47Z)
• Best Arm Identification with Minimal Regret [55.831935724659175]
  最高の腕識別問題 優雅にアマルガメートは、最小化とBAIを後悔している。 エージェントの目標は、所定の信頼度で最高の腕を特定することである。 二重KL-UCBアルゴリズムは、信頼度がゼロになる傾向があるため、最適性を達成する。
  論文  参考訳（メタデータ） (2024-09-27T16:46:02Z)
• Safe Exploration Incurs Nearly No Additional Sample Complexity for Reward-free RL [43.672794342894946]
  Reward-free reinforcement learning (RF-RL) は、未知の環境を探索するランダムなアクションテイクに依存する。 このような安全な探索要求が、得られた政策の計画における望ましい最適性を達成するために、対応するサンプルの複雑さにどのように影響するかは、いまだ不明である。 本稿では,Safe reWard-frEe ExploraTion (SWEET) フレームワークを提案し,Tabular-SWEET と Low-rank-SWEET というアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-06-28T15:00:45Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。 提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。 初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2021-10-09T21:13:48Z)
• Shortest-Path Constrained Reinforcement Learning for Sparse Reward Tasks [59.419152768018506]
  最適ポリシーは必ずk-SP制約を満たすことを示す。 本研究では,SP制約に違反するポリシーを完全に排除する代わりに,新たなコスト関数を提案する。 また,MiniGrid,DeepMind Lab,Atari,Fetchを用いた実験の結果,提案手法はPPOを著しく改善することが示された。
  論文  参考訳（メタデータ） (2021-07-13T21:39:21Z)
• Temporal Difference Uncertainties as a Signal for Exploration [76.6341354269013]
  強化学習における探索の効果的なアプローチは、最適な政策に対するエージェントの不確実性に依存することである。 本稿では,評価値のバイアスや時間的に矛盾する点を強調した。 本稿では,時間差誤差の分布の導出に依存する値関数の不確かさを推定する手法を提案する。
  論文  参考訳（メタデータ） (2020-10-05T18:11:22Z)
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization [55.937424268654645]
  有界ノルムを持つ関数のブラックボックス最適化問題に対するアルゴリズム非依存な下界を考える。 本稿では, 単純さ, 汎用性, エラー確率への依存性の向上など, 後悔の下位境界を導出するための新しい証明手法を提案する。
  論文  参考訳（メタデータ） (2020-08-20T03:48:14Z)

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

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