論文の概要: Near-Optimal Regret for Semi-Bandit Learning of Monotone Stochastic Problems

• arxiv url: http://arxiv.org/abs/2610.24446v1
• Date: Sat, 17 Oct 2026 04:17:23 GMT
• ステータス: 情報取得中
• システム内更新日: 2026-10-20 11:43:31.397925
• Title: Near-Optimal Regret for Semi-Bandit Learning of Monotone Stochastic Problems
• Title（参考訳）: 単調確率問題の半帯域学習における準最適回帰法
• Abstract要約: 本研究は,真の分布が不明な最適化問題に対する最適ポリシーを学習する作業について考察する。 各期間、アルゴリズムは問題に対するポリシーを実行し、半帯域フィードバック、すなわちポリシーによって選択されたランダム変数からのみ新しいサンプルを受け取る。 我々は,預言不平等,Pandoraのボックス,シリーズテスト,knapsack,マッチングなど,大規模なモノトーン問題に対処するアルゴリズムを得る。
• 参考スコア（独自算出の注目度）: 3.329206202900235
• License:
• Abstract: We consider the task of learning an (approximately) optimal policy for stochastic optimization problems where the true distributions are unknown. In each period, the algorithm plays a policy for the stochastic problem and observes semi-bandit feedback, i.e., it only receives new samples from the random variables that were selected by the policy. We obtain an algorithm that works for a large class of ``monotone'' stochastic problems, including prophet inequality, Pandora's box, series testing, stochastic knapsack and stochastic matching. We obtain $\tilde{O}(\sqrt{nkT})$ regret for ``weakly'' monotone problems and $\tilde{O}(\sqrt{nT})$ regret for ``strongly'' monotone problems, where $T$ is the number of periods, $n$ is the problem dimension (number of random variables) and $k$ is the maximum support size of any random variable. This improves over previous regret bounds by a $\sqrt{n}$ factor. In fact, our dependence on $n$ and $T$ is the best-possible due the $Ω(\sqrt{nT})$ lower bound for multi-armed-bandits. Our main technique is the use of Hellinger distance in bounding the ``error'' between the true and learned distributions, and the use of a constant-factor chain rule for the Hellinger distance of dependent random variables.
• Abstract（参考訳）: 真の分布が不明な確率的最適化問題に対する(およそ)最適ポリシーを学習する作業について考察する。 各期間において、アルゴリズムは確率問題に対するポリシーを実行し、半帯域フィードバック、すなわちポリシーによって選択されたランダム変数からのみ新しいサンプルを受け取る。 我々は,預言不等式,Pandoraのボックス,シリーズテスト,確率的knapsack,確率的マッチングなど,‘モノトーン’の確率的問題に対処するアルゴリズムを得る。 我々は ``weakly'' 単調問題に対する $\tilde{O}(\sqrt{nkT})$ regret と ``weakly' 単調問題に対する $\tilde{O}(\sqrt{nT})$ regret を得る。 これにより、以前の後悔境界よりも$\sqrt{n}$ factor で改善される。 実際、$n$ と $T$ への依存は、多武装バンドに対して $Ω(\sqrt{nT})$ が下界であることから、最も有益である。 我々の主な手法は、実数分布と学習した分布の'error' の有界化における Hellinger 距離の利用と、従属確率変数の Hellinger 距離に対する定数要素連鎖則の利用である。

関連論文リスト

• Near-Optimal Regret Bounds for Monotone Stochastic Optimization under Semi-Bandit Feedback [7.234249257243776]
  citetagarwal2026semibanditは、半帯域でのモノトン最適化をオンラインからオフラインに還元する。 citetliu2025は問題固有のアルゴリズムを使って$widetilde O(sqrtnT)$を達成する。
  論文  参考訳（メタデータ） (2026-10-12T19:21:10Z)
• Parameter-Free Interval-Dynamic Regret under Heavy-Tailed Noise [55.29259818039367]
  オンライン凸最適化を1ラウンドに1つの偏りのない下位段階と、未知の有限条件の雑音モーメントであるp$th, $1ple2$で検討する。 長さ$n$の固定区間$I$に対して、学習者は最適な全水平静的レートを含む1+log(T/n)$を達成する。
  論文  参考訳（メタデータ） (2026-09-30T21:03:03Z)
• Near-Optimal Regret in Adversarial Kernel Bandits [50.68324062892194]
  本稿では,各ラウンドにおける損失が任意の有界要素によって誘導される逆カーネルバンドイット問題について検討する。 我々の主な結果は、$widetildeObig(sqrtT, d_*(),log|X|big)$, ここでは$d_*()$は有効次元の広く解釈された概念である。
  論文  参考訳（メタデータ） (2026-05-26T06:10:24Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Semi-Bandit Learning for Monotone Stochastic Optimization [16.921694787482213]
  一般的なオンライン学習アルゴリズムは「モノトーン」問題のクラスのために開発されている。 当社のフレームワークは,預言不平等やPandoraのボックス,単一リソースの収益管理,ポスト価格など,いくつかの基本的な問題に適用しています。
  論文  参考訳（メタデータ） (2023-12-24T07:46:37Z)
• Bandit Algorithms for Prophet Inequality and Pandora's Box [13.709418181148148]
  マルチアーメッド・バンディットモデルにおける預言不等式とPandoraのボックス問題について検討した。 我々の結果は、予言の不平等とPandoraのBoxの両面で、ほぼ最適の$tildeO(mathsfpoly(n)sqrtT)$トータル後悔アルゴリズムを提供する。
  論文  参考訳（メタデータ） (2022-11-16T00:10:35Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  制約付き非線形最適化問題のオンライン統計的推測を考察する。 これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
  論文  参考訳（メタデータ） (2022-05-27T00:34:03Z)
• Variance-Aware Sparse Linear Bandits [64.70681598741417]
  余分な線形包帯に対する最悪のミニマックスは$widetildeThetaleft(sqrtdTright)$である。 ノイズがなく、アクションセットが単位球面である良性設定では、ディビジョン・アンド・コンカーを使用して、$widetildemathcal O(1)$ regretを達成することができる。 我々は,任意の分散対応線形帯域幅アルゴリズムを分散対応線形帯域幅アルゴリズムに変換する汎用フレームワークを開発した。
  論文  参考訳（メタデータ） (2022-05-26T15:55:44Z)
• Smoothed Analysis with Adaptive Adversaries [28.940767013349408]
  オンライン問題に対する新しいアルゴリズムの保証を平滑化解析モデルで証明する。 このモデルでは、敵は各時間に一様分布の$tfrac1sigma$倍の密度関数を持つ入力分布を選択する。 本研究の結果は,アルゴリズムの決定と前回の時間ステップにおける入力の実現に基づいて,入力分布を選択可能な適応的敵に対して成り立っている。
  論文  参考訳（メタデータ） (2021-02-16T20:54:49Z)

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

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