Can Black Ops Zombies teach us about something about hard search problems?

Introduction

One of the things I find interesting about the SOTA in machine learning for sequential decision-making problems is that there are still a lot of areas where humans do dramatically better than the bots, in a way that seems less prominent in other areas of machine learning (like vision, or expert-systems like NLP applications).

Some (most?) of these problems seem to me like ones where there is a limited amount of experience the agent gets to learn from. For instance, a stock trader on Wall Street does not need 700 years of experience to become competent, but more like 7 months. Good self-driving algorithms require the human equivalent of centuries of experience, while starting teenage drivers achieve competency in a few months. Our knowledge of the theory of reinforcement learning makes this unsurprising - in the tabular setting you need a tremendous amount of experience to get to strong performance guarantees, and this is somewhat aligned with our knowledge that when RL does outperform humans, it is when it has access to much more experience than humans can realistically obtain (such as in chess, Dota, etc.).

Other ones are different, and seem to me more like hard search problems. You can probably propose many different frameworks to describe these precisely, but I generally mean any case where the Markov Decision Process state space is very large and the number of states that give reward are very small (and so are hard to find). Accordingly, these MDPs do not have nice “reward shaping” -> there are no small rewards that lead you like “breadcrumbs” to larger, more meaningful reward. This reward shaping is very common in video games (such as Pac-Man, where eating pellets shapes the policy towards board clears) or robotics (where the reward function is usually carefully designed to be near-greedy optimal).

The infamous canonical example is Montezuma’s Revenge, an Atari 2600 game that for some reason is very difficult to make progress in by randomly taking actions (such as in epsilon-greedy exploration the original DQN variants used).

My understanding is that part of the problem with Montezuma is that you needed to grab keys before progressing to new areas, so it meant you had to randomly stumble into the key, find your way to the door, and learn that general relationship (need key before go through door) which is tricky. Similarly, for policy gradient algorithms, unless you do some smart policy initialization from behavior cloning or something most of your early policy evaluations will just give no reward, which is not a useful signal to learn from. So you need to get a very lucky run, and then need to get a lot more, and hopefully at some point learning will happen.

This particular game turned out not to be insurmountable, it just required much more sophisticated search/planning heuristics to be baked explicitly into the algorithm. The general idea behind GoExplore is to find useful states, and then return to them before explicit exploration stages. This intuitively should work well for many of the kinds of games we tend to characterize as good hard exploration test-benches: essentially nested “lock and key” puzzle boxes where you need to complete some task before being allowed to progress.

But there are games/problems where this is much, much much harder. Some of these problems are important and still unsolved, like gene folding. Today I’ll talk about a problem more dear to my heart.

Black Ops: Zombies is a game mode in the broader video game series Call of Duty: Black Ops, which is itself a sub-series of the broader Call of Duty game series. Basically, you can treat it as its own game. In each BOZ games there are a set of maps, which take place in different locales, such as a castle in the Swiss Alps (see the post title image) or in the jungles of the Himalayas.

The game takes place in a first-person simulated environment where you take the role of a human stuck in a zombie apocalypse. You can move, look in any direction, and use firearms. The game features a “round” based system. So you start on round 1, a bunch of zombies spawn progressively, you kill them, and then another round will start with more zombies, which will have more health and spawn in greater numbers.

Nominally, the goal of the game is to just survive as long as possible. I suspect training an RL agent to do this would not be that bad: the best human zombies high-round behavior is a pretty simply loop involving training zombies in a line, using powerful area of effect weapons to kill them, and then repeating. This strategy does not require much memory, long-horizon problem solving, etc. But under the surface, almost every map has a hidden objective called an “Easter Egg” (often in the BOZ community, just EE) which involves completing a very obscure set of hidden steps, each in a careful sequence and many requiring several players cooperate together, to reach a fixed final secret ending .

These Easter Eggs are both mechanically challenging on their own, demanding a very competent baseline level of play ability, and are a perfect example of hard search problems. It is very infrequently clear what the correct next step of an EE is, and the BOZ community often spends somewhere between a couple of days and a week working together to discover the correct sequence of steps when each new map launches.

I was originally going to write out the full steps to completing one of these, but they are much better described visually. Here is a good video guide to the Der Eisendrache EE. Even if you are an avid video game player, you should be able to recognize that most of these steps are not remotely intuitive. They require seeing incidental background details (such as the paintings in the wolf bow step, the wisps in the two time-travel steps, and the stone slab you originally collect in the past visiting Dr. Groph’s lab and then need to place in the wall during the end of the Keepers step) as objects you must manipulate somehow to reach the next step.

Why is BLOPS Zombies potentially hard for Deep RL?

I think that this presents a “nightmare” scenario for Deep RL, where all of its worst weaknesses are areas where the learning agent must be competent to solve the problem. These are…

1] Long Horizon Rewards: most BOZ EEs take in the region of 3 hours to complete. RL agents do not operate continuously in time but on discretized control intervals that are chosen by the RL engineer. I’ll make a generous assumption of an action 5 times a second, roughly in line with the OpenAI Five agent. Doing the math, and you get a total horizon of around 54,000 timesteps. This isn’t orders of magnitude above the horizon lengths that RL agents handle, but normally training gets much more difficult above a temporal horizon of like 6 minutes. A BOZ RL agent probably wouldn’t need to keep the entire game in its horizon (augmenting the state space with information about if certain tasks were completed would help greatly, for instance), but it would probably need at least a couple of minutes to complete more complex EE steps.

2] Combining low-level control and perception with high-level planning: unlike hard exploration tasks in toy settings, most in the real world require you to also solve some kind of control and perception task. For instance, moving from Dr. Groph’s lab in the undercroft area of Der Eisendrache to the area where Dempsy’s pod lands outside of the cathedral requires you to solve first-person camera perception, an idea of the layout of the map, and the appropriate navigation to get there. Further adding difficulty is the fact that there are zombies everywhere on the map you need to avoid, kill, or otherwise deal with, which if not will kill you and hamper the high-level steps of the EE. The good news is that the movement interface is relatively high-level: you are given controls to move, look around, etc. instead of needing to learning leg motor actuation values or PID controller values or something ridiculous like that.

Is this possible? I’m not totally sure, but from my knowledge most examples of RL solving very impressive long planning problems (Dota, Chess, soccer robots, etc.) are ones where perception is treated as a solved problem (Dota takes observations from the engine, Chess doesn’t have a perception problem whatsoever, soccer bot was trained with a feature extractor or sim ground-truth information) and RL solving impressive dual control-perception problems (walking robots?) are ones where the goal is relatively simple/super long term planning isn’t required.

But enough speculation: how does RL perform in first-person games with relatively long reward horizons? To my knowledge the greatest success is the DeepMind Quake III agent, which learned strong capture the flag multiplayer FPS gameplay from pixels (note: one of the things they required was massive parallelization, which will come up later!). I think the most obvious failure is Minecraft, which to get nice RL performance for you need to use a lot of tricks like using BC as a prior, curriculum task learning, only using RL to get into locations where state-machine based policies take over for specific actions, and probably other stuff.

A mixed-success example are DeepMind’s soccer robots, which they taught successfully to combine low level motor control and strategy. Their initial work learned from high-level features (self and opponent positions/deltas, ball position, etc.), and it appears they did not initially find success learning E2E from video, but they ended up making it work later with an asynchronous actor critic architecture, where the critic can learn from privileged information but the policy does not, which lets you “cheat” during training but retain only the vision requirement during execution. This is a pretty cool idea - it’s one that a recent paper from the new RLC conference demonstrated in Gran Turismo, taking the previous GT-Sophie and training a policy from just pixels and human-observable information like speed and acceleration (arguably human observable, maybe), also uses. As far as I can tell, this idea came from this paper.

So bottom line - learning low level control, high level strategy/planning, and perception all at the same time is hard. It is easier to break these down somehow: curriculum learning to solve the low-level control, heuristics to jump start the policy initialization’s learning of planning, use a VAE backbone or feature extractor for perception, etc. With the right tricks you could maybe use some of these for BOZ: but I suspect given the same circumstance as new humans playing a new map where you do not know what features are meaningful, this would be very difficult.

3] Ambiguous Reward (yes, we are still numbering!): Deep RL, when applied to long-horizon tasks, usually benefits a lot from good reward shaping. For instance, while it is literally true that the only objective in Dota II is to win the game, the OpenAI Five team did not just give a terminal reward for winning and call it a day. Their final reward function required a lot of careful engineering in the end to make the system work. In a sense you can think of the “true” MDP for BOZ Zombies as getting reward 1 when you complete the EE, and 0 otherwise.

That doesn’t quite seem fair to me. Most EEs give you some indication of progress through unique voicelines, collecting unique items, and other “soft” measures. There is no score counter or the like that gives a nice scalar reward, but generally you do know when you are making progress. One could argue a RL agent should learn to recognize these as a sign of progress through some intrinsic reward process (like the problem inverse RL studies) but given how deeply these signs of progress are tied to human-strong priors this still feels a little unfair. If there was a robotics benchmark that required some ridiculous human-specific thing to pass (showing you have a heartbeat, or can experience the beauty of a flower) no one would blame the underlying learning process of the robot for failing to complete that. So I think giving rewards for completing steps is basically fair game.

But that still gives a very sparse reward signal, and the many tricks used in say, the OpenAI Five agent are less readily accessible. Unlike in Dota, you can’t use killing enemies or making money as a good proxy of progress. In fact, during BOZ EEs you will often avoid killing enemies or progressing the round in order to make the current EE step easier to complete. You do make points from killing the zombies that are useful for buying weapons, opening doors on the map, etc. but these quickly lose their usefulness as a proxy for progress. The uncomfortable truth becomes that to further shape reward, you would need prior knowledge of how to complete each EE step, which I would consider cheating personally.

How do humans solve BOZ?

Given all of this, it might seem confounding that humans are even able to solve these with any level of reliability. You need to recognize details as incidental as the direction that rocks in the background point, organically learn a complex multi-step recipe, and also just be pretty good at the base video game skills of killing and avoiding zombies.

The answer boils down to parallelization, and efficient communication, and an understanding of the general structure of each EE. It would probably take a single agent working non-stop months to solve one of these. But the fact that there is a community working together to solve these puzzles means information about progression can be communicated. This means that even though the odds of any agent finding the next step is highly stochastic, the fact that a couple thousand people are exploring potential new avenues simultaneously helps this process.

The kind of problem these EEs are helps a lot: because you can pretty clearly tell when a step is completed, and the steps progress more or less linearly (you can’t really complete steps “out of order”) the whole problem can be reduced to one linear chain of rooms, where progression is gated by a smaller sub-puzzle you solve within that room. There are some things that carry between rooms (some EE steps can be parallelized, you sometimes need to set up some steps or be searching for certain weapons well in advance) but these are well-understood and not in any way “nettlesome”. By that I mean that if a BOZ EE had some weird mechanic where the number of shots you fire in each step had to follow the digits of Pi when modulo operated, otherwise you would instantly die right before the end of the EE, that would complicate the linear progression because you wouldn’t know if you had completed each step “right” and you would need to think about each step as part of a larger puzzle instead of independent tasks.

This post has been sitting in my drafts folder for a long, long time (I believe since well before I came to Canada?) and so I am just going to stop the rambling here. The basic point I want to emphasize is that RL still struggles at long horizon tasks without strong priors connecting complex perception to control. Lots of room for improvements!