Tree-Based On-Line Reinforcement Learning.

André da Motta Salles BarretoAAAI 2014 · OpenReview

Abstract

Fitted Q-iteration (FQI) stands out among reinforcement learning algorithms for its flexibility and ease of use. FQI can be combined with any regression method, and this choice determines the algorithm's statistical and computational properties. The combination of FQI with an ensemble of regression trees gives rise to an algorithm, FQIT, that is computationally efficient, scalable to high dimensional spaces, and robust to noise. Despite its nice properties and good performance in practice, FQIT also has some limitations: the fact that an ensemble of trees must be constructed (or updated) at each iteration confines the algorithm to the batch scenario. This paper aims to address this specific issue. Based on a strategy recently proposed in the literature, called the stochastic-factorization trick, we propose a modification of FQIT that makes it fully incremental, and thus suitable for on-line learning. We call the resulting method tree-based stochastic factorization (TBSF). We derive upper bounds for the difference between the value functions computed by FQIT and TBSF, and also show in which circumstances the approximations coincide. A series of computational experiments is presented to illustrate the properties of TBSF and to show its usefulness in practice, including a medical problem involving the treatment of patients infected with HIV.

Introduction

Reinforcement Learning (RL) agents learn optimal decision-making policies through interaction with an environment. Among practical RL algorithms, Fitted Q-Iteration (FQI) is highly regarded, particularly when implemented with ensembles of regression trees (FQIT). This approach is favored for its robustness to noise and its ability to navigate high-dimensional state spaces.

However, FQIT faces a significant hurdle in dynamic environments: it is fundamentally a batch algorithm. It requires a fixed dataset to construct its trees, and as new data arrives, the entire ensemble must be rebuilt or extensively updated. This computational overhead makes FQIT unsuitable for online learning, where agents must learn and act simultaneously. This paper introduces Tree-Based Stochastic Factorization (TBSF) to bridge this gap, enabling the power of tree-based RL for real-time, incremental applications.

Methodology: The Stochastic-Factorization Trick

The core innovation of TBSF is the application of the "stochastic-factorization trick" to regression trees. The method proceeds in four key steps:

  1. Factorization: The transition matrix of a Markov Decision Process (MDP) is factored into two smaller stochastic matrices.
  2. Trees as Discretizers: The paper proves that the partitions (leaves) of a regression tree ensemble provide an exact factorization of the FQIT model. The tree structure effectively defines a compressed, abstract version of the environment.
  3. Abstract MDP: Instead of performing value iterations over every individual transition in a massive dataset, TBSF operates on a compact "abstract" MDP where the states are the tree partitions.
  4. Incremental Updates: TBSF uses specific mathematical rules to update this abstract model as new transitions arrive. Raw samples can be discarded immediately after processing, significantly reducing memory and time requirements.

While standard FQIT re-optimizes its tree structure at every iteration, the basic TBSF keeps the structure fixed but updates the values within that structure incrementally.

Empirical Evaluation and Scalability

The algorithm was tested on two benchmarks: the classic Mountain Car problem and a complex, 6-dimensional HIV Domain simulation involving drug-scheduling optimization.

Computational time (seconds) as a function of the number of samples n for FQIT (black) and TBSF (blue dots).

A primary result of these experiments is the massive speedup achieved by TBSF. As shown in the figure above, the computational cost of FQIT grows sharply with the number of samples ($n$). In contrast, TBSF's complexity is decoupled from $n$ and instead depends on the number of tree partitions ($m$). Since $m \ll n$, TBSF processes data orders of magnitude faster than the batch-based FQIT.

Real-World Application: HIV Treatment

In the HIV domain, the trade-off between data efficiency and time efficiency becomes clear. While FQIT may extract more information from a very small, fixed dataset, TBSF's speed allows it to process significantly more data in the same timeframe.

Performance comparison in the HIV domain: Return vs. computation time for varying patient sample sizes.

As illustrated in the HIV domain results, TBSF could process data from 600 patients in the time FQIT required for only 30 patients. By leveraging this increased volume of data, TBSF produced treatment policies of comparable quality to the much slower batch algorithm, demonstrating its utility in high-stakes, data-rich environments.

Conclusion

TBSF successfully transforms tree-based FQI into a scalable, online learning algorithm. While the current version relies on a fixed tree structure (which may limit performance if the initial "seed" data is poor), it offers a mathematically grounded and computationally efficient alternative for real-time RL. Future work on "Adaptive TBSF," which occasionally updates tree structures, promises to combine the flexibility of FQIT with the unprecedented speed of stochastic factorization.

Summary updated

Abstract

Fitted Q-iteration (FQI) stands out among reinforcement learning algorithms for its flexibility and ease of use. FQI can be combined with any regression method, and this choice determines the algorithm's statistical and computational properties. The combination of FQI with an ensemble of regression trees gives rise to an algorithm, FQIT, that is computationally efficient, scalable to high dimensional spaces, and robust to noise. Despite its nice properties and good performance in practice, FQIT also has some limitations: the fact that an ensemble of trees must be constructed (or updated) at each iteration confines the algorithm to the batch scenario. This paper aims to address this specific issue. Based on a strategy recently proposed in the literature, called the stochastic-factorization trick, we propose a modification of FQIT that makes it fully incremental, and thus suitable for on-line learning. We call the resulting method tree-based stochastic factorization (TBSF). We derive upper bounds for the difference between the value functions computed by FQIT and TBSF, and also show in which circumstances the approximations coincide. A series of computational experiments is presented to illustrate the properties of TBSF and to show its usefulness in practice, including a medical problem involving the treatment of patients infected with HIV.
BibTeX
@inproceedings{barreto2014tree,
  author = {André da Motta Salles Barreto},
  title = {{Tree-Based On-Line Reinforcement Learning.}},
  booktitle = {AAAI},
  year = {2014},
  url = {https://openreview.net/forum?id=9KB1jWk-xQN},
}
Figure