Source-linked AI summary
Learn What Not to Learn: Action Elimination with Deep Reinforcement Learning
Tom Zahavy, Matan Haroush, Nadav Merlis, Daniel J. Mankowitz, Shie Mannor
TL;DR
Large action spaces burden RL when many available actions are irrelevant. The paper proposes AE-DQN, combining DQN with an Action Elimination Network trained from environment elimination signals, and reports faster learning in Zork while providing convergence guarantees.
Problem
RL agents may waste computation exploring redundant or irrelevant actions in large discrete action spaces.
Method
AE-DQN combines Q-learning with an Action Elimination Network that predicts invalid actions from an external elimination signal.
Results
The method advances faster than baseline agents in Zork, where states have more than a thousand possible text actions.
Takeaways & Limitations
Action elimination reduces the action space, makes exploration more effective, and improves learning in the evaluated large-action-space tasks.
Takeaways & Limitations
Embedding elimination signals into the MDP is nontrivial, while reward shaping can be difficult to tune and joint models can be strongly coupled.
Abstract
from arXiv · showhide
Learning how to act when there are many available actions in each state is a challenging task for Reinforcement Learning (RL) agents, especially when many of the actions are redundant or irrelevant. In such cases, it is sometimes easier to learn which actions not to take. In this work, we propose the Action-Elimination Deep Q-Network (AE-DQN) architecture that combines a Deep RL algorithm with an Action Elimination Network (AEN) that eliminates sub-optimal actions. The AEN is trained to predict invalid actions, supervised by an external elimination signal provided by the environment. Simulations demonstrate a considerable speedup and added robustness over vanilla DQN in text-based games with over a thousand discrete actions.
1 Introduction
Large action spaces make RL costly when many actions are redundant or irrelevant. AE-DQN addresses this by learning to eliminate actions using environment-provided feedback before DQN action selection.
- Motivation: Large action spaces can make real-world RL computationally difficult, particularly when many actions are redundant or irrelevant.Such systems may contain millions of possible actions at each time step.
- Action elimination: Action elimination restricts each state’s available actions to a subset of the most likely relevant actions.The approach uses an elimination signal as immediate feedback about actions that are not optimal.
- Approach: AE-DQN concurrently learns a Q-function and an action-elimination model using two CNN-based deep networks suited to natural-language states and actions.The architecture combines a DQN with an Action Elimination Network and a contextual bandit based on AEN activations.
- Evaluation: In Zork, natural-language commands create more than a thousand possible actions in each state.The agent is evaluated on whether eliminating irrelevant actions lets it advance faster than baseline agents.
2 Related Work
Related work establishes text-based games as challenging RL–NLP testbeds and surveys representation, large-action-space, and action-elimination methods. These prior approaches motivate combining deep RL with explicit elimination in compositional text action spaces.
- Text-based games: Text-based games combine language understanding with long-term memory, planning, exploration, affordance extraction, common sense, and stochastic dynamics.Their action spaces are combinatorial and compositional, while states can be partially observable.
- Representations: Prior text-game agents used pre-trained embeddings, bag-of-words features, recurrent representations, or neural networks to represent states and actions.These approaches differ in whether representations are transferred, learned separately, or trained end-to-end.
- Large action spaces: Large-action-space RL research has explored factorizing discrete actions or embedding them into continuous spaces before selecting nearby discrete actions.These methods address action selection without the explicit elimination framework proposed here.
- Action elimination: Earlier action-elimination work used confidence intervals in bandits and tabular MDPs, while related work classified hazardous states or extracted affordances.The present work extends the elimination perspective to deep RL in text-based games.
3 Action Elimination
The framework augments Q-learning with an elimination signal and a contextual-bandit predictor that removes actions while protecting valid ones. Under stated assumptions, the resulting algorithm has high-probability correctness and convergence guarantees.
- Definitions: The elimination signal marks an action as removable when no optimal policy in the state would choose it.Valid state-action pairs include those belonging to some optimal policy; admissible pairs are those the algorithm does not eliminate.
- Advantages: Action elimination can reduce overestimation and sampling demands because Q-estimates need only be accurate for valid actions.The target’s max operator is restricted to admissible actions, avoiding unnecessary invalid-action exploration.
- Sample complexity: At least ϵ^-2(1 −γ)^-3 log 1/δ samples are required per state-action pair under the cited lower bound.Eliminating A′ near-optimal but unnecessary actions can therefore reduce the number of sampled pairs needed during learning.
- Design challenge: Embedding elimination directly into the MDP is difficult because reward shaping is hard to tune and joint policy-gradient models are strongly coupled.The contextual-bandit formulation is introduced to avoid these convergence and sample-efficiency problems.
- Contextual bandits: A contextual bandit predicts elimination from state representations, decoupling the elimination signal from the MDP’s reward-learning process.The analysis assumes a linear expected elimination signal in the context, with bounded noise and a separation between valid and invalid actions.
- Guarantees: With probability 1 −δ, the method never eliminates a valid action under the concentration-bound procedure.The threshold uses an assumed upper bound ℓ for valid actions; the signal itself may remain binary even when its expectation is not.
- Concurrent learning: Action Elimination Q-learning updates and bootstraps only over admissible state-action pairs, while concurrent learning affects both the Q-function and elimination model.Under the stated visitation and concentration conditions, it converges to the optimal Q-function for valid pairs; invalid actions receive finite or logarithmic sampling depending on noise.
4 Method
AE-DQN combines a DQN with an Action Elimination Network and a contextual bandit to remove unlikely actions before action selection and value estimation. The method uses environment-provided elimination signals to train the AEN and periodically updates its elimination model.
- AEN and contextual bandit: The AEN learns realizable state-action features and periodically uses them to construct a contextual linear bandit model.The bandit is rebuilt every L iterations from the AEN’s last hidden-layer activations because those activations change during optimization.
- AE-DQN architecture: AE-DQN trains a DQN and an Action Elimination Network concurrently to approximate Q-values and eliminate actions.The architecture incorporates action elimination into DQN and initializes separate online and target networks.
- Action elimination: The contextual bandit eliminates actions with high probability through ACT() and Targets(), producing an admissible action set.ACT() and Targets() use the elimination model to restrict actions considered during interaction and target-value computation.
- Target computation: Targets() computes target values using the maximum Q-value over admissible actions, reducing function approximation errors.The method also stores elimination signals alongside transitions in experience replay for AEN training.
- Action selection: Among admissible actions, ACT() explores uniformly with probability ϵ and otherwise selects the action with the highest Q-value.The exploitation arg max and exploration Uniform(A′) both operate only over the retained action set.
- Network training: The AEN is trained with mean squared error using the elimination signal as its label.Both networks use NLP CNN architectures, while the DQN uses 500 convolutional filters and the AEN uses 100.
5 Experimental Results
Experiments in grid worlds and Zork show that eliminating irrelevant actions improves learning, robustness, and performance, especially as action spaces become larger. AE-DQN learns faster than DQN in text-based quests and approaches an optimal-elimination baseline in the Troll Quest.
- Grid World Domain: Action elimination dramatically improves tabular Q-learning as the number of state categories and grid size increase.The reported gain is attributed to eliminating actions that would otherwise delay reaching the goal.
- Experimental Setting: Zork provides a large text-based action space because players issue natural-language commands in a world containing complex puzzles and action sequences.The game offers more than a thousand possible actions in each state, motivating action elimination.
- The Egg Quest: AE-DQN is more robust to hyperparameter settings when many actions are available, learning considerably faster than DQN for A2 with T=100.For A1 with T=100 and A2 with T=200, both agents solve the task well; the clearest difference appears for A2 with T=100.
- The Troll Quest: AE-DQN significantly outperforms DQN in the Troll Quest and achieves performance comparable to the optimal-elimination baseline.The agents use 215 actions, while the optimal-elimination baseline uses 35 actions; the improvement over DQN is larger than in the Egg Quest.
- Open Zork: Open Zork evaluates AE-DQN with both the 131-action Minimal Zork set and the 1227-action Open Zork set, reporting state-of-the-art results over previous work.Training used 1M steps, with trajectories capped at T=200 and 5000 trajectories executed.
6 Summary
The paper proposes AE-DQN, which combines Q-learning with action elimination for large state and action spaces. Experiments in Zork show reduced action spaces, more effective exploration, and improved learning, while the approach also has theoretical convergence guarantees.
- Summary: AE-DQN eliminates actions while performing Q-learning to solve Markov decision processes with large state and action spaces.The approach is presented as a deep reinforcement learning method.
- Summary: In Zork, action elimination reduces the action space, makes exploration more effective, and improves learning.These findings are reported for the paper’s text-based game evaluation.
- Summary: The paper provides theoretical guarantees on the convergence of its approach using linear contextual bandits.The convergence guarantee is stated as part of the paper’s contribution.
- Summary: AE-DQN learning appeared to converge when trained for 2M steps, in addition to the 1M-step evaluation used for comparison with previous work.The 2M-step result is reported for completeness.
Appendix A Proof of Proposition 1
The proof establishes that action-elimination Q-learning converges on valid state-action pairs while limiting visits to invalid actions under probabilistic guarantees. Its visit bound depends on confidence growth and is not tight because it ignores correlations between contexts.
- Convergence: The proof assumes all state-action pairs are visited infinitely often unless eliminated, enabling standard Q-learning convergence on the surviving pairs.This assumption is used to distinguish ordinary convergence from convergence after invalid actions become permanently excluded.
- Convergence: With probability at least 1−δ, action elimination never removes valid actions and Q-learning converges to the optimal Q-function on valid state-action pairs.The proof constructs a reduced MDP after strictly suboptimal actions are eliminated and shows it preserves the value and Q-values of valid actions.
- Invalid-action visits: Invalid actions are visited at most 4β_t/(u−ℓ)^2 + 1 times before being eliminated with high probability.The elimination threshold follows from the confidence-bound condition on the number of visits T_s,a(t).
- Bound limitations: The confidence-bound visit bound is not tight because it ignores correlations between different contexts.A tighter contextual bound is difficult when a state’s context is uncorrelated with those of other states.
- Invalid-action visits: For bounded state representations, invalid-action visits have a logarithmic-order bound through the increasing confidence parameter β_t.The supplied derivation states that invalid actions are sampled no more than a bound involving β_t and the action gap (u−ℓ).
Appendix B Grid world simulations
Grid-world experiments show that action elimination substantially improves tabular Q-learning, especially as the action space, grid size, or difficulty of distinguishing optimal actions increases. Performance remains superior unless the elimination signal is almost completely random, although the advantage narrows when valid actions are nearly deterministic and invalid actions highly random.
- Experimental protocol: Experiments average results over 5 random seeds and display error bars equal to std/3 after moving-average filtering.The moving-average window has length 200.
- Baseline comparison: Action elimination significantly improves Q-learning over vanilla Q-learning, with larger gains when more state categories create more invalid actions.The comparison uses vanilla Q-learning, action-elimination Q-learning, and an optimal-elimination upper-bound baseline.
- Grid-size effects: Action elimination becomes more effective as grid size increases because random exploration reaches the goal less readily on larger grids.The reported comparisons cover 40x40, 30x30, and 20x20 grid worlds.
- Signal robustness: Only when the elimination signal is almost completely random does action elimination fail to show superior performance.The signal-randomness study varies elimination probabilities for invalid and valid actions.
- Signal robustness: When valid actions are nearly deterministic and invalid actions nearly random, action elimination still converges faster, but the convergence-rate gap is smaller.The reported setting uses pT_c = 0.9 for valid actions and pF_c = 0.1 for invalid actions.
- Overall findings: The tabular simulations show significant improvement when the action space is large, optimal and suboptimal actions are hard to distinguish, and the goal requires a long horizon.These are the experiment’s summarized conditions for the strongest benefit from elimination.
Appendix C Additional figures
The additional figure reports results in the Open Zork setting.
- Figure 8 reports results in the Open Zork environment.The supplied caption identifies the figure’s setting but does not state the plotted outcome.
Appendix D Maps of Zork
The appendix provides maps of Zork and identifies the Troll and Egg quests as subdomains.
- Figure 9 depicts the world of Zork.
- Figure 10 identifies the Troll and Egg quests as Zork subdomains.The Troll quest is shown in green and the Egg quest in blue.