Seminar: Machine Learning Seminar

ECE Women Community

Efficient Rate Optimal Regret for Adversarial Contextual MDPs Using Online Function Approximation

Date: June,07,2023 Start Time: 10:30 - 11:30
Location: 1061, Meyer Building
Add to:
Lecturer: Orin Levy
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 $\widetilde{O}(H^{2.5} \sqrt{ T|S||A| ( \mathcal{R}_{TH}(\mathcal{O})+ H \log(\delta^{-1}) )})$ regret guarantee, with $T$ being the number of episodes, $S$ the state space, $A$ the action space, $H$ the horizon and $\mathcal{R}_{TH}(\mathcal{O}) = \mathcal{R}_{TH}(\mathcal{O}_{\mathrm{sq}}^\mathcal{F}) + \mathcal{R}_{TH (\mathcal{O}_{\mathrm{log}}^\mathcal{P})$ is the sum of the square and log-loss 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. This is a joint work with Alon Cohen, Asaf Cassel and Yishay Mansour , which will be presented in ICML 2023.

Orin Levy is a Ph.D. student at TAU under the supervision of Prof. Yishay Mansour.

 

All Seminars
Skip to content