論文の概要: Beyond Monotonicity: Stochastic Online Optimization under Semi-Bandit Feedback

• arxiv url: http://arxiv.org/abs/2611.02739v1
• Date: Mon, 02 Nov 2026 08:27:17 GMT
• ステータス: 情報取得中
• システム内更新日: 2026-11-03 19:45:18.926479
• Title: Beyond Monotonicity: Stochastic Online Optimization under Semi-Bandit Feedback
• Title（参考訳）: モノトニック性を超えて - 半帯域フィードバック下での確率的オンライン最適化
• Abstract要約: 1次支配(FSD)の単調性は、オンライン最適化(SOO)学習の一般的な削減を可能にする アルゴリズムは最適ポリシーの動的プログラムを実行し、各期待値を最も楽観的な値に置き換える。 一定のレベルセットの複素数に対して、後悔は連続分布に対しても$tildeO(sqrtnT)$である。
• 参考スコア（独自算出の注目度）: 7.858819231575403
• License:
• Abstract: We study stochastic online optimization (SOO) under semi-bandit feedback: in each of $T$ rounds, a policy adaptively observes $n$ independent random variables with unknown distributions, learning only from observed values. First-order stochastic dominance (FSD) monotonicity enables general reductions for learning SOO, but can fail when observations change future feasibility, resource use, or reference points. Our algorithm runs the dynamic program for the optimal policy, replacing each expectation by its most optimistic value over a confidence set of distributions. Its regret depends on the level-set complexity $s_i$ of the computed values as functions of the $i$th variable: the number of intervals needed to describe their superlevel sets. For rewards in $[0,1]$, the regret is $\tilde{O}(\sqrt{ST})$ without this monotonicity, where $S=\sum_{i=1}^n\min\{s_i,k_i\}$ and $k_i$ is the support size of the $i$th distribution, which may be infinite when $s_i$ is finite. For constant level-set complexities, regret is $\tilde{O}(\sqrt{nT})$, even for continuous distributions. The algorithm requires no knowledge of $s_i$, $k_i$, or the supports, and it also achieves regret $\tilde{O}(\sqrt{nkT})$ for supports of size at most $k$ without any level-set condition, which improves the previous bound $\tilde{O}(n(\sqrt{kT}+k))$ for FSD-monotone problems. We also prove a lower bound of $Ω(\min\{T,\sqrt{ST}\})$ for all positive integers $s_1,\ldots,s_n$ with $k_i=2s_i+1$, which holds even under full feedback and matches the upper bound up to logarithmic factors. We obtain $\tilde{O}(\sqrt{nT})$ regret for these problems, all nonmonotone under FSD: stochastic Boolean function evaluation, the full-information secretary problem, optimal stopping with loss aversion, scheduling with deadlines and correlated stochastic knapsack with unimodal rewards, and overbooking with group reservations.
• Abstract（参考訳）: 半帯域フィードバック下で確率的オンライン最適化(SOO)について検討し、それぞれ$T$のラウンドで、未知分布を持つ独立確率変数を適応的に観測し、観測値のみから学習する。 1次確率支配(FSD)の単調性は、SOO学習の一般的な削減を可能にするが、観測結果が将来の実現可能性、リソース使用、参照ポイントを変えると失敗する。 我々のアルゴリズムは最適ポリシーの動的プログラムを実行し、各期待値を最も楽観的な値に置き換える。 その後悔は、$i$th変数の関数として計算された値のレベルセットの複雑さ$s_i$に依存する: 超レベル集合を記述するのに必要な間隔の数である。 ここで、$S=\sum_{i=1}^n\min\{s_i,k_i\}$と$k_i$は、$i$thディストリビューションのサポートサイズであり、$s_i$が有限であれば無限である。 一定レベル集合の複素数に対して、後悔は連続分布に対しても$\tilde{O}(\sqrt{nT})$である。 このアルゴリズムは、$s_i$、$k_i$、またはサポートの知識を必要とせず、また、任意のレベルセット条件なしに、最大$k$でのサイズのサポートに対して、後悔の$\tilde{O}(\sqrt{nkT})$を達成し、FSD単調問題に対して、以前の有界$\tilde{O}(n(\sqrt{kT}+k))$を改善する。 また、すべての正の整数に対して$Ω(\min\{T,\sqrt{ST}\})$の低い境界を$s_1,\ldots,s_n$と$k_i=2s_i+1$で証明する。 我々はこれらの問題に対して$\tilde{O}(\sqrt{nT})$ regret, all nonmonotone under FSD: stochastic Boolean function evaluation, the full-information Secretary problem, optimal stop with loss aversion, schedule with deadlines and correlation stochastic knapsack with unimodal rewards, and overbooking with group reservationsを得る。

関連論文リスト

• Near-Optimal Regret for Semi-Bandit Learning of Monotone Stochastic Problems [3.329206202900235]
  本研究は,真の分布が不明な最適化問題に対する最適ポリシーを学習する作業について考察する。 各期間、アルゴリズムは問題に対するポリシーを実行し、半帯域フィードバック、すなわちポリシーによって選択されたランダム変数からのみ新しいサンプルを受け取る。 我々は,預言不平等,Pandoraのボックス,シリーズテスト,knapsack,マッチングなど,大規模なモノトーン問題に対処するアルゴリズムを得る。
  論文  参考訳（メタデータ） (2026-10-17T04:17:23Z)
• Optimal Oracle Complexity for Finite-Sum Monotone Inclusions [1.6921396880325779]
  提案手法は,$$y$,$$gin G(y)$ with $(mathbbE|F(y)+g|2)1/2levarepsilon$ using $mathcalO(n+sqrtnLR/varepsilon)$ expected component evaluations and resolvent evaluations。 A matching $(n+sqrtnLR/varepsilon)$ lower bound Hold for randomized linear-span component-oracle algorithm with adapt Stop and expected query budgets
  論文  参考訳（メタデータ） (2026-10-04T08:14:47Z)
• 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)
• Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence [54.59847568544922]
  有限水平時間同質なマルコフ決定過程に対して、$A$状態、$A$アクション、hoighty $H$、および1ドルで有界なトラジェクティブ当たりの合計報酬について、地平自由な後悔について検討する。 失敗確率$$K$はエピソード数で$tilde O(sqrtSAK+S3K)$ hides $mathsfpolyである。
  論文  参考訳（メタデータ） (2026-07-22T07:42:19Z)
• 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)
• On the Complexity of Decentralized Smooth Nonconvex Finite-Sum Optimization [21.334985032433778]
  分散最適化問題 $min_bf xinmathbb Rd f(bf x)triq frac1msum_i=1m f_i(bf x)triq frac1nsum_j=1n。
  論文  参考訳（メタデータ） (2022-10-25T11:37:11Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  制約付き非線形最適化問題のオンライン統計的推測を考察する。 これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
  論文  参考訳（メタデータ） (2022-05-27T00:34:03Z)
• Decentralized Stochastic Variance Reduced Extragradient Method [25.21457349137344]
  本稿では,$min_xmax_y fx,y triqfrac1msumi=1m f_i triqfrac1msumi=1m f_i triqfrac1msumi=1m f_i triqfrac1msumi=1m f_i triqfrac1msumiの分散凸-凹極小最適化問題を考察する。
  論文  参考訳（メタデータ） (2022-02-01T16:06:20Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。 我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。 ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
  論文  参考訳（メタデータ） (2021-02-15T08:16:51Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。 同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
  論文  参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

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