Source-linked AI summary
Hybrid Reward Architecture for Reinforcement Learning
Harm van Seijen, Mehdi Fatemi, Joshua Romoff, Romain Laroche, Tavian Barnes, Jeffrey Tsang
TL;DR
RL generalisation becomes difficult when the optimal value function is too complex for a low-dimensional representation. HRA decomposes rewards and learns separate value functions for the components, achieving above-human performance in the evaluated tasks. The approach depends on a suitable decomposition and does not generally produce an environment-optimal value function.
Problem
RL methods can struggle when the optimal value function cannot easily be reduced to a low-dimensional representation, making efficient generalisation difficult.
Method
HRA decomposes the environment reward and trains separate value functions for its components, whose action-values are aggregated for control.
Results
HRA’s domain-knowledge-based decomposition addresses the underlying value-function difficulty in Ms. Pac-Man, where HRA learns about 1,800 general value functions and reduces each to a state space on the order of 10^3 states.
Takeaways & Limitations
HRA achieved above-human performance on the evaluated toy and Atari tasks, including 999,990 points in Ms. Pac-Man under a fixed-start evaluation using simplified executive memory.
Takeaways & Limitations
HRA’s decomposition should make each component depend mainly on a small number of state variables, and its aggregated value function is generally not consistent with the environment reward.
Abstract
from arXiv · showhide
One of the main challenges in reinforcement learning (RL) is generalisation. In typical deep RL methods this is achieved by approximating the optimal value function with a low-dimensional representation using a deep network. While this approach works well in many domains, in domains where the optimal value function cannot easily be reduced to a low-dimensional representation, learning can be very slow and unstable. This paper contributes towards tackling such challenging domains, by proposing a new method, called Hybrid Reward Architecture (HRA). HRA takes as input a decomposed reward function and learns a separate value function for each component reward function. Because each component typically only depends on a subset of all features, the corresponding value function can be approximated more easily by a low-dimensional representation, enabling more effective learning. We demonstrate HRA on a toy-problem and the Atari game Ms. Pac-Man, where HRA achieves above-human performance.
1 Introduction
RL must generalise across massive state spaces, but approximating a complex optimal value function can be difficult. HRA addresses this by decomposing rewards and learning separate value functions, evaluated on a toy task and Ms. Pac-Man.
- Large real-world RL problems require strong generalisation because their state spaces are typically massive.
- Deep RL methods such as DQN generalise by approximating the optimal value function with a low-dimensional representation.The value function predicts expected return from a state or state-action pair, enabling greedy policy derivation.
- When the optimal value function is too complex for a low-dimensional representation, learning can become challenging or impossible.HRA therefore regularises the target side by using an easier-to-learn value function that may yield a good but non-optimal policy.
- HRA decomposes the environment reward into components, trains a separate reinforcement-learning agent for each, and aggregates their action-values.The agents can learn in parallel from the same sample sequence using off-policy learning.
- HRA is evaluated on a fruit-collection toy problem and the Atari game Ms. Pac-Man.
2 Related Work
HRA relates to several approaches that decompose tasks, rewards, or learning objectives, but differs in targeting efficient control of a single complex reward through simpler value functions.
- HRA builds on Horde’s parallel off-policy demons but trains separate components of the environment reward to learn a control policy.Horde instead develops general knowledge through general value functions based on separate policies and pseudo-rewards.
- Unlike UVFA, which generalises across tasks or goals, HRA focuses on solving one complex task.
- HRA can be viewed as applying multi-objective learning to learn a policy for a single reward function more efficiently.
- Earlier reward-decomposition methods pursued optimal behaviour, whereas HRA prioritises learning efficiency by using simpler value functions and relaxing optimality requirements.
- UNREAL uses auxiliary tasks to improve deep-network representations, while HRA breaks the main task into directly relevant smaller tasks.HRA is agnostic to the function approximator and can work with exact tabular representations.
- Diuk’s object-oriented approach efficiently learns a compact transition model and solves it with dynamic programming, but does not reduce the state space.
- Options resemble HRA heads because both can train in parallel using intrinsic rewards, but options’ intrinsic rewards no longer guide the higher-level agent after training.
3 Model
The model defines RL value estimation and introduces HRA as a reward-decomposed collection of value-function heads whose action-values are aggregated. Its alternative targets can be easier to learn, but the resulting policy is not generally optimal or fully consistent with the environment reward.
- An MDP specifies states, actions, transitions, environment rewards, and discounting; policies select actions and aim to maximise discounted return.
- DQN estimates the optimal action-value function with a neural-network approximator and minimises successive loss functions.A separate target network encodes the previous iteration’s weights.
- A training target is consistent when its greedy policy is environment-optimal, while a semi-consistent target yields a good but non-optimal policy.
- Consistency does not guarantee learnability: sparse or high-dimensional environment rewards can make the default optimal target difficult to learn.
- Hybrid Reward Architecture: HRA decomposes the environment reward into n components and trains a separate value function for each component.The decomposition is intended to make each value function depend mainly on a small number of state variables.
- Hybrid Reward Architecture: HRA combines the component action-values into QHRA and selects actions greedily according to their sum.The agents may share lower-level network layers and can be viewed as multiple heads of one agent.
- Hybrid Reward Architecture: The HRA heads approximate component-specific optimal action-values, while their aggregate generally differs from the environment’s optimal action-value function.
- Alternative training target: An alternative target evaluates the uniformly random policy under each component reward, and its greedy policy can be surprisingly effective in navigation domains.This target is learned with an expected Sarsa update.
4 Experiments
The experiments evaluate HRA on fruit collection and Ms. Pac-Man, testing reward decomposition, domain knowledge, exploration, preprocessing, and memory. HRA achieves strong performance, including above-human Ms. Pac-Man scores and a maximum fixed-start score with simplified executive memory.
- Fruit Collection task: HRA decomposes the fruit-collection reward into 10 location-specific functions and represents each with a separate action-value head.The shared network encodes the agent’s position and fruit features, while the heads represent four action-values for each reward component.
- Fruit Collection task: Domain knowledge is added incrementally by removing irrelevant features, identifying terminal states, and using pseudo-reward GVFs for each fruit location.These variants are named HRA+1, HRA+2, and HRA+3; DQN+1 uses the corresponding reduced-feature network.
- Fruit Collection task: HRA shows a clear performance boost over DQN with the same network, while adding domain knowledge produces further large improvements.Using the domain-knowledge-enhanced network improves HRA but decreases DQN performance.
- ATARI game: Ms. Pac-Man: In Ms. Pac-Man, HRA decomposes shaped rewards by object, assigning separate agents and Q-value functions to pellets, fruits, ghosts, and blue ghosts.The architecture uses object-specific GVFs and reward weights, with absent objects contributing zero Q-values.
- ATARI game: Ms. Pac-Man: HRA’s best configuration outperforms state-of-the-art and human scores under both fixed-start and random-start evaluation after about 150 million frames.The reported configuration uses normalization and both exploration types, whereas no exploration performs very poorly.
- ATARI game: Ms. Pac-Man: With simplified executive memory, HRA reaches the maximum possible score of 999,990 points in fewer than 3,000 episodes by exploiting fixed-start evaluation.The score ceiling results from overflow at one million points, and the simplified executive memory does not generalise.
5 Discussion
HRA exploits reward decomposition to make difficult value functions easier to learn. The approach substantially reduces effective problem size and supports domain-knowledge-driven performance gains.
- Discussion: Figure 6 examines training with trajectory memorisation as part of the HRA discussion.The supplied passage identifies the figure’s training condition but does not state its outcome.
- Discussion: HRA can exploit domain knowledge more effectively than single-head methods, improving on the fruit collection task when irrelevant features are removed.The same architectural change decreased DQN performance.
- Discussion: HRA learns close to 1,800 general value functions for Ms. Pac-Man, replacing a state-space of about 10^77 with GVF state-spaces of about 10^3 states.These smaller problems can be represented without function approximation.
- Discussion: Reward decomposition can exponentially reduce problem size, so even two or three reward components may substantially help on real-world tasks.This is presented as a broader applicability claim for tasks permitting reward decomposition.
A.1 General information about Atari 2600 Ms. Pac-Man
Ms. Pac-Man is a complex Atari benchmark with multiple maps, object types, and evaluation protocols. Reported scores vary greatly between fixed-start and random-start evaluation, making metric distinctions essential.
- General information: Ms. Pac-Man contains four maps and seven fruit types, while gameplay rewards pellets, ghosts, power pellets, and bonus fruits.Bonus fruits appear twice per level, and completing a pellet layout starts a new level.
- General information: Two Atari evaluation methods produce very different scores because they introduce randomness through different starting-point procedures.The random-start metric samples starting points along a human trajectory.
- General information: 6.673 points is the best reported fixed-start score, while 2.251 points is the best reported random-start score among the cited methods.The cited human baseline is 15.693 points, while the highest reported human score is 266.330.
- General information: Figure 7 presents the four different Ms. Pac-Man maps used in the domain.Tables 2 and 3 provide map, fruit-type, and edible-object point breakdown information.
- General information: Table 4 reports Ms. Pac-Man scores separately for fixed-start and random-start evaluation.The table labels fixed-start evaluation as random no-ops and random-start evaluation as human starts.
A.2 HRA architecture
The Ms. Pac-Man HRA architecture combines specialised value and exploration heads to learn object-related behavior while avoiding deterministic or overly cautious trajectories.
- GVF heads: GVF heads create online value functions for visited Ms. Pac-Man positions, each estimating a pseudo-reward associated with its position.The Ms. Pac-Man state uses map position and heading, with roughly 400 positions and 950 states.
- Aggregator: The aggregator activates object-specific GVFs with type-dependent multipliers and sums their action values.Multipliers include 10 for pellets, 50 for power pellets, 200 for fruits, and 1,000 for edible ghosts.
- Architecture comparison: Figure 8 tracks training as HRA heads are added incrementally.The supplied figure passage identifies the comparison but does not report numerical outcomes.
- Diversification head: A diversification head samples random action values uniformly from [0,20] during the first 50 steps to make trajectories unique.The method avoids relying on ϵ-greedy exploration because unsafe actions may endanger Ms. Pac-Man.
- Score heads normalisation: Without score-head normalisation, the architecture initially reaches 10,000 points but later regresses because ghost-avoidance values overwhelm the aggregator near level completion.The resulting behavior becomes increasingly scared of ghosts as learning progresses.
- Targeted exploration head: The targeted exploration head prioritises less-explored state-action pairs and, together with diversification, forms the HRA architecture used in every experiment.Diversification makes trajectories unique, whereas targeted exploration prioritises exploration and speeds learning.
- Executive memory head: The executive memory head records action sequences that complete a level without a kill and assigns high value to recorded actions on the same level.It models memorisation of favorable situations described in human play.
A.3 A3C baselines
The A3C baselines compare pixel and low-level feature inputs under controlled training settings, with separate grid searches for γ under different memory conditions.
- Baseline setup: A3C is evaluated on both pixel-based and low-level-feature environments to reproduce prior results under HRA’s input representation.The implementation follows Mnih et al. (2015).
- Baseline setup: A3C training uses 8.108 frames, γ = 0.99, entropy regularisation 0.01, five-step returns, 16 threads, and gradient clipping 40.α is selected for maximum performance from five tested values between 0.0001 and 0.001.
- Low-level features: The low-feature input uses five 40 × 40 channels for Ms. Pac-Man, pellets, ghosts, blue ghosts, and fruit, plus direction information.Two convolutional layers use 16 and 32 filters with the stated kernel and subsampling settings.
- Hyperparameter evaluation: Figure 9 compares smoothed training curves for γ values without executive memory.The figure is smoothed over 500 episodes.
- Hyperparameter evaluation: Figure 10 reports a γ grid search with executive memory.The supplied passage does not state the comparison outcome.
- Network architecture: The baseline network has a 256-unit hidden layer, a nine-unit softmax policy head, and a one-unit linear value head.Weights are uniformly initialised using the cited He et al. method.
A.4 Results
Across γ grid searches, all tested values produced very good results, with higher ghost-discount values tending to perform better and score discount having less impact. These findings persisted with executive memory, although level-passing efficiency appeared somewhat more random.
- All tested γ values yielded very good results, and these results generalised over random human starts.The tested values were 0.95, 0.97, and 0.99 for both γscore and γghosts.
- Higher γ values for the ghosts tended to perform better, while the γ value for the score was less impactful.
- The same conclusions held when executive memory was used.
- Executive memory was associated with somewhat more randomness in level-passing efficiency.