EUVIMEDEUVIMED entdecken
Crossref

Convergence of off-policy TD(0) with linear function approximation for reversible Markov chains

Maik Overmars, Jasper Goseling, Richard J. Boucherie

ACM SIGMETRICS Performance Evaluation Review · 31.03.2026 · 53 (4) · 91-96

DOI: 10.1145/3797823.3797851 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM SIGMETRICS Performance Evaluation Review, online erschienen am 31.03.2026. Verfasst von Maik Overmars und 2 weiteren Autor:innen. Die Arbeit nennt 24 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 onpolicy 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 o?-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.

Zitieren

APA

Overmars, M., Goseling, J., & Boucherie, R. J. (2026). Convergence of off-policy TD(0) with linear function approximation for reversible Markov chains. ACM SIGMETRICS Performance Evaluation Review, 53(4), 91-96. https://doi.org/10.1145/3797823.3797851

Vancouver

Overmars M, Goseling J, Boucherie RJ. Convergence of off-policy TD(0) with linear function approximation for reversible Markov chains. ACM SIGMETRICS Performance Evaluation Review. 2026;53(4):91-96. doi:10.1145/3797823.3797851

BibTeX
@article{Overmars2026,
  author = {Overmars, Maik and Goseling, Jasper and Boucherie, Richard J.},
  title = {Convergence of off-policy TD(0) with linear function approximation for reversible Markov chains},
  journal = {ACM SIGMETRICS Performance Evaluation Review},
  year = {2026},
  volume = {53},
  number = {4},
  pages = {91--96},
  doi = {10.1145/3797823.3797851}
}
Kostenlos starten →