# Global Optimization For Value Function Approximation

Marek Petrik petrik@cs.umass.edu Department of Computer Science University of Massachusetts Amherst, MA 01003, USA
Shlomo Zilberstein shlomo@cs.umass.edu Department of Computer Science University of Massachusetts Amherst, MA 01003, USA

## Editor: Abstract

Existing value function approximation methods have been successfully used in many applications, but they often lack useful a priori error bounds. We propose a new approximate bilinear programming formulation of value function approximation, which employs global optimization. The formulation provides strong a priori guarantees on both robust and expected policy loss by minimizing specific norms of the Bellman residual. Solving a bilinear program optimally is NP-hard, but this is unavoidable because the Bellman-residual minimization itself is NP-hard. We describe and analyze both optimal and approximate algorithms for solving bilinear programs. The analysis shows that this algorithm offers a *convergent* generalization of approximate policy iteration. We also briefly analyze the behavior of bilinear programming algorithms under incomplete samples. Finally, we demonstrate that the proposed approach can consistently minimize the Bellman residual on simple benchmark problems.

Keywords: value function approximation, Markov decision processes, reinforcement learning, approximate dynamic programming

## 1. Motivation

Solving large Markov Decision Problems (MDPs) is a very useful, but computationally challenging problem addressed widely in the AI literature, particularly in the area of reinforcement learning. It is widely accepted that large MDPs can only be solved approximately.

The commonly used approximation methods can be divided into three broad categories: 1)
policy search, which explores a restricted space of all policies, 2) *approximate dynamic programming*, which searches a restricted space of value functions, and 3) *approximate linear* programming, which approximates the solution using a linear program. While all of these methods have achieved impressive results in many application domains, they have significant limitations.

Policy search methods rely on local search in a restricted policy space. The policy may be represented, for example, as a finite-state controller (Stanley and Miikkulainen, 2004) or as a greedy policy with respect to an approximate value function (Szita and Lorincz, 2006). Policy search methods have achieved impressive results in such domains as Tetris (Szita and