← Back to papers
2022 ICML ICML 2022

Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximation

Abstract

We propose an algorithm that uses linear function approximation (LFA) for stochastic shortest path (SSP). Under minimal assumptions, it obtains sublinear regret, is computationally efficient, and uses stationary policies. To our knowledge, this is the first such algorithm in the LFA literature (for SSP or other formulations). Our algorithm is a special case of a more general one, which achieves regret square root in the number of episodes given access to a computation oracle.

🌉 Interdisciplinary Bridge — Machine Learning and Mathematics & Optimization and Reinforcement Learning
🐝 Cross-Pollinator — Artificial Intelligence, Computer Science, Computer Vision, Data Science & Analytics, Deep Learning, Healthcare & Medicine, Interdisciplinary, Knowledge & Reasoning, Machine Learning, Mathematics & Optimization, Natural Language Processing, Reinforcement Learning, Robotics, Security & Privacy, Speech & Audio

Authors

Daniel Vial , Advait Parulekar , Sanjay Shakkottai , R Srikant

Topics

Machine Learning > Optimization & Theory > Learning Theory Machine Learning > Optimization & Theory > Theory Reinforcement Learning > Methods > Deep RL Reinforcement Learning > Methods > Policy Learning Mathematics & Optimization > Optimization > Optimization

Keywords

reinforcement learning linear function approximation stochastic shortest path regret bound sublinear regret stationary policy
Download PDF

Related papers

A Tree-based Model Averaging Approach for Personalized Treatment Effect Estimation from Heterogeneous Data Sources 2022
Generic Coreset for Scalable Learning of Monotonic Kernels: Logistic Regression, Sigmoid and more 2022
Active fairness auditing 2022
Toward Compositional Generalization in Object-Oriented World Modeling 2022
Robustness Verification for Contrastive Learning 2022