Timezone: »

 
Poster
Oracle-Efficient Regret Minimization in Factored MDPs with Unknown Structure
Aviv Rosenberg · Yishay Mansour

Thu Dec 09 08:30 AM -- 10:00 AM (PST) @
in Poster Session 6 »

We study regret minimization in non-episodic factored Markov decision processes (FMDPs), where all existing algorithms make the strong assumption that the factored structure of the FMDP is known to the learner in advance. In this paper, we provide the first algorithm that learns the structure of the FMDP while minimizing the regret. Our algorithm is based on the optimism in face of uncertainty principle, combined with a simple statistical method for structure learning, and can be implemented efficiently given oracle-access to an FMDP planner. Moreover, we give a variant of our algorithm that remains efficient even when the oracle is limited to non-factored actions, which is the case with almost all existing approximate planners. Finally, we leverage our techniques to prove a novel lower bound for the known structure case, closing the gap to the regret bound of Chen et al. [2021].

Keywords: Theory · Reinforcement Learning and Planning · Online Learning

Author Information

Aviv Rosenberg (Tel Aviv University)
Aviv Rosenberg

I am an Applied Scientist at Amazon Alexa Shopping, Tel Aviv. Previously, I obtained my PhD from the department of computer science at Tel Aviv University, where I was fortunate to have Prof. Yishay Mansour as my advisor. Prior to that, I received my Bachelor's degree in Mathematics and Computer Science from Tel Aviv University. My primary research interest lies in theoretical and applied machine learning. More specifically, my PhD focused on data-driven sequential decision making such as reinforcement learning, online learning and multi-armed bandit.

Yishay Mansour (Tel Aviv University & Google)

More from the Same Authors