Timezone: »

 
Poster
Tractable Optimality in Episodic Latent MABs
Jeongyeol Kwon · Yonathan Efroni · Constantine Caramanis · Shie Mannor

Thu Dec 01 09:00 AM -- 11:00 AM (PST) @ Hall J #533
in Poster Session 5 »
We consider a multi-armed bandit problem with $M$ latent contexts, where an agent interacts with the environment for an episode of $H$ time steps. Depending on the length of the episode, the learner may not be able to estimate accurately the latent context. The resulting partial observation of the environment makes the learning task significantly more challenging. Without any additional structural assumptions, existing techniques to tackle partially observed settings imply the decision maker can learn a near-optimal policy with $O(A)^H$ episodes, but do not promise more. In this work, we show that learning with {\em polynomial} samples in $A$ is possible. We achieve this by using techniques from experiment design. Then, through a method-of-moments approach, we design a procedure that provably learns a near-optimal policy with $O(\poly(A) + \poly(M,H)^{\min(M,H)})$ interactions. In practice, we show that we can formulate the moment-matching via maximum likelihood estimation. In our experiments, this significantly outperforms the worst-case guarantees, as well as existing practical methods.
Keywords: Latent Variable Models · Multi-armed Bandits · experimental design · partially observable MDPs · method-of-moments · maximum likelihood estimation

Author Information

Jeongyeol Kwon (University of Wisconsin - Madison)
Yonathan Efroni (Microsoft Research, New York)
Constantine Caramanis (UT Austin)
Shie Mannor (Technion)

More from the Same Authors