論文の概要: Regret Guarantees for Linear Contextual Stochastic Shortest Path

• arxiv url: http://arxiv.org/abs/2511.12534v1
• Date: Sun, 16 Nov 2025 10:09:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-18 14:36:24.300979
• Title: Regret Guarantees for Linear Contextual Stochastic Shortest Path
• Title（参考訳）: 線形確率的最短経路に対する規則保証
• Authors: Dor Polikar, Alon Cohen,
• Abstract要約: LR-CSSPは,O(sqrtK cdot d2 |S|3 |A| B_star3 log (1/)/ell_min)$の残差を求めるアルゴリズムである。 解析の結果,LR-CSSPは連続的なコンテキスト空間を効果的に処理し,全てのエピソードが適切な時間ステップで終了することを確認した。
• 参考スコア（独自算出の注目度）: 5.120675183010349
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We define the problem of linear Contextual Stochastic Shortest Path (CSSP), where at the beginning of each episode, the learner observes an adversarially chosen context that determines the MDP through a fixed but unknown linear function. The learner's objective is to reach a designated goal state with minimal expected cumulative loss, despite having no prior knowledge of the transition dynamics, loss functions, or the mapping from context to MDP. In this work, we propose LR-CSSP, an algorithm that achieves a regret bound of $\widetilde{O}(K^{2/3} d^{2/3} |S| |A|^{1/3} B_\star^2 T_\star \log (1/ δ))$, where $K$ is the number of episodes, $d$ is the context dimension, $S$ and $A$ are the sets of states and actions respectively, $B_\star$ bounds the optimal cumulative loss and $T_\star$, unknown to the learner, bounds the expected time for the optimal policy to reach the goal. In the case where all costs exceed $\ell_{\min}$, LR-CSSP attains a regret of $\widetilde O(\sqrt{K \cdot d^2 |S|^3 |A| B_\star^3 \log(1/δ)/\ell_{\min}})$. Unlike in contextual finite-horizon MDPs, where limited knowledge primarily leads to higher losses and regret, in the CSSP setting, insufficient knowledge can also prolong episodes and may even lead to non-terminating episodes. Our analysis reveals that LR-CSSP effectively handles continuous context spaces, while ensuring all episodes terminate within a reasonable number of time steps.
• Abstract（参考訳）: そこで,各エピソードの冒頭で学習者は,固定だが未知の線形関数によってMDPを決定する逆選択された文脈を観察する。 学習者の目的は、遷移ダイナミクスや損失関数、文脈からMDPへのマッピングに関する事前知識がないにもかかわらず、最小限の累積損失で指定された目標状態に到達することである。 LR-CSSP, $\widetilde{O}(K^{2/3} d^{2/3} |S| |A|^{1/3} B_\star^2 T_\star \log (1/δ))$, where $K$ is the number of episodes, $d$ is the context dimension, $S$ and $A$ are the set of state and action, $B_\star$ bounds the optimal cumulative loss, $T_\star$, unknown to the learner, bounds the expected time of the optimal policy to reach the goal。 すべてのコストが$\ell_{\min}$を超える場合、LR-CSSPは$\widetilde O(\sqrt{K \cdot d^2 |S|^3 |A| B_\star^3 \log(1/δ)/\ell_{\min}})$を後悔する。 限られた知識が主に損失と後悔を招き、CSSP設定では不足した知識がエピソードを延長し、終了しないエピソードも引き起こすような文脈的有限水平MDPとは異なり、CSSP設定では不十分な知識はエピソードを長引かせる。 解析の結果,LR-CSSPは連続的なコンテキスト空間を効果的に処理し,全てのエピソードが適切な時間ステップで終了することを確認した。

関連論文リスト

• Reinforcement Learning from Adversarial Preferences in Tabular MDPs [62.73758165845971]
  我々は,敵対的嗜好を持つエピソードマルコフ決定プロセス(MDP)の新たな枠組みを導入する。 PbMDP では、標準的なエピソード MDP とは異なり、学習者は2つの候補アーム間の好みを観察する。 我々は、既知遷移の下で、T2/3$という残差境界を達成するアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2025-07-15T20:19:32Z)
• Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
  本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。 我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。 技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
  論文  参考訳（メタデータ） (2022-10-15T09:22:22Z)
• Optimism in Face of a Context: Regret Guarantees for Stochastic Contextual MDP [46.86114958340962]
  我々は,最小到達可能性仮定の下での文脈的MDPに対する後悔のアルゴリズムを提案する。 我々のアプローチは、一般関数近似を用いた文脈的MDPに適用された最初の楽観的アプローチである。
  論文  参考訳（メタデータ） (2022-07-22T15:00:15Z)
• Minimal Expected Regret in Linear Quadratic Control [79.81807680370677]
  オンライン学習アルゴリズムを考案し、その期待された後悔を保証します。 当時のこの後悔は、$A$と$B$が未知の場合、$widetildeO((d_u+d_x)sqrtd_xT)$によって上界(i)となる。
  論文  参考訳（メタデータ） (2021-09-29T14:07:21Z)
• Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret [144.6358229217845]
  エージェントが目標状態に到達する前に蓄積される期待コストを最小限に抑えるために,最短経路(ssp)設定で学習する問題について検討する。 我々は,経験的遷移を慎重に歪曲し,探索ボーナスで経験的コストを摂動する新しいモデルベースアルゴリズムEB-SSPを設計する。 私達はEB-SSPが$widetildeO(B_star sqrtS A K)$のミニマックスの後悔率を達成することを証明します。
  論文  参考訳（メタデータ） (2021-04-22T17:20:48Z)
• Minimax Regret for Stochastic Shortest Path [63.45407095296692]
  我々は、エージェントが最小の総予想コストで目標状態に達する必要がある最短パス(SSP)問題を研究します。 この設定に対するminimaxの後悔は、$widetilde O(B_star sqrt|S| |A|K)$であり、$B_star$は任意の状態から最適なポリシーの予想コストに拘束されることを示しています。 本アルゴリズムは, 有限水平MDPにおける強化学習の新たな削減を基礎として, エピソードごとのインタイム動作を行う。
  論文  参考訳（メタデータ） (2021-03-24T10:11:49Z)
• Near-optimal Regret Bounds for Stochastic Shortest Path [63.029132134792555]
  最短経路 (SSP) は計画と制御においてよく知られた問題であり、エージェントは最小の総コストで目標状態に到達する必要がある。 任意の学習アルゴリズムは、最悪の場合、少なくとも$Omega(B_star sqrt|S| |A|K)$後悔しなければならない。
  論文  参考訳（メタデータ） (2020-02-23T09:10:14Z)

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

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