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 guarantees convergence when used with FVI. To ensure convergence, we constrain the least squares regression operator to be a non-expansion in the infinity-norm. We show that the space of function approximators that satisfy this constraint is more rich than the space of "averagers," we prove a minimax property of the ECOLS residual error, and we give an efficient algorithm for computing the coefficients of ECOLS based on constraint generation. We illustrate the algorithmic convergence of FVI with ECOLS in a suite of experiments, and discuss its properties.

📄 PDF Abstract BibTeX

Code (0)

등록된 구현이 없습니다.

Tasks

regression

Finite-Sample Analysis for SARSA with Linear Function Approximation

2019-02-06 · NeurIPS 2019 12 · Shaofeng Zou, Tengyu Xu, Yingbin Liang

SARSA is an on-policy algorithm to learn a Markov decision process policy in reinforcement learning. We investigate the SARSA algorithm with linear function approximation under the non-i.i.d.\ data, where a single sample…

Q-Learning Reinforcement Learning

Fitted Value Iteration Methods for Bicausal Optimal Transport

2023-06-22 · Erhan Bayraktar, Bingyan Han

We develop a fitted value iteration (FVI) method to compute bicausal optimal transport (OT) where couplings have an adapted structure. Based on the dynamic programming formulation, FVI adopts a function class to approxim…

A New Policy Iteration Algorithm For Reinforcement Learning in Zero-Sum Markov Games

2023-03-17 · Anna Winnicki, R. Srikant

Optimal policies in standard MDPs can be obtained using either value iteration or policy iteration. However, in the case of zero-sum Markov games, there is no efficient policy iteration algorithm; e.g., it has been shown…

Model-based Reinforcement Learning Multi-agent Reinforcement Learning reinforcement-learning Reinforcement Learning (RL)

Logically-Constrained Neural Fitted Q-Iteration

2018-09-20 · Mohammadhosein Hasanbeig, Alessandro Abate, Daniel Kroening

We propose a method for efficient training of Q-functions for continuous-state Markov Decision Processes (MDPs) such that the traces of the resulting policies satisfy a given Linear Temporal Logic (LTL) property. LTL, a …

Robust Value Function Approximation Using Bilinear Programming

2009-12-01 · NeurIPS 2009 12 · Marek Petrik, Shlomo Zilberstein

Existing value function approximation methods have been successfully used in many applications, but they often lack useful a priori error bounds. We propose approximate bilinear programming, a new formulation of value fu…