Timezone: »

 
Poster
Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes
Jiafan He · Heyang Zhao · Dongruo Zhou · Quanquan Gu

Thu Jul 27 04:30 PM -- 06:00 PM (PDT) @ Exhibit Hall 1 #603
in Poster Session 6 »
We study reinforcement learning (RL) with linear function approximation. For episodic time-inhomogeneous linear Markov decision processes (linear MDPs) whose transition probability can be parameterized as a linear function of a given feature mapping, we propose the first computationally efficient algorithm that achieves the nearly minimax optimal regret $\tilde O(d\sqrt{H^3K})$, where $d$ is the dimension of the feature mapping, $H$ is the planning horizon, and $K$ is the number of episodes. Our algorithm is based on a weighted linear regression scheme with a carefully designed weight, which depends on a new variance estimator that (1) directly estimates the variance of the *optimal* value function, (2) monotonically decreases with respect to the number of episodes to ensure a better estimation accuracy, and (3) uses a rare-switching policy to update the value function estimator to control the complexity of the estimated value function class. Our work provides a complete answer to optimal RL with linear MDPs, and the developed algorithm and theoretical tools may be of independent interest.
[ PDF] 

Author Information

Jiafan He (University of California, Los Angeles)
Heyang Zhao (Computer Science Department, University of California, Los Angeles)
Dongruo Zhou (UCLA)
Quanquan Gu (University of California, Los Angeles)

More from the Same Authors