Bellman Error Based Feature Generation using Random Projections on Sparse Spaces

2013-12-01 · NeurIPS 2013 12 · Mahdi Milani Fard, Yuri Grinberg, Amir-Massoud Farahmand, Joelle Pineau, Doina Precup

This paper addresses the problem of automatic generation of features for value function approximation in reinforcement learning. Bellman Error Basis Functions (BEBFs) have been shown to improve the error of policy evaluation with function approximation, with a convergence rate similar to that of value iteration. We propose a simple, fast and robust algorithm based on random projections, which generates BEBFs for sparse feature spaces. We provide a finite sample analysis of the proposed method, and prove that projections logarithmic in the dimension of the original space guarantee a contraction in the error. Empirical results demonstrate the strength of this method in domains in which choosing a good state representation is challenging.

📄 PDF Abstract BibTeX

Code (0)

등록된 구현이 없습니다.

Tasks

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

LSTD with Random Projections

2010-12-01 · NeurIPS 2010 12 · Mohammad Ghavamzadeh, Alessandro Lazaric, Odalric Maillard, Rémi Munos

We consider the problem of reinforcement learning in high-dimensional spaces when the number of features is bigger than the number of samples. In particular, we study the least-squares temporal difference (LSTD) learning…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Fast Summation of Radial Kernels via QMC Slicing

2024-10-02 · Johannes Hertrich, Tim Jahn, Michael Quellmalz

The fast computation of large kernel sums is a challenging task, which arises as a subproblem in any kernel method. We approach the problem by slicing, which relies on random projections to one-dimensional subspaces and …

DUAL-LOCO: Distributing Statistical Estimation Using Random Projections

2015-06-08 · Christina Heinze, Brian McWilliams, Nicolai Meinshausen

We present DUAL-LOCO, a communication-efficient algorithm for distributed statistical estimation. DUAL-LOCO assumes that the data is distributed according to the features rather than the samples. It requires only a singl…

Distributed Optimization

Ternary and Binary Quantization for Improved Classification

2022-03-31 · Weizhi Lu, Mingrui Chen, Kai Guo, Weiyu Li

Dimension reduction and data quantization are two important methods for reducing data complexity. In the paper, we study the methodology of first reducing data dimension by random projection and then quantizing the proje…

Classification Dimensionality Reduction Quantization

Computationally Efficient RL under Linear Bellman Completeness for Deterministic Dynamics

2024-06-17 · Runzhe Wu, Ayush Sekhari, Akshay Krishnamurthy, Wen Sun

We study computationally and statistically efficient Reinforcement Learning algorithms for the linear Bellman Complete setting. This setting uses linear function approximation to capture value functions and unifies exist…