Efficient Rate Optimal Regret for Adversarial Contextual MDPs Using Online Function Approximation
Jul 24, 2023
Speakers
Alon Cohen
Speaker · 0 followers
Asaf Cassel
Speaker · 0 followers
Yishay Mansour
Speaker · 1 follower
About
We present the OMG-CMDP! algorithm for regret minimization in adversarial Contextual MDPs. The algorithm operates under the minimal assumptions of realizable function class and access to online least squares and log loss regression oracles. Our algorithm is efficient (assuming efficient online regression oracles), simple and robust to approximation errors. It enjoys an O(H^2.5√( T|S||A| ( ℛ(𝒪)+ H log(δ^-1) ))) regret guarantee, with T being the number of episodes, S the state space, A the action space, H the horizon and ℛ(𝒪) = ℛ(𝒪^ℱ𝓈𝓆 ) + ℛ(𝒪^𝒫𝓁ℴℊ) is the sum of the regression oracles' regret, used to approximate the context-dependent rewards and dynamics, respectively. To the best of our knowledge, our algorithm is the first efficient rate optimal regret minimization algorithm for adversarial CMDPs that operates under the minimal standard assumption of online function approximation.We present the OMG-CMDP! algorithm for regret minimization in adversarial Contextual MDPs. The algorithm operates under the minimal assumptions of realizable function class and access to online least squares and log loss regression oracles. Our algorithm is efficient (assuming efficient online regression oracles), simple and robust to approximation errors. It enjoys an O(H^2.5√( T|S||A| ( ℛ(𝒪)+ H log(δ^-1) ))) regret guarantee, with T being the number of episodes, S the state space, A the actio…
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
Nonparametric Generative Modeling with Conditional Sliced-Wasserstein Flows
Watch later
Chao Du, …
Data Poisoning Attacks Against Multimodal Encoders
Watch later
Ziqing Yang, …
On the Relationship Between Explanation and Prediction: A Causal View
Watch later
Denoising MCMC for Accelerating Diffusion-Based Generative Models
Watch later
Beomsu Kim, …
