Isoperimetry is All We Need: Langevin Posterior Sampling for RL with Sublinear Regret

Understand

Common assumptions, like linear or RKHS models, and Gaussian or log-concave posteriors over the models, do not explain practical success of RL across a wider range of distributions and models.

• Thus, we study how to design RL algorithms with sublinear regret for isoperimetric distributions, specifically the ones satisfying the Log-Sobolev Inequality (LSI).
• LSI distributions include the standard setups of RL theory, and others, such as many non-log-concave and perturbed distributions.
• First, we show that the Posterior Sampling-based RL (PSRL) algorithm yields sublinear regret if the data distributions satisfy LSI and some mild additional assumptions.