Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing

2021-05-18 · Anshumali Shrivastava, Zhao Song, Zhaozhuo Xu

We present the first provable Least-Squares Value Iteration (LSVI) algorithms that have runtime complexity sublinear in the number of actions. We formulate the value function estimation procedure in value iteration as an approximate maximum inner product search problem and propose a locality sensitive hashing (LSH) [Indyk and Motwani STOC'98, Andoni and Razenshteyn STOC'15, Andoni, Laarhoven, Razenshteyn and Waingarten SODA'17] type data structure to solve this problem with sublinear time complexity. Moreover, we build the connections between the theory of approximate maximum inner product search and the regret analysis of reinforcement learning. We prove that, with our choice of approximation factor, our Sublinear LSVI algorithms maintain the same regret as the original LSVI algorithms while reducing the runtime complexity to sublinear in the number of actions. To the best of our knowledge, this is the first work that combines LSH with reinforcement learning resulting in provable improvements. We hope that our novel way of combining data-structures and iterative algorithm will open the door for further study into cost reduction in optimization.

📄 PDF Abstract BibTeX arXiv:2105.08285

Code (0)

등록된 구현이 없습니다.

Tasks

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

A Randomised Subspace Gauss-Newton Method for Nonlinear Least-Squares

2022-11-10 · Coralia Cartis, Jaroslav Fowkes, Zhen Shao

We propose a Randomised Subspace Gauss-Newton (R-SGN) algorithm for solving nonlinear least-squares optimization problems, that uses a sketched Jacobian of the residual in the variable domain and solves a reduced linear …

regression

SPALS: Fast Alternating Least Squares via Implicit Leverage Scores Sampling

2016-12-01 · NeurIPS 2016 12 · Dehua Cheng, Richard Peng, Yan Liu, Ioakeim Perros

Tensor CANDECOMP/PARAFAC (CP) decomposition is a powerful but computationally challenging tool in modern data analytics. In this paper, we show ways of sampling intermediate steps of alternating minimization algorithms f…

Randomised Bayesian Least-Squares Policy Iteration

2019-04-06 · Nikolaos Tziortziotis, Christos Dimitrakakis, Michalis Vazirgiannis

We introduce Bayesian least-squares policy iteration (BLSPI), an off-policy, model-free, policy iteration algorithm that uses the Bayesian least-squares temporal-difference (BLSTD) learning algorithm to evaluate policies…

Thompson Sampling

Improved Worst-Case Regret Bounds for Randomized Least-Squares Value Iteration

2020-10-23 · Priyank Agrawal, Jinglin Chen, Nan Jiang

This paper studies regret minimization with randomized value functions in reinforcement learning. In tabular finite-horizon Markov Decision Processes, we introduce a clipping variant of one classical Thompson Sampling (T…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)Thompson Sampling

Convergent Fitted Value Iteration with Linear Function Approximation

2011-12-01 · NeurIPS 2011 12 · Daniel J. Lizotte

Fitted value iteration (FVI) with ordinary least squares regression is known to diverge. We present a new method, "Expansion-Constrained Ordinary Least Squares" (ECOLS), that produces a linear approximation but also guar…