More Like this

1. An Empirical Relative Value Learning Algorithm for Non-parametric MDPs with Continuous State Space

   https://doi.org/10.23919/ECC.2019.8795982  

   Sharma, Hiteshi; Jain, Rahul; Gupta, Abhishek (June 2019, 2019 18th European Control Conference (ECC))

   We propose an empirical relative value learning (ERVL) algorithm for non-parametric MDPs with continuous state space and finite actions and average reward criterion. The ERVL algorithm relies on function approximation via nearest neighbors, and minibatch samples for value function update. It is universal (will work for any MDP), computationally quite simple and yet provides arbitrarily good approximation with high probability in finite time. This is the first such algorithm for non-parametric (and continuous state space) MDPs with average reward criteria with these provable properties as far as we know. Numerical evaluation on a benchmark problem of optimal replacement suggests good performance. 

   more » « less
2. Q-learning with nearest neighbors

   Shah, Devavrat; Xie, Qiaomin (October 2018, Nips)

   We consider model-free reinforcement learning for infinite-horizon discounted Markov Decision Processes (MDPs) with a continuous state space and unknown transition kernel, when only a single sample path under an arbitrary policy of the system is available. We consider the Nearest Neighbor Q-Learning (NNQL) algorithm to learn the optimal Q function using nearest neighbor regression method. As the main contribution, we provide tight finite sample analysis of the convergence rate. In particular, for MDPs with a d-dimensional state space and the discounted factor in (0, 1), given an arbitrary sample path with “covering time” L, we establish that the algorithm is guaranteed to output an "-accurate estimate of the optimal Q-function nearly optimal sample complexity. 

   more » « less
3. An Approximately Optimal Relative Value Learning Algorithm for Averaged MDPs with Continuous States and Actions

   https://doi.org/10.1109/ALLERTON.2019.8919719  

   Sharma, Hiteshi; Jain, Rahul (September 2019, 2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton))

   It has long been a challenging problem to design algorithms for Markov decision processes (MDPs) with continuous states and actions that are provably approximately optimal and can provide arbitrarily good approximation for any MDP. In this paper, we propose an empirical value learning algorithm for average MDPs with continuous states and actions that combines empirical value iteration with n function-parametric approximation and approximation of transition probability distribution with kernel density estimation. We view each iteration as operation of random operator and argue convergence using the probabilistic contraction analysis method that the authors (along with others) have recently developed. 

   more » « less
4. Scalable spectral representations for multiagent reinforcement learning in network MDPs

   Ren, Zhaolin; Zhang, Runyu; Dai, Bo; Li, Na (May 2025, Proceedings of Machine Learning Research)

   Li, Yingzhen; Mandt, Stephan; Agrawal, Shipra; Khan, Emtiyaz (Ed.)

   Network Markov Decision Processes (MDPs), which are the de-facto model for multi-agent control, pose a significant challenge to efficient learning caused by the exponential growth of the global state-action space with the number of agents. In this work, utilizing the exponential decay property of network dynamics, we first derive scalable spectral local representations for multiagent reinforcement learning in network MDPs, which induces a network linear subspace for the local $$Q$$-function of each agent. Building on these local spectral representations, we design a scalable algorithmic framework for multiagent reinforcement learning in continuous state-action network MDPs, and provide end-to-end guarantees for the convergence of our algorithm. Empirically, we validate the effectiveness of our scalable representation-based approach on two benchmark problems, and demonstrate the advantages of our approach over generic function approximation approaches to representing the local $$Q$$-functions. 

   more » « less
5. Skill Discovery for Exploration and Planning using Deep Skill Graphs

   Bagaria, A; Senthil, J; Konidaris, G (July 2021, Proceedings of the Thirty-Eighth International Conference on Machine Learning)

   null (Ed.)

   We introduce a new skill-discovery algorithm that builds a discrete graph representation of large continuous MDPs, where nodes correspond to skill subgoals and the edges to skill policies. The agent constructs this graph during an unsupervised training phase where it interleaves discovering skills and planning using them to gain coverage over ever-increasing portions of the state-space. Given a novel goal at test time, the agent plans with the acquired skill graph to reach a nearby state, then switches to learning to reach the goal. We show that the resulting algorithm, Deep Skill Graphs, outperforms both flat and existing hierarchical reinforcement learning methods on four difficult continuous control tasks. 

   more » « less