Online Sparse Reinforcement Learning

Abstract

We investigate the hardness of online reinforcement learning in fixed horizon, sparse linear Markov decision process (MDP), with a special focus on the high-dimensional regime where the ambient dimension is larger than the number of episodes. Our contribution is two-fold. First, we provide a lower bound showing that linear regret is generally unavoidable in this case, even if there exists a policy that collects well-conditioned data. The lower bound construction uses an MDP with a fixed number of states while the number of actions scales with the ambient dimension. Note that when the horizon is fixed to one, the case of linear stochastic bandits, the linear regret can be avoided. Second, we show that if the learner has oracle access to a policy that collects well-conditioned data then a variant of Lasso fitted Q-iteration enjoys a nearly dimension-free regret of \(\tilde\{O\}( s^\{2/3\} N^\{2/3\})\) where \(N\) is the number of episodes and \(s\) is the sparsity level. This shows that

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyhao2020online

Related papers

• Online Reinforcement Learning In Markov Decision Process Using Linear Programming (2023)3.58
• Efficient Learning In Non-stationary Linear Markov Decision Processes (2020)6.77
• Nearly Horizon-free Offline Reinforcement Learning (2021)0.00
• Nearly Minimax Optimal Reinforcement Learning For Linear Markov Decision Processes (2022)0.00
• Dynamic Regret Of Online Markov Decision Processes (2022)0.00
• Towards Optimal Regret In Adversarial Linear Mdps With Bandit Feedback (2023)0.00
• Refined Regret For Adversarial Mdps With Linear Function Approximation (2023)0.00
• Online Learning In Mdps With Linear Function Approximation And Bandit Feedback (2020)0.00