論文の概要: Stochastic Shortest Path with Sparse Adversarial Costs

• arxiv url: http://arxiv.org/abs/2511.00637v1
• Date: Sat, 01 Nov 2025 17:34:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-05 16:37:26.872389
• Title: Stochastic Shortest Path with Sparse Adversarial Costs
• Title（参考訳）: スパース対向コストを考慮した確率的最短経路
• Authors: Emmeran Johnson, Alberto Rumi, Ciara Pike-Burke, Patrick Rebeschini,
• Abstract要約: 本研究は,全情報フィードバックによる対向的最短経路 (SSP) 問題とスパースコストについて検討する。 負のエントロピーは本質的にはスパーシティに適応しないことを示す。 我々は、sqrtlog SA$の代わりに$sqrtlog M$で、sqrtlog M$による後悔のスケーリングを達成できるような、$ell_r$norm正規化器のファミリーを提案する。
• 参考スコア（独自算出の注目度）: 17.39852236778619
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the adversarial Stochastic Shortest Path (SSP) problem with sparse costs under full-information feedback. In the known transition setting, existing bounds based on Online Mirror Descent (OMD) with negative-entropy regularization scale with $\sqrt{\log S A}$, where $SA$ is the size of the state-action space. While we show that this is optimal in the worst-case, this bound fails to capture the benefits of sparsity when only a small number $M \ll SA$ of state-action pairs incur cost. In fact, we also show that the negative-entropy is inherently non-adaptive to sparsity: it provably incurs regret scaling with $\sqrt{\log S}$ on sparse problems. Instead, we propose a family of $\ell_r$-norm regularizers ($r \in (1,2)$) that adapts to the sparsity and achieves regret scaling with $\sqrt{\log M}$ instead of $\sqrt{\log SA}$. We show this is optimal via a matching lower bound, highlighting that $M$ captures the effective dimension of the problem instead of $SA$. Finally, in the unknown transition setting the benefits of sparsity are limited: we prove that even on sparse problems, the minimax regret for any learner scales polynomially with $SA$.
• Abstract（参考訳）: 本研究は,全情報フィードバックによる対向的確率的最短経路 (SSP) 問題とスパースコストについて検討する。 既知の遷移設定では、正エントロピー正則化スケールが$\sqrt{\log S A}$で、オンラインミラー Descent (OMD) に基づく既存の境界は状態-作用空間のサイズである。 最悪の場合、これが最適であることを示すが、この境界は、わずかな数$M \ll SA$の状態-作用対がコストのかかる場合にのみ、スパーシティの利点を捉えることができない。 実際、負エントロピーは本質的にはスパース性に適応せず、スパース問題に対して$\sqrt{\log S}$の後悔のスケーリングを生じさせる。 代わりに、スパーシティに適応し、$\sqrt{\log M}$で後悔のスケーリングを行う$\ell_r$-norm regularizers$r \in (1,2)$) の族を提案する。 これは一致する下界によって最適であることが示され、$M$は$SA$ではなく問題の有効次元をキャプチャする。 スパース問題に関しても、学習者のミニマックスが$SA$で多項式的にスケールすることを証明します。

関連論文リスト

• Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and $(L_0, L_1)$-Smoothness [57.93371273485736]
  我々は、最近提案された$ell$-smoothness条件$|nabla2f(x)|| le ellleft(||nabla f(x)||right),$$$L$-smoothnessと$(L_0,L_1)$-smoothnessを一般化する関数を持つ凸最適化問題の一階法について検討する。
  論文  参考訳（メタデータ） (2025-08-09T08:28:06Z)
• Batched Stochastic Bandit for Nondegenerate Functions [8.015503209312786]
  本稿では,非退化関数に対するバッチ帯域学習問題について検討する。 本稿では,非退化関数に対するバッチバンドイット問題をほぼ最適に解くアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-05-09T12:50:16Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes [62.90204655228324]
  我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。 我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
  論文  参考訳（メタデータ） (2022-10-20T21:32:01Z)
• Scale-Free Adversarial Multi-Armed Bandit with Arbitrary Feedback Delays [21.94728545221709]
  制限のないフィードバック遅延を伴うMAB(Scale-Free Adversarial Multi Armed Bandit)問題を考える。 textttSFBankerは$mathcal O(sqrtK(D+T)L)cdot rm polylog(T, L)$ total regret, where $T$ is the total number of steps, $D$ is the total feedback delay。
  論文  参考訳（メタデータ） (2021-10-26T04:06:51Z)
• 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)
• $Q$-learning with Logarithmic Regret [60.24952657636464]
  楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
  論文  参考訳（メタデータ） (2020-06-16T13:01:33Z)
• Near-optimal Regret Bounds for Stochastic Shortest Path [63.029132134792555]
  最短経路 (SSP) は計画と制御においてよく知られた問題であり、エージェントは最小の総コストで目標状態に到達する必要がある。 任意の学習アルゴリズムは、最悪の場合、少なくとも$Omega(B_star sqrt|S| |A|K)$後悔しなければならない。
  論文  参考訳（メタデータ） (2020-02-23T09:10:14Z)
• Logistic Regression Regret: What's the Catch? [3.7311680121118345]
  パラメータに対する$L_infty$制約の下で、対数的後悔を伴う下界を導出する。 L$の制約については、十分に大きな$d$の場合、後悔は$d$で線形であるが、$T$で対数化されなくなることが示されている。
  論文  参考訳（メタデータ） (2020-02-07T18:36:39Z)

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

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