Exploratory Gradient Boosting for Reinforcement Learning in Complex Domains

Motivation

• High-dimensional observations and complex dynamics make efficient reinforcement learning difficult, as illustrated by navigating to the highest terrain from raw visual input.The paper identifies these challenges as important for real-world domains.Source: §1 · p. 1, Figure 1 · p. 1
• Existing approaches struggle in these settings because linear function approximation cannot scale to visual input, while deep Q-learning uses relatively simple exploration strategies.Source: §1 · p. 1

Function approximation

• The paper introduces a non-parametric gradient-boosting function approximator adapted to reinforcement learning and trained on Q-function residuals.Unlike deep-learning approaches, the proposed boosting models are described as trainable and usable on a single laptop rather than requiring GPUs.Source: §1 · p. 1

Exploration

• The complementary IAUU-inspired exploration tactic improves over ε-uniform exploration by incentivizing novel action applications.The two techniques are combined in Generalized Exploratory Q-learning (GEQL).Source: §1 · p. 1

Empirical evaluation

• GEQL consistently and substantially outperforms the baseline on two large Minecraft tasks with high-dimensional visual observations, while remaining competitive on Blackjack and n-Chain.The evaluation covers two standard RL domains and two Minecraft tasks whose observations are pixel arrays of the agent’s visual field.Source: §1 · pp. 1–2

Function approximation

• The paper adopts gradient-boosted regression trees rather than neural-network architectures, differing from prior reinforcement-learning ensembles that use independently trained agents.Gradient-boosted trees are presented as a non-parametric regression class with competitive supervised-learning performance.Source: §2 · p. 2
• Interleaving boosting iterations with adaptive data collection distinguishes the method from Fitted Q-Iteration and significantly outperforms it in experiments.The current Q-function guides subsequent data collection, which drives the next update.Source: §2 · p. 2

Exploration

• The exploration strategy uses a compact state model only for exploration, so model compression does not compromise the learning algorithm’s policy expressivity.This contrasts with typical state-abstraction approaches that use the abstraction for both exploration and policy learning.Source: §2 · p. 2
• Other exploration approaches use predictive models, optimism or uncertainty bonuses, or known metric structure, whereas constructing such structure generally remains unclear.These approaches include [Oh et al., 2015], [Xie et al., 2015], [Stadie et al., 2015], [Guez et al., 2012], and.Source: §2 · p. 2

3 The GEQL Algorithm

• GEQL has two complementary components: gradient-boosting function approximation and model-compression-based exploration.Source: §3 · p. 2

3.1 The setting

• The setting assumes discounted model-free reinforcement learning with observable states, while noting that realistic observations may instead be partial or history-based.Source: §3.1 · p. 2

3.2 Boosting-based Q-function approximation

• Each episode uses the current Q-function to guide behavior, collects state-action-reward trajectories, and fits a regressor to residuals from one-step look-ahead targets.Source: §3.2 · p. 3
• The fitted weak regressor is added to the current Q-function, enabling nonlinear non-parametric approximation with batch updates and discarded trajectories after each update.Source: §3.2 · p. 3

3.3 The IAUU exploration strategy

• IAUU clusters states with a state-collapsing function, tracks action counts per cluster, and samples less frequent actions during exploratory steps while otherwise acting greedily.Source: §3.3 · p. 3
• Using the state-collapsing function only for exploration makes IAUU robust to misspecification and gives it O(m|A|) space with O(|A|) additional time per action.Source: §3.3 · p. 3
• IAUU can also be paired with tabular Q-learning, with modifications that preserve convergence by ensuring every action is taken from every state infinitely often.Source: §3.3 · p. 3

4 Experiments on Standard Benchmarks

• The standard-benchmark evaluation covered Blackjack and n-Chain, testing function approximation and exploration under both low-dimensional and tabular settings.Blackjack used linear, batchboost, and forest baselines alongside the booster, while n-Chain used tabular Q-learning with uniform or IAUU exploration and RMAX.Source: §4 · p. 4, §4.1 · p. 4, §4.2 · p. 4

4.1 Blackjack

• Gradient boosting significantly outperformed linear and both batch approximators on Blackjack, while exploration had negligible effect.The experiments used 100 trials over 500 episodes, and the small action space and short episodes likely limited exploration differences.Source: §4.1 · p. 4

4.2 n-Chain

• RMAX significantly outperformed IAUU and uniform-exploration tabular Q-learning on n-Chain by seeking state-action applications and quickly discovering the terminal high reward.The comparison used 5000 trials.Source: §4.2 · p. 4, Figure 3 · p. 4
• IAUU occupied an intermediate position in n-Chain: it generalized to extremely large state spaces unlike RMAX while exploring more effectively than ε-uniform exploration.Uniform exploration discovers the terminal reward only with exponentially small probability because the agent favors the greedy return action and must repeatedly explore forward.Source: §4.2 · pp. 4–5

5 Experiments on Visual Domains

• The visual experiments use Minecraft because its large state space and changing visual conditions make tabular planning and learning infeasible.AIX provides control over agent actions, perception, and world design for the two benchmark tasks.Source: §5 · p. 5

5.1 Implementation Details

• Minecraft observations begin as 320 × 240 RGB images and are transformed through key-point features, a 3 × 3 spatial partition, and an occupancy grid.A separate offline k-means state-collapsing function maps feature vectors to cluster centers for IAUU exploration.Source: §5.1 · p. 5

5.2 Visual Grid World

• Visual Grid World is a deterministic 6 × 6 navigation task using raw visual input plus occupancy features, with reward equal to the negative Euclidean distance from the goal.The optimal direct policy receives roughly −31 reward.Source: §5.2 · p. 5, Figure 4 · p. 6
• GEQL, combining the gradient booster with IAUU, substantially improved Visual Grid World performance over prior baselines.Booster with IAUU averaged −34.22 after 100 episodes, near the optimal policy’s roughly −31 reward, versus −82.77 for booster with uniform exploration and around −119.5 for the best baseline.Source: §5.2 · p. 6, Figure 5 · p. 6

5.3 Visual Hill Climbing

• In Visual Hill Climbing, only the gradient booster showed non-negligible learning, and IAUU further helped it learn a policy producing positive reward.The task uses a complex partially observable 3D world with occlusion, varied terrain, and obstacles that can make some hills unreachable.Source: §5.3 · p. 6, Figure 6 · p. 7
• The booster with IAUU reliably reached much higher elevations in the final quarter than in the initial quarter of Visual Hill Climbing episodes.Elevation profiles compare booster and forest over successive groups of 25 episodes, with effective behavior indicated by increasing elevation.Source: §5.3 · p. 6, Figure 7 · p. 7

• Gradient boosting coupled with favorable computational properties appears promising, motivating future comparison with more computationally intensive deep-learning approaches.Source: §6 · p. 7
• Extending gradient-boosting theory from supervised learning to reinforcement learning is identified as a natural future research question.Source: §6 · p. 7
• IAUU improves over ϵ-uniform exploration but remains limited by its state-collapsing function and can be suboptimal when the least-frequent action is bad.Source: §6 · p. 7
• Minecraft offers a framework for visual versions of standard reinforcement-learning tasks, with opportunities to test additional learning abilities and examine the gap to human performance.Source: §6 · p. 7