Convergence Rate for RVI -Learning
Organizations: Department of Computer Science and Automation, Indian Institute of Science, Bengaluru, India. · Department of Electrical Engineering, Stanford University, Stanford, California, USA. · EPITA, Laboratoire Recherche de l’EPITA, Paris, France.
Abstract
We establish finite-time convergence guarantee for synchronous relative value iteration (RVI) -learning for finite weakly communicating Markov decision processes (MDPs). For stochastic Krasnosel'skiĭ--Mann iterations driven by a non-expansive, linearly regular map on a finite-dimensional normed space, we establish last-iterate mean-squared residual bounds under martingale-difference noise whose conditional second moment grows at most linearly with the squared residual. Suitable polynomial stepsizes of order yield an rate for . We verify linear regularity and the noise condition for the centered Bellman operator for finite weakly communicating MDPs. Applying the general result gives an bound on the mean-squared Bellman span residual of RVI -learning iterates when a suitable stepsize sequence is used. The positive gap between optimal and suboptimal stationary deterministic policies then yields an bound on the expected suboptimality of the greedy policy. Consequently, synchronous iterations suffice for an -optimal policy in expectation. These guarantees are instance-dependent, with constants that depend on the hitting-time parameters and the suboptimality gap of the second-best policy.
Reinforcement Learning
Reinforcement learning studies how agents learn sequential decisions from rewards and interaction, balancing exploration, performance, safety, and adaptation.
See all 1,835 papers