論文の概要: Convergence of off-policy TD(0) with linear function approximation for reversible Markov chains

• arxiv url: http://arxiv.org/abs/2510.25514v1
• Date: Wed, 29 Oct 2025 13:38:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-30 15:50:45.59729
• Title: Convergence of off-policy TD(0) with linear function approximation for reversible Markov chains
• Title（参考訳）: 可逆マルコフ連鎖に対する線形関数近似を用いたオフポリチックTD(0)の収束
• Authors: Maik Overmars, Jasper Goseling, Richard Boucherie,
• Abstract要約: マルコフ連鎖における期待割引報酬を近似するために,線形関数近似を用いたオフポリチックTD(0)の収束について検討した。 我々のアプローチは、標準的なアルゴリズムを解析することであるが、可逆的なマルコフ連鎖のクラスへの注意を制限することである。
• 参考スコア（独自算出の注目度）: 0.17478203318226307
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the convergence of off-policy TD(0) with linear function approximation when used to approximate the expected discounted reward in a Markov chain. It is well known that the combination of off-policy learning and function approximation can lead to divergence of the algorithm. Existing results for this setting modify the algorithm, for instance by reweighing the updates using importance sampling. This establishes convergence at the expense of additional complexity. In contrast, our approach is to analyse the standard algorithm, but to restrict our attention to the class of reversible Markov chains. We demonstrate convergence under this mild reversibility condition on the structure of the chain, which in many applications can be assumed using domain knowledge. In particular, we establish a convergence guarantee under an upper bound on the discount factor in terms of the difference between the on-policy and off-policy process. This improves upon known results in the literature that state that convergence holds for a sufficiently small discount factor by establishing an explicit bound. Convergence is with probability one and achieves projected Bellman error equal to zero. To obtain these results, we adapt the stochastic approximation framework that was used by Tsitsiklis and Van Roy [1997 for the on-policy case, to the off-policy case. We illustrate our results using different types of reversible Markov chains, such as one-dimensional random walks and random walks on a weighted graph.
• Abstract（参考訳）: マルコフ連鎖における期待割引報酬を近似するために,線形関数近似を用いたオフポリチックTD(0)の収束について検討した。 オフポリシー学習と関数近似の組み合わせがアルゴリズムの分岐につながることはよく知られている。 この設定の既存の結果は、例えば、重要サンプリングを使用して更新を再検討することで、アルゴリズムを変更する。 これにより、さらなる複雑さを犠牲にして収束が確立される。 対照的に、我々のアプローチは標準的なアルゴリズムを解析することであるが、可逆的なマルコフ連鎖のクラスへの注意を制限することである。 この軽度可逆性条件の下での収束を鎖の構造上で示し、多くの応用においてドメイン知識を用いて仮定することができる。 特に、非政治的プロセスと非政治的プロセスの差異の観点から、割引係数の上限の下で収束保証を確立する。 これは、明らかな境界を確立することによって、収束が十分小さな割引係数を保っているという文献の既知の結果を改善する。 収束は確率 1 であり、予想されるベルマン誤差は 0 に等しい。 これらの結果を得るために、ツィシクリスとヴァン・ロイ (1997) が行った確率近似の枠組みを、政治外の場合に適用する。 1次元のランダムウォークや、重み付きグラフ上のランダムウォークなど、さまざまな可逆マルコフ連鎖を用いて、その結果を説明する。

関連論文リスト

• Uncertainty quantification for Markov chain induced martingales with application to temporal difference learning [55.197497603087065]
  線形関数近似を用いた時間差分学習アルゴリズムの性能解析を行った。 マルコフ連鎖によって誘導されるベクトル値マルティンタに対する新規で一般的な高次元濃度不等式とベリー-エッセイン境界を確立する。
  論文  参考訳（メタデータ） (2025-02-19T15:33:55Z)
• Statistical Inference for Temporal Difference Learning with Linear Function Approximation [55.80276145563105]
  The statistics properties of Temporal difference learning with Polyak-Ruppert averaging。 3つの理論的な貢献により、現在の最先端の成果が向上する。
  論文  参考訳（メタデータ） (2024-10-21T15:34:44Z)
• A Unified Theory of Stochastic Proximal Point Methods without Smoothness [52.30944052987393]
  近点法はその数値的安定性と不完全なチューニングに対する頑健性からかなりの関心を集めている。 本稿では,近位点法(SPPM)の幅広いバリエーションの包括的解析について述べる。
  論文  参考訳（メタデータ） (2024-05-24T21:09:19Z)
• The ODE Method for Stochastic Approximation and Reinforcement Learning with Markovian Noise [17.493808856903303]
  近似アルゴリズムを解析する根本的な課題は、その安定性を確立することである。 我々は、マルティンゲール差分雑音設定からマルコフ雑音設定へ有界な安定性に対するボルカール・メインの定理を拡張した。
  論文  参考訳（メタデータ） (2024-01-15T17:20:17Z)
• Optimal variance-reduced stochastic approximation in Banach spaces [114.8734960258221]
  可分バナッハ空間上で定義された収縮作用素の定点を推定する問題について検討する。 演算子欠陥と推定誤差の両方に対して漸近的でない境界を確立する。
  論文  参考訳（メタデータ） (2022-01-21T02:46:57Z)
• Stochastic Approximation with Markov Noise: Analysis and applications in reinforcement learning [0.0]
  マルコフ雑音によって駆動される2つの時間スケール近似の収束解析を初めて提示する。 両方の時間スケールにおける差分包摂を限定することで、フレームワークの挙動を分析する。 ポリシ評価アルゴリズムの関数近似における最初の情報的誤差境界を求める。
  論文  参考訳（メタデータ） (2020-04-08T03:59:21Z)
• A Distributional Analysis of Sampling-Based Reinforcement Learning Algorithms [67.67377846416106]
  定常ステップサイズに対する強化学習アルゴリズムの理論解析に対する分布的アプローチを提案する。 本稿では,TD($lambda$)や$Q$-Learningのような値ベースの手法が,関数の分布空間で制約のある更新ルールを持つことを示す。
  論文  参考訳（メタデータ） (2020-03-27T05:13:29Z)

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

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