Counterfactual Optimism: Rate Optimal Regret for Stochastic Contextual MDPs

11/27/2022
by   Orin Levy, et al.
0

We present the UC^3RL algorithm for regret minimization in Stochastic Contextual MDPs (CMDPs). The algorithm operates under the minimal assumptions of realizable function class, and access to offline least squares and log loss regression oracles. Our algorithm is efficient (assuming efficient offline regression oracles) and enjoys an O(H^3 √(T |S| |A|(log (|ℱ|/δ) + log (|𝒫|/ δ) ))) regret guarantee, with T being the number of episodes, S the state space, A the action space, H the horizon, and 𝒫 and ℱ are finite function classes, used to approximate the context-dependent dynamics and rewards, respectively. To the best of our knowledge, our algorithm is the first efficient and rate-optimal regret minimization algorithm for CMDPs, which operates under the general offline function approximation setting.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset