Reinforcement Learning: Pokemon Red

The environment is configured as a Python AI Gym custom environment where the user can define state, action, and reward spaces as well as observation functions and transition functions. The game is emulated using the PyBoy python library.The state space is taken from game RAM at every step. The number and type of variables included in the state space is largely a tuning parameter as passing a smaller subset of the RAM will likely allow faster learning since there are less parameters to consider. If too few variables are passed the agent will be incapable of learning certain tasks.

Ultimately, most of the state space was used with the omission of game flags that were relegated to much later in the game. The scope of the project only extended to making some progress through the game.

The agent has several actions it can choose which are mapped to the different buttons on the gameboy. Some buttons have little use in game (such as select), so those actions were omitted from the action space.

The training is set up to run 96 agents each in their own environment, allowing for the parallelization of training using GPU hardware acceleration. In addition to speeding up training, each agent is able to share its experiences with other agents, meaning that when one agent finds an event flag, typically other agents will follow suit.

One aspect of this project which required significant tuning was the reward function. Often times with reinforcement learning, the reward function must be shaped to extract desirable behaviors from the agents, but not manipulated in such a way to encourage potentially inefficient behaviors or exploitation. For example, initially, a reward was given for having healthy Pokemon that have not fainted. Once a Pokemon fainted, a negative reward was applied. This became a traumatizing event for the agents, and in general, they tended to avoid battling altogether despite battling being core to the games mechanics. Alternatively, if an agent new a Pokemon was about to faint, it would select actions which would prolong the battle indefinitely to avoid the negative reward.

Balancing exploration and exploitation is a well known problem in reinforcement learning. Easy traditional solutions to this are decaying epsilon greedy policies for taking actions in the environment which excel at exploring the environment early in training and then eventually exploiting the environment with the learned policy. In an effectively infinite horizon problem like Pokemon Red, this proves ineffective as the agent should be exploring both early in the game and later in the game. Another solution to the exploration problem is using Random Network Distillation to generate intrinsic motivation to add to the reward function which promotes visiting previously unexplored states both early and later in the game. Historically, this approach has proved to be successful when implemented in Montezuma's Revenge, a reasonable comparison to Pokemon Red

Random network distillation introduces an intrinsic reward agents get from exploring infrequently visited states. Extrinsic rewards are the rewards garnered from the environment. The total reward is the sum of the intrinsic and extrinsic rewards. The plot on the left illustrates what typical learning curves look like for the PPO implementation.

The first algorithm implemented was a Deep Q-Network (DQN). DQN is a popular algorithm for reinforcement learning which uses a neural network to approximate the Q-value function. This Q-value function can then be used to determine actions which lead to states of high value. This is a pretty popular algorithm given the simplicity, but when using a large state space like Pokemon Red, it becomes difficult for the network to capture the nuances of sequential actions required to progress.

The DQN algorithm was able to successfully navigate out of the starting house and reach the first flag, but it was only able to do so on a reduced state space size which simply included the agent's position, location area, the number of game flags triggered. While this seems successful, the algorithm lacks the necessary information in the state to progress much further than this. The image on the right shows the learned policy to leave the starting room and progress the game.

After many trials and tribulations, a more state of the art algorithm was implemented. Proximal Policy Optimization (PPO) is a well established actor-critic reinforcment learning algorithm in which two neural networks are leveraged: one to approximate the policy function (actor) and one to approximate the value function of that policy function (critic). PPO differs from standard actor critic algorithms in that it uses a clipped surrogate objective function to ensure that the policy is updated in a way that is more stable and less likely to diverge from the previous policy. This leads to incremental improvements in the policy instead of the more drastic changes seen in DQN. In addition, to off the shelf PPO, random network distillation was added to increase the exploration of agents due to the immense environment to explore.

The PPO algorithm was able to successfully navigate through the early stages of the game, reaching the second town and delivering Oak's parcel. It was able to do so due to its capability to learn a somewhat complex series of actions to trigger specific event flags. Additionally, as shown in the image on the left, the agent with the highest reward evolved his Squirtle into a Wartortle named RP.