Timezone: »
Spotlight
Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximation
Daniel Vial · Advait Parulekar · Sanjay Shakkottai · R Srikant
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.
Author Information
Daniel Vial (UT Austin / UIUC)
Advait Parulekar (University of Texas at Austin)
Sanjay Shakkottai (University of Texas at Austin)
R Srikant (UIUC)
Related Events (a corresponding poster, oral, or spotlight)
-
2022 Poster: Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximation »
Wed. Jul 20th through Thu the 21st Room Hall E #1418
More from the Same Authors
-
2021 : Sample Complexity and Overparameterization Bounds for Temporal Difference Learning with Neural Network Approximation »
Semih Cayci · Siddhartha Satpathi · Niao He · R Srikant -
2021 : Linear Convergence of Entropy-Regularized Natural Policy Gradient with Linear Function Approximation »
Semih Cayci · Niao He · R Srikant -
2023 Poster: Collaborative Multi-Agent Heterogeneous Multi-Armed Bandits »
Ronshee Chawla · Daniel Vial · Sanjay Shakkottai · R Srikant -
2023 Poster: PAC Generalization via Invariant Representations »
Advait Parulekar · Karthikeyan Shanmugam · Sanjay Shakkottai -
2022 Poster: MAML and ANIL Provably Learn Representations »
Liam Collins · Aryan Mokhtari · Sewoong Oh · Sanjay Shakkottai -
2022 Poster: Asymptotically-Optimal Gaussian Bandits with Side Observations »
Alexia Atsidakou · Orestis Papadigenopoulos · Constantine Caramanis · Sujay Sanghavi · Sanjay Shakkottai -
2022 Spotlight: Asymptotically-Optimal Gaussian Bandits with Side Observations »
Alexia Atsidakou · Orestis Papadigenopoulos · Constantine Caramanis · Sujay Sanghavi · Sanjay Shakkottai -
2022 Spotlight: MAML and ANIL Provably Learn Representations »
Liam Collins · Aryan Mokhtari · Sewoong Oh · Sanjay Shakkottai -
2022 Poster: Linear Bandit Algorithms with Sublinear Time Complexity »
Shuo Yang · Tongzheng Ren · Sanjay Shakkottai · Eric Price · Inderjit Dhillon · Sujay Sanghavi -
2022 Spotlight: Linear Bandit Algorithms with Sublinear Time Complexity »
Shuo Yang · Tongzheng Ren · Sanjay Shakkottai · Eric Price · Inderjit Dhillon · Sujay Sanghavi -
2019 Poster: Pareto Optimal Streaming Unsupervised Classification »
Soumya Basu · Steven Gutstein · Brent Lance · Sanjay Shakkottai -
2019 Oral: Pareto Optimal Streaming Unsupervised Classification »
Soumya Basu · Steven Gutstein · Brent Lance · Sanjay Shakkottai -
2018 Poster: Understanding the Loss Surface of Neural Networks for Binary Classification »
SHIYU LIANG · Ruoyu Sun · Yixuan Li · R Srikant -
2018 Oral: Understanding the Loss Surface of Neural Networks for Binary Classification »
SHIYU LIANG · Ruoyu Sun · Yixuan Li · R Srikant