Efficient Local Planning with Linear Function Approximation

Abstract

We study query and computationally efficient planning algorithms with linear function approximation and a simulator. We assume that the agent only has local access to the simulator, meaning that the agent can only query the simulator at states that have been visited before. This setting is more practical than many prior works on reinforcement learning with a generative model. We propose two algorithms, named confident Monte Carlo least square policy iteration (Confident MC-LSPI) and confident Monte Carlo Politex (Confident MC-Politex) for this setting. Under the assumption that the Q-functions of all policies are linear in known features of the state-action pairs, we show that our algorithms have polynomial query and computational costs in the dimension of the features, the effective planning horizon, and the targeted sub-optimality, while these costs are independent of the size of the state space. One technical contribution of our work is the introduction of a novel proof technique that makes use of a virtual policy iteration algorithm. We use this method to leverage existing results on ${\ell }_{\infty }$-bounded approximate policy iteration to show that our algorithm can learn the optimal policy for the given initial state even only with local access to the simulator. We believe that this technique can be extended to broader settings beyond this work.

Algorithmic Learning Theory 2022

References in corpus (15)

• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• Model-Based Reinforcement Learning with Value-Targeted Regression
• Learning Near Optimal Policies with Low Inherent Bellman Error
• Optimism in Reinforcement Learning with Generalized Linear Function Approximation
• Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms
• PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learning
• Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping
• Comments on the Du-Kakade-Wang-Yang Lower Bounds
• Bilinear Classes: A Structural Framework for Provable Generalization in RL
• Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functions
• Efficient Planning in Large MDPs with Weak Linear Function Approximation
• An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap
• Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisiting
• On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Function
• Improved Regret Bound and Experience Replay in Regularized Policy Iteration

Cited by in corpus (1)

• Improved Algorithms for Misspecified Linear Markov Decision Processes