論文の概要: Near-Optimal Regret Bounds for Monotone Stochastic Optimization under Semi-Bandit Feedback

• arxiv url: http://arxiv.org/abs/2610.17320v1
• Date: Mon, 12 Oct 2026 19:21:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-18 02:13:37.408175
• Title: Near-Optimal Regret Bounds for Monotone Stochastic Optimization under Semi-Bandit Feedback
• Title（参考訳）: 半帯域フィードバック下でのモノトーン確率最適化のための近接最適回帰境界
• Abstract要約: citetagarwal2026semibanditは、半帯域でのモノトン最適化をオンラインからオフラインに還元する。 citetliu2025は問題固有のアルゴリズムを使って$widetilde O(sqrtnT)$を達成する。
• 参考スコア（独自算出の注目度）: 7.234249257243776
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Stochastic optimization models sequential decision-making under uncertainty, typically assuming known input distributions. When these distributions are unknown, \citet{agarwal2026semibandit} give an online-to-offline reduction for monotone stochastic optimization under semi-bandit feedback, where only probed variables are observed. Its expected regret relative to the offline guarantee is $\widetilde O(n\sqrt T)$, where $n$ is the number of variables and $T$ the horizon. For optimal stopping and Pandora's box, \citet{liu2025improved} achieve $\widetilde O(\sqrt{nT})$ using problem-specific algorithms. \emph{Can a general online-to-offline reduction achieve this improved rate?} We give such a reduction for strongly monotone stochastic optimization, answering the corresponding open question. Strong monotonicity is defined relative to the chosen offline algorithm. Our oracle-efficient reduction achieves $\widetilde O(\sqrt{nT})$ expected regret while preserving approximation guarantees for oracles satisfying the same condition. It combines Bernstein-type optimistic distribution estimates with a Hellinger stability bound for adaptive policy transcripts, aggregating squared marginal errors weighted by the executed policy's probing probabilities. The rate is optimal up to logarithmic factors for $T\ge n$, even under full feedback. Under monotonicity and uniformly bounded coordinate-wise variation, the same algorithm achieves $\widetilde O(n^{3/4}\sqrt T)$ expected approximation regret, improving the previous linear dependence on $n$. The exponent $3/4$ is sharp for its ordinary regret over instances and exact oracle choices. Our framework applies to prophet inequality, Pandora's box, best-of-$K$ selection, stochastic knapsack, stochastic orienteering, and stochastic submodular maximization.
• Abstract（参考訳）: 確率最適化は、一般に既知の入力分布を仮定して、不確実性の下でのシーケンシャルな意思決定をモデル化する。 これらの分布が未知のとき、 \citet{agarwal2026semibandit} は半帯域フィードバックの下で単調確率最適化をオンラインからオフラインに還元する。 オフライン保証に対する後悔は$\widetilde O(n\sqrt T)$であり、$n$は変数の数、$T$は地平線である。 最適な停止とPandoraのボックスのために、 \citet{liu2025improved} は問題固有のアルゴリズムを使って $\widetilde O(\sqrt{nT})$ を達成する。 一般的なオンラインとオフラインの削減は、この改善率を達成するだろうか? } 強い単調確率最適化に対して,対応する開解問題に答えて,そのような削減を与える。 強い単調性は、選択されたオフラインアルゴリズムに対して定義される。 我々のオラクル効率の低下は、同じ条件を満たすオラクルの近似保証を保ちながら、期待された後悔を$\widetilde O(\sqrt{nT})$にします。 これは、ベルンシュタイン型の楽観的な分布推定と、適応的なポリシーの書き起こしに縛られたヘリンジャー安定性を組み合わせ、実行されたポリシーの確率によって重み付けられた2乗の辺縁誤差を集約する。 この率は、完全なフィードバックの下でさえも、$T\ge n$の対数係数に最適である。 単調性と一様有界な座標偏移の下で、同じアルゴリズムは$\widetilde O(n^{3/4}\sqrt T)$予想近似の後悔を達成し、以前の$n$への線形依存を改善した。 3/4ドル(約3万4000円)は、例と正確なオラクルの選択に対する通常の後悔の理由です。 我々のフレームワークは、預言不平等、Pandoraのボックス、ベスト・オブ・K$選択、確率的knapsack、確率的オリエンテーリング、確率的部分モジュラー最大化に適用される。

関連論文リスト

• 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)
• Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
  一般的な実現可能性の下では、我々のLEDGERアルゴリズムは、期待される損失$O(sqrt T)と期待される予算違反$O(sqrtTlog(eT))を達成します。 スレーター条件、フィードバックチャネル間の独立性、絶対的制約値境界は不要である。
  論文  参考訳（メタデータ） (2026-09-07T01:38:41Z)
• Optimizing the Preconditioner: A Black-box Online-to-Nonconvex Conversion with Static Regret Minimization Oracles [15.386375612838371]
  非最適化は、ブラックボックス方式でオンライン凸最適化において通常の静的に還元できる。 スムーズな非目的に対して、当社の削減は予測可能な勾配トラッカーを維持し、ブラックボックスは固定されたMをオンラインに選択する。 オンラインでブラックボックスがaを選択します。 オンラインのブラックボックスはグラデーショントラッカーを選択し、トラッカーがグラデーションにどのように変換されるかを決定する。 A。 Black-box Onlineは、トラッカーがグラデーションにどのように変換されるかを決定する固定されたMを選択する。 A。 オンラインのブラックボックスがグラデーショントラッカーを選択し、トラッカーがaに変換される方法を決定する
  論文  参考訳（メタデータ） (2026-07-20T06:53:59Z)
• New Bounds for the Last Iterate of the Stochastic subGradient Method [11.179752660122281]
  本稿では,1次元凸リプシッツ目標に対する下段法の最後の繰り返しについて検討する。 最後の繰り返しは1/sqrt n$の順序の最適化誤差を特徴とする。 i.d.仮定がなければ、最適化誤差は位数 $(log n)/sqrt n$ となる。
  論文  参考訳（メタデータ） (2026-06-23T17:55:18Z)
• Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clipping [21.865728815935665]
  重み付き雑音下での最初の収束を提供するが、切断はしない。 また、テールインデックス$mathfrakp$が事前に不明な場合には、最初の$mathcalO(Tfrac1-mathfrakp3mathfrakp-2)$収束率も設定する。
  論文  参考訳（メタデータ） (2024-12-27T08:46:46Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Oblivious Stochastic Composite Optimization [47.48197617884748]
  我々のアルゴリズムは問題のパラメータに関する事前の知識なしで収束することを示す。 3つのアルゴリズムは全て、実現可能な集合の直径、リプシッツ定数、あるいは目的関数の滑らかさについて事前の知識なしに機能する。 我々は,フレームワークを比較的大規模に拡張し,大規模半確定プログラム上での手法の効率性と堅牢性を実証する。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。 漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2022-06-17T06:10:20Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  制約付き非線形最適化問題のオンライン統計的推測を考察する。 これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
  論文  参考訳（メタデータ） (2022-05-27T00:34:03Z)

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

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