PaperlayerView exact revision on arXiv

Source-linked AI summary

On Hard Exploration for Reinforcement Learning: a Case Study in Pommerman

Chao Gao, Bilal Kartal, Pablo Hernandez-Leal, Matthew E. Taylor

arXiv:1907.11788v1cs.LGcs.AIstat.ML

TL;DR

The paper examines why model-blind random exploration in Pommerman can lead to suicide and delay learning bomb-use behavior. The paper analyzes random-walk path counts and suicide cases, then proposes a model-based module that prunes unsafe actions. With the reasoning module, neural nets learned the tasks in FFA and Team settings, while agents without it did not improve after days of training.

Abstract

from arXiv · show

How to best explore in domains with sparse, delayed, and deceptive rewards is an important open problem for reinforcement learning (RL). This paper considers one such domain, the recently-proposed multi-agent benchmark of Pommerman. This domain is very challenging for RL --- past work has shown that model-free RL algorithms fail to achieve significant learning without artificially reducing the environment's complexity. In this paper, we illuminate reasons behind this failure by providing a thorough analysis on the hardness of random exploration in Pommerman. While model-free random exploration is typically futile, we develop a model-based automatic reasoning module that can be used for safer exploration by pruning actions that will surely lead the agent to death. We empirically demonstrate that this module can significantly improve learning.

Analysis of Random Exploration

The analysis builds path-count models for random movement, then applies them to Pommerman to examine how obstacles and bomb placement constrain survival. It finds that suicidal outcomes are common and that the unique safe route in some settings can make positive experience exponentially hard to obtain.

Obstacle-free 2D grid world

  • With five equally likely actions, the probability of occupying cell p at time t is its path count N(p,t) divided by 5^t.The recurrence counts paths from the prior step’s neighboring cells and the cell itself; path counts can be computed bottom-up by dynamic programming.Source: Obstacle-free 2D grid world · p. 2, Figure 2 · p. 2

Generalization to arbitrary obstacles

  • For a bounded board with static obstacles, the path-count recurrence uses each action’s predecessor position, with invalid moves leaving the agent in place.The analysis considers this setting similar to Pommerman with ammo=0, so bomb placement is unavailable.Source: Generalization to arbitrary obstacles · pp. 2–3, Figure 3 · p. 3

Suicide study: Pommerman

  • The suicide analysis treats bomb placement as a special origin: once the agent moves off the bomb, it cannot return, so the origin’s path counts require separate initialization.The model assumes five available actions until the bomb explodes and otherwise static board items.Source: Suicide study: Pommerman · p. 3
  • At the 9-step bomb-explosion horizon, suicide probabilities are approximately 0.38–0.46 across four starting corners.The random-board example also finds path counts concentrated around each agent’s origin.Source: Suicide study: Pommerman · p. 3, Figure 5 · p. 4, Figure 4 · p. 4
  • In a corridor worst case, only 1 of 5^9 paths is safe, so obtaining one positive behavior example can require exponentially many samples.Survival requires taking the correct action at every time step; the paper contrasts this with an ideal empty-board case whose suicide probability is 0.16.Source: Suicide study: Pommerman · p. 4, Figure 6 · p. 4, Figure 7 · p. 4

Action Pruning

The section presents action pruning as a way to support safe exploration when model-free assumptions are relaxed. It reasons about whether each action leaves enough time to reach a region outside bomb range, then returns the actions judged safe.

Action Pruning

  • The pruning module removes actions that will lead to death, enabling safe exploration when the model-free demand is relaxed.The paper focuses on learning among the remaining safe actions.Source: Action Pruning · pp. 4–5
  • For each action, the algorithm computes the resulting cell and evaluates its safety against the minimum life of bombs that cover it.The method generalizes the corridor example to arbitrary bombs.Source: Action Pruning · pp. 4–5
  • The algorithm takes visible board and agent information and returns safe actions; in partially observable settings, unseen areas can be treated as walls for an approximation.Exact computation is impossible with partial observability.Source: Action Pruning · p. 5
  • A cell is safe when bombs do not cover it, or when the agent can reach a bomb-free region before the bomb explodes.The algorithm compares the post-action cell’s safety value—the minimum steps to a safe region—with the minimum life of bombs covering that cell.Source: Action Pruning · pp. 4–5
  • With a fully observable board and stationary bombs and opponents, optimal moves are not pruned; dynamic environments can be handled by expanding opponent moves in a look-ahead tree search.The stated complexity is O(l^2), with l = 11 in Pommerman.Source: Action Pruning · p. 5

Experiments

The experiments compare PPO with and without action pruning in FFA and Team modes, then evaluate trained agents against SimpleAgent. Pruning enables learning against static opponents, and the resulting agents outperform the baseline in both modes.

Experiments

  • The experiments compare learning with and without action pruning in both FFA and Team modes.Source: Experiments · p. 5

Learning Algorithm

  • PPO trains on games played by the old neural-network policy, using returns and generalized advantage estimates.Returns are −1, 0, or 1 for a loss, draw, or win; the reported settings include γ = 0.9, λ = 0.95, and 32-step returns.Source: Learning Algorithm · p. 5

Architecture

  • The network takes 14 observation feature planes of shape 11×11 and uses four convolution layers before separate policy and value heads.Each of the four layers has 64 3×3 kernels; the heads use two 1×1 kernels.Source: Architecture · pp. 5–6

Learn with Static Opponents

  • Without pruning, PPO's success rate remained zero after five days, while pruning enabled it to learn the static-opponent tasks.The unpruned run lasted 5,000 iterations; each iteration comprised 80 games across eight workers.Source: Figure 9 · p. 6, Learn with Static Opponents · p. 6

Reward Shaping

  • Reward shaping adds dense rewards for exploration, power-ups, opponent kills, and blasting wood, while penalizing teammate kills.The listed rewards include 0.001 for visiting a cell outside a FIFO queue of size 30 and 0.5 for killing an opponent.Source: Reward Shaping · p. 6

Learn with Static Opponents

  • Against static stop-action opponents, agents must still blast wood with bombs to reach and kill opponents on randomly generated boards.FFA wins require killing three static agents within 800 steps; Team wins require destroying both opponents within 800 steps.Source: Learn with Static Opponents · p. 6

Evaluate Against Baseline Opponents

  • Around 40% against three SimpleAgents in FFA and around 70% against a SimpleAgent team in Team mode; a similarly strong player would win about 25% in FFA.The final-iteration models were tested in three independent trials of 100 games each.Source: Table 1 · p. 6, Evaluate Against Baseline Opponents · p. 6

Conclusions

The paper analyzes the hardness of directionless exploration in Pommerman and presents a model-based reasoning module that prunes unsafe actions. Its experiments show the module's merit in FFA and Team settings, while motivating action pruning and tree search as directions for high-level play.

  • The analysis addresses the hardness of directionless exploration in Pommerman and may also apply to other grid-world-like environments.Source: Conclusions · p. 6
  • With the reasoning module, neural networks learn the pure exploration task against static opponents; without it, performance did not improve after days of training.Source: Conclusions · p. 6
  • The paper identifies action pruning for survival and tree search for look-ahead opponent moves as promising components of high-level multi-agent play.Source: Conclusions · p. 6
Loading 1907.11788v1…