Timezone: »

 
Poster
Near-Optimal Representation Learning for Linear Bandits and Linear RL
Jiachen Hu · Xiaoyu Chen · Chi Jin · Lihong Li · Liwei Wang

Wed Jul 21 09:00 PM -- 11:00 PM (PDT) @ Virtual
in Poster Session 4 »
This paper studies representation learning for multi-task linear bandits and multi-task episodic RL with linear value function approximation. We first consider the setting where we play $M$ linear bandits with dimension $d$ concurrently, and these bandits share a common $k$-dimensional linear representation so that $k\ll d$ and $k \ll M$. We propose a sample-efficient algorithm, MTLR-OFUL, which leverages the shared representation to achieve $\tilde{O}(M\sqrt{dkT} + d\sqrt{kMT} )$ regret, with $T$ being the number of total steps. Our regret significantly improves upon the baseline $\tilde{O}(Md\sqrt{T})$ achieved by solving each task independently. We further develop a lower bound that shows our regret is near-optimal when $d > M$. Furthermore, we extend the algorithm and analysis to multi-task episodic RL with linear value function approximation under low inherent Bellman error (Zanette et al., 2020a). To the best of our knowledge, this is the first theoretical result that characterize the benefits of multi-task representation learning for exploration in RL with function approximation.
Keywords: Online Learning Theory
[ Slides] 

Author Information

Jiachen Hu (Peking University)
Xiaoyu Chen (Peking University)
Chi Jin (Princeton University)
Lihong Li (Amazon)
Liwei Wang (Peking University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors