More Like this

1. Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolation

   Zhang, Yixuan; Xie, Qiaomin (August 2024, Reinforcement Learning Journal)

   Stochastic Approximation (SA) is a widely used algorithmic approach in various fields, including optimization and reinforcement learning (RL). Among RL algorithms, Q-learning is particularly popular due to its empirical success. In this paper, we study asynchronous Q-learning with constant stepsize, which is commonly used in practice for its fast convergence. By connecting the constant stepsize Q-learning to a time-homogeneous Markov chain, we show the distributional convergence of the iterates in Wasserstein distance and establish its exponential convergence rate. We also establish a Central Limit Theory for Q-learning iterates, demonstrating the asymptotic normality of the averaged iterates. Moreover, we provide an explicit expansion of the asymptotic bias of the averaged iterate in stepsize. Specifically, the bias is proportional to the stepsize up to higher-order terms and we provide an explicit expression for the linear coefficient. This precise characterization of the bias allows the application of Richardson-Romberg (RR) extrapolation technique to construct a new estimate that is provably closer to the optimal Q function. Numerical results corroborate our theoretical finding on the improvement of the RR extrapolation method. 

   more » « less
2. On the Optimal Control of a Linear Peridynamics Model

   https://doi.org/10.1007/s00245-023-10045-x  

   Mengesha, Tadele; Salgado, Abner J; Siktar, Joshua M (December 2023, Applied Mathematics & Optimization)

   We study a non-local optimal control problem involving a linear, bond-based peridynamics model. In addition to existence and uniqueness of solutions to our problem, we investigate their behavior as the horizon parameter 𝛿, which controls the degree of nonlocality, approaches zero. We then study a finite element-based discretization of this problem, its convergence, and the so-called asymptotic compatibility as the discretization parameter h and the horizon parameter 𝛿 tend to zero simultaneously. 

   more » « less
3. Learning Optimal Policies in Mean Field Models with Kullback-Leibler Regularization

   Ana Busic, Sean Meyn (December 2023, IEEE Conference on Decision and Control)

   The theory and application of mean field games has grown significantly since its origins less than two decades ago. This paper considers a special class in which the game is cooperative, and the cost includes a control penalty defined by Kullback-Leibler divergence, as commonly used in reinforcement learning and other fields. Its use as a control cost or regularizer is often preferred because this leads to an attractive solution. This paper considers a particular control paradigm called Kullback-Leibler Quadratic (KLQ) optimal control, and arrives at the following conclusions: 1. in application to distributed control of electric loads, a new modeling technique is introduced to obtain a simple Markov model for each load (the `agent' in mean field theory). 2. It is argued that the optimality equations may be solved using Monte-Carlo techniques---a specialized version of stochastic gradient descent (SGD). 3. The use of averaging minimizes the asymptotic covariance in the SGD algorithm; the form of the optimal covariance is identified for the first time. 

   more » « less
4. Explicit Mean-Square Error Bounds for Monte-Carlo and Linear Stochastic Approximation

   Chen, Shuhang and (July 2020, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics)

   This paper concerns error bounds for recursive equations subject to Markovian disturbances. Motivating examples abound within the fields of Markov chain Monte Carlo (MCMC) and Reinforcement Learning (RL), and many of these algorithms can be interpreted as special cases of stochastic approximation (SA). It is argued that it is not possible in general to obtain a Hoeffding bound on the error sequence, even when the underlying Markov chain is reversible and geometrically ergodic, such as the M/M/1 queue. This is motivation for the focus on mean square error bounds for parameter estimates. It is shown that mean square error achieves the optimal rate of $O(1/n)$, subject to conditions on the step-size sequence. Moreover, the exact constants in the rate are obtained, which is of great value in algorithm design 

   more » « less
5. Fast Ergodic Search With Kernel Functions

   https://doi.org/10.1109/TRO.2025.3543298  

   Sun, Max Muchen; Gaggar, Ayush; Trautman, Pete; Murphey, Todd (January 2025, IEEE Transactions on Robotics)

   Ergodic search enables optimal exploration of an information distribution with guaranteed asymptotic coverage of the search space. However, current methods typically have exponential computational complexity and are limited to Euclidean space. We introduce a computationally efficient ergodic search method. Our contributions are two-fold: First, we develop a kernel-based ergodic metric, generalizing it from Euclidean space to Lie groups. We prove this metric is consistent with the exact ergodic metric and ensures linear complexity. Second, we derive an iterative optimal control algorithm for trajectory optimization with the kernel metric. Numerical benchmarks show our method is two orders of magnitude faster than the state-of-the-art method. Finally, we demonstrate the proposed algorithm with a peg-in-hole insertion task. We formulate the problem as a coverage task in the space of SE(3) and use a 30-second-long human demonstration as the prior distribution for ergodic coverage. Ergodicity guarantees the asymptotic solution of the peg-in-hole problem so long as the solution resides within the prior information distribution, which is seen in the 100% success rate. 

   more » « less