Figure B.1: A bee leaving a trail of mushrooms as it moves from the top of the
screen to the bottom in the game _Millipede_. The left image is earlier in
time than the right image.

and another ($-$10) for shooting while aligned, regardless of if the bolt
connects. An alignment cool-down period of approximately one second is used to
prevent the agent from trivially accruing costs by continuously breaking and
regaining alignment with the millipede.

The agent’s objective is impeded in several ways. Foremost, there are
mushrooms present in the environment, which act as barriers to the bolts and
make the millipede body segments harder to hit. When a millipede encounters a
mushroom in its path, it drops down a row and reverses direction. Mushrooms
can absorb multiple bolts before disappearing. A minuscule cost is accrued as
a mushroom is hit ($-$1) and when it is destroyed ($-$5). Shooting any section
of the millipede creates a new mushroom. Mushrooms also randomly grow and are
culled at various intervals. Randomly spawned enemies, known as bees and
dragonflies, have the ability to leave mushrooms as they travel from top to
bottom in the environment (see figure B.1). Mushrooms can turn into
impenetrable flowers when touched by an enemy known as beetles. Flowers return
to normal either when the agent dies or if a nearby DDT canister is hit.
Earwigs can poison the mushrooms so that a millipede segment

Figure B.2: An example of a _Millipede_ game state where multiple poison
mushrooms are visible in the environment. These are denoted using light green
mushroom sprites instead of the more common green-black mushrooms. Once a
millipede hits a poison mushroom, it immediately ignores boundary constraints
and heads toward the bottom of the screen. The left image is earlier in time
than the right image.

hurtles towards the agent when touching one (see figure B.2). This can create
conditions where the agent becomes trapped in a small part of the screen.
Destroying poisoned mushrooms is encouraged using a large-magnitude cost
($-$500).

The agent also faces several enemies, each with different behaviors. For
instance, spiders bounce irregularly across the player area and consume
mushrooms. Multiple spiders can appear on the screen simultaneously later in
the game. Mosquitoes and beetles move in various parts of the environment.
Destroying mosquitoes scrolls the position of everything in the environment up
one row. Destroying beetles scrolls the position of everything down one row.
Hitting inchworms slows all enemies for a brief time. The agent incurs
negative costs for destroying such enemies. Easily hit enemies like inchworms
($-$100), bees ($-$200), spiders ($-$300 to $-$1200) have low costs compared
to ones that are either harder to hit or spawn less frequently like beetles
($-$300), mosquitoes ($-$400), dragonflies ($-$500), and earwigs ($-$1000).
Bees have a moderate cost ($-$500), as they can clutter the environment with
mushrooms and make targeting

Figure B.3: Using DDT canisters to take out enemies in the game _Millipede_.
Here, the DDT cloud destroys an entire millipede. The left image is earlier in
time than the right image.

certain enemies difficult. The agent receives a small cost ($-$30) for being
aligned with any enemy and another ($-$20) for shooting while aligned,
regardless of if the bolt connects. We use the same alignment cool-down
strategy outlined above. Activating DDT canisters causes a cloud of poison gas
to spawn, which destroys nearby enemies (see figure B.3). Any enemies that die
within the cloud increase the accrued costs by one and one half times.
Triggering a DDT canister when an enemy is adjacent to it is encouraged using
a moderate cost ($-$300).

The agent loses a life ($+$1000) when it is hit by any enemy. A game ends when
all of the agent’s lives are gone. Good policies should hence choose context-
specific actions that minimize the total cost.

An in-game score is supplied and can be used to track agent performance.
However, based on initial experiments, we opted to fashion the above scoring
system. Such a system provides denser rewards, compared to the in-game score,
which promotes better self-supervision. For instance, the agent learns that it
can destroy mushrooms to clear out sections of the environment. Doing so
enables the agent to hit enemies. The in-game reward for destroying mushrooms
is too low for this to readily occur early during learning. Likewise, the
agent learns to track enemies more effectively early during the learning
process.

Centipede Gameplay. The gameplay for _Centipede_ is highly related to that of
_Millipede_. The agent controls the two-dimensional movement of a mobile
platform and fires bolts at enemies that appear on the screen. The most common
enemies are centipedes. They have a similar behavioral pattern to their
counterparts in _Millipede_ but leave mushrooms when they are shot. Since
other enemies are rare in _Centipede_ , destroying a centipede segment results
in a moderate cost ($-$25). Destroying the head yields a larger cost ($-$100).
Finishing all segments, and hence transitioning between levels, is encouraged
($-$250). We use the same alignment cost and cool-down strategy as in
_Millipede_ to help the agent learn to track the centipede segments.

Figure B.4: A large number of mushrooms can quickly emerge in the game
_Centipede_ , as centipede segments leave them when destroyed. In later levels
of the game, only centipede heads spawn. They hence distribute mushrooms near-
uniformly on the screen. The left image is much earlier in time than the right
image.

As in _Millipede_ , mushrooms are present in _Centipede_. However, they are
far more prevalent and more difficult to destroy in _Centipede_ , as they
require four shots. There are no DDT canisters to remove large fields of
mushrooms. The agent dying also restores partially destroyed mushrooms. It is
therefore common for many mushrooms to be present in later levels,
complicating the agent’s progress. Increasing amounts of mushrooms also cause
the centipede segments to reach the agent quickly, limiting the agent’s action
choices in certain situations. We encourage the agent to destroy mushrooms
whenever possible. The agent receives a small cost ($-$2) for shooting at a
mushroom and weakening it. This cost increases ($-$5, $-$7, $-$10) with each
additional shot that weakens and eventually removes a mushroom from the
environment. However, the agent is also encouraged to leave vertical tunnels
of six or more contiguous mushrooms ($-$500) so that centipedes are funneled
into them and their segments can be easily destroyed.

Figure B.5: A flea leaving a trail of mushrooms as it moves from the top of
the screen to the bottom in the game _Centipede_. The left image is earlier in
time than the right image.

There are fewer enemies in _Centipede_ than _Millipede_. Fleas take the place
of bees and yield the same cost ($-$300). Both require two shots to destroy.
However, unlike bees, fleas move more quickly after the first shot. Another
enemy, scorpions, possess a high destruction cost ($-$500). Scorpions cause
mushrooms they touch to turn poisonous; these mushrooms behave just as in
_Millipede_. Lastly, spiders are present and yield a cost that is proportional
to how close they are to the agent when destroyed ($-$300 to $-$1200). Spiders
zig-zag through the environment, sometimes blocking the agent. They do,
however, randomly clear mushrooms in their path.

The agent loses a life ($+$1000) when it is hit by any enemy. The agent gains
a life, up to a maximum of six, for every 12000 in-game points earned
($-$1000). A game ends when all of the agent’s lives are gone. Good policies
should hence choose context-specific actions that minimize the total cost.

## B.2.2. State-Action Space

Action Space. The action spaces for both _Centipede_ and _Millipede_ are
limited to six discrete actions. For every twentieth step, the agent has the
option of moving in one of four directions, up, down, left, and right, by
simulating directional-pad button presses. It can also remain stationary. At
any time, the agent can simulate a press of the action button in an attempt to
fire a bolt, provided that one is loaded. The chosen action is then repeated
over the next nineteen steps. Repeating the motions in this way prevents
significant jitter, which generally helps improve gameplay performance. All
other GameBoy buttons are disabled.

We permit the agent to string up to three arbitrary button presses together to
form a compound action that is executed over up to a set number of game
frames. While performing a compound action, any additional button presses made
by the agent are ignored.

State Space. We evaluated a variety of state spaces for both games. We
initially considered convolutional autoencoders that were pre-trained on a
half-hour of human gameplay videos and fixed during reinforcement learning. We
then considered pre-trained convolutional and recurrent-convolutional
autoencoders that could be updated during reinforcement learning.

Figure B.6: A visualization of template-correlation sprite recognition for the
game _Millipede_. The right image shows the grid-occupancy labels for the game
frame on the left.

Neither of these options fare well. The former yields poor features for
gameplay, as they are uncoupled from the extrinsic reward structure and hence
the inferred policy. The latter approach produces representations with the
same issues. They are also often altered too greatly over time to facilitate
good learning convergence. Moreover, online adaptation of the features can
cause significant learning stagnations for strategies that used pre-defined
annealing schedules for the exploration rate. This makes a fair assessment of
the exploration strategies difficult.

To facilitate fair comparison of the different strategies, we rely on a fixed
state space composed of static and dynamic features. For each game frame, we
determine which grid cells are occupied and use knowledge of the game sprites
to recognize the agent, enemies, and any environment objects. An example of a
labeled game frame is given in figure B.6. The entire labeled occupancy grid
is then taken as the static feature representation of a game state. For the
dynamic features, we characterize both the changes and the directional
movement of any objects over the previous twenty game frames. This is done
using a primitive optical flow process at the sprite level, not the pixel
level. Objects which have not been altered in some way are ignored in the
dynamic-feature representation.

$H\\!(p(s_{t+1}|s_{t},a_{t}))$$\mathcal{S}$1234567887654321$Q(s,a)$

Figure B.7: (middle) Depiction of the state-space organization for
_Millipede_. Here, we randomly selected ten thousand visited states, across
ten random runs, and projected them via UMAP. Each state is color coded
according to it’s maximum learned $Q$-value across all available actions. The
plot shows that the states are roughly divided into two groups, those that
have moderate to high expected costs and those with low expected costs.
(bottom left) Call-outs one through four correspond to the former group. The
first call-out, for instance, corresponds to the agent just having been hit by
an enemy and losing a life. The remaining call-outs correspond to states where
the agent cannot readily lower costs greatly. (bottom right) Call-outs five
through eight correspond to the latter group. For example, the eighth call-out
shows that the agent is about to receive a large reduction in costs due to the
DDT canister being active and taking out several millipede segments. Each
call-out is spatially referenced to the state space plot in the middle. (top
left) The average next-state transition surprise after training has concluded.
The plot shows that the agent has sufficiently explored much of the space and
understands the transition dynamics well.

$\|\partial Q(s_{t},a_{t})/\partial s_{t,ij}\|_{1}$$\mathcal{S}$12341234

Figure B.8: (middle) Depiction of the state-action-space organization for
_Millipede_. Here, we use the same states as in figure B.7. Each state is
color coded according to the dominant action chosen after learning concluded.
The plot shows that contiguous groups of action clusters emerge for scenarios
with related $Q$-values. (bottom left) Call-outs one and two correspond to
cases where the agent cannot readily lower its costs. In the first call-out,
for example, the enemies are located behind the agent. The agent’s best course
of action is to move to the right and down so that it can begin to target some
of the enemies. (bottom right) Call-outs three and four correspond to cases
where the agent can achieve moderate cost reductions. In both situations, the
agent’s best option is to remain stationary and shoot, as it will eventually
destroy all of the millipede segments. Due to the similarity of states
depicted in the call-outs, they naturally cluster together in the UMAP
embedding. For each call-out, we provide feature gradient maps that illustrate
what features the agent uses to make its decision. The maps show that the
agent fixates on local features that are relevant over the next time step and
subsequent ones for a short-term horizon.

$H\\!(p(s_{t+1}|s_{t},a_{t}))$$\mathcal{S}$1234567887654321$Q(s,a)$

Figure B.9: (middle) Depiction of the state-space organization for
_Centipede_. Here, we randomly selected ten thousand visited states, across
ten random runs, and projected them via UMAP. Each state is color coded
according to it’s maximum learned $Q$-value across all available actions. The
plot shows that the states are roughly divided into two groups, those that
have moderate to high expected costs and those with low expected costs.
(bottom left) Call-outs one through four correspond to the former group. The
first call-out, for instance, corresponds to the agent just having been hit by
an enemy and losing a life. The remaining call-outs correspond to states where
the agent cannot readily lower costs greatly. (bottom right) Call-outs five
through eight correspond to the latter group. For example, the eighth call-out
shows that the agent is about to receive a large reduction in costs due to the
DDT canister being active and taking out several millipede segments. Each
call-out is spatially referenced to the state space plot in the middle. (top
left) The average next-state transition surprise after training has concluded.
The plot shows that the agent has sufficiently explored much of the space and
understands the transition dynamics well.

$\|\partial Q(s_{t},a_{t})/\partial s_{t,ij}\|_{1}$$\mathcal{S}$12341234

Figure B.10: (middle) Depiction of the state-action-space organization for
_Centipede_. Here, we use the same states as in figure B.7. Each state is
color coded according to the dominant action chosen after learning concluded.
The plot shows that contiguous groups of action clusters emerge for scenarios
with related $Q$-values. (bottom left) Call-outs one and two correspond to
cases where the agent cannot readily lower its costs. In the first call-out,
for example, the enemies are located behind the agent. The agent’s best course
of action is to move to the right and down so that it can begin to target some
of the enemies. (bottom right) Call-outs three and four correspond to cases
where the agent can achieve moderate cost reductions. In both situations, the
agent’s best option is to remain stationary and shoot, as it will eventually
destroy all of the millipede segments. Due to the similarity of states
depicted in the call-outs, they naturally cluster together in the UMAP
embedding. For each call-out, we provide feature gradient maps that illustrate
what features the agent uses to make its decision. The maps show that the
agent fixates on local features that are relevant over the next time step and
subsequent ones for a short-term horizon.

This latter characterization of states is appropriate for both _Centipede_ and
_Millipede_. The features are tied to the games’ objectives and hence the
reward structures. Due to how we compute the grid-occupancy features, their
interpretability remains the same throughout the entire learning process. All
of these traits aid in efficiently discerning good agent behaviors.

There are additional practical appeals to using such a feature representation.
Foremost, it is straightforward to specify. This is because, in both games,
the grid size and shape that defines the environment remains constant. Only
the objects and their locations within the grid change over time. Tabular
policies with a finite state count can thus be considered. Secondly, the
features can be reliably discerned in real time using simple correlation-based
template recognition. This stems from the fact that the appearances of the
agent, enemies, and objects also do not change greatly. There are also few
sprite animations in both games.

## B.3. Simulation Supplement

We illustrate that context-specific groupings arise when learning using the
value of information.

Similar to the results presented in [ZahavyT-conf2016a], there appears to be a
hierarchical, spatio-temporal aggregation of the state space when using value-
of-information-based exploration. In both games, the agent begins in a low-
cost state. It is rarely in a position to immediately score points and thus
must navigate in the environment to align with an enemy and fire bolts. This
is shown, for instance, in the second and third call-outs in figure B.7 and
figure B.9. As the agent progresses through the early parts of the games, it
predominantly shifts between low- and moderate-cost states. The former are
visited whenever the agent has no ability to score, such as when it must move
from one side of the environment to the other to target an enemy or when
enemies are blocked by mushrooms. The latter case is illustrated in the third
call-out in figure B.7. These states also correspond to whenever the agent is
clearing blocks of mushrooms, as in the third and forth call-outs in figure
B.9. Moderate-cost states are visited when the agent can target one or more
common enemies, like spiders, in quick succession. Once the agent has cleared
a few levels, its opportunities for scoring greatly improve. Rare enemies
begin to appear in these levels. Common enemies also spawn more rapidly. The
agent thus spends more time in moderate- to high-cost states. Examples of
these states are depicted in the fifth through eighth call-outs of figure B.7
and the seventh and eighth call-outs in figure B.9. Eventually, though, the
agent is overwhelmed. Sometimes, it cannot clear mushrooms quickly enough,
leaving it vulnerable to waves of quickly-moving enemies. Other times, enemies
spawn at the fringes of the environment and the agent has little time to dodge
them. It thus always moves to a low-cost death state. Examples are given in
the first call-out of figure B.7 and figure B.9.

Alongside the state-space aggregation is one of the action space. By the end
of training, there are fifteen action groups that emerge, as shown in figure
B.8 and figure B.10, which are spread across some thirty well-defined clusters
for each game. All of these groups is usually well correlated with cost. Not
surprisingly, clusters associated with firing bolts correspond either to
states or near states with large costs. Sometimes, however, bolt firing groups
correspond with moderate-cost states, since there is a delay for a bolt to
strike an enemy or environmental object, like a mushroom. Those action groups
related to movement have varying degrees of association with low- and
moderate-cost states. For example, certain types of movement, like left or
right, may coincide with moderate-cost states, since the agent achieves
alignment with an enemy. Alternatively, the agent may move away from an enemy,
thus allowing it to avoid being hit and playing the game. Other movement
directions, like up and down, are typically associated with low-cost states.
Unless the agent has happened to score, due to a bolt hit, then there is
typically no cost reduction for such actions. There does not appear to be a
strong correlation between states associated with agent death and actions,
however. Any type of action can feasibly be executed as the agent is struck
and dies. Based on the transition-uncertainty plots in figure B.7 and figure
B.9, we can be relatively assured that the chosen action groups are stable for
these simulations. The highest transition entropy appears to be moderately
low, suggesting that the agent understands well the environment dynamics and
hence what it should do to consistently attain low costs.

The action groups in figure B.8 and figure B.10 depict decision making at the
macro scale. At the local scale, there are multiple factors that influence the
agent’s action choices and hence the observed action aggregation. Examples of
the factors, which are illustrated by inferred saliency maps, are provided at
the bottom of the figures. These saliency maps highlight that, at least for
value-of-information-based searches, the positions of the agents and nearest
enemies are paramount for decision making. The type of enemy also dictates how
the agent will respond. Rare enemies hence precedence over common ones, unless
the agent is either threatened or currently engaged with an enemy. If the
agent is threatened by nearby enemies, then spiders are often targeted more
readily than centipede segments. The former move more quickly and less
predictably and hence have a greater chance of colliding with the agent.
Earwigs are also prioritized over many other enemy types, since hitting them
can cause them to accelerate quickly toward the agent. The location of fired
bolts is of additional importance. It, alongside other features, determines
whether the agent can move on to another objective or must continue pursuing
its current one. Surprisingly, nearby objects, like mushrooms, often do not
influence the action choice, and hence macro-level behaviors. It would appear
that the agent mainly favors targeting enemies and that clearing mushrooms is
a byproduct of that. It is only when the environment is littered with
mushrooms that the agent begins to destroy them frequently after dispatching
enemies. Alternatively, stray bolts naturally remove them from the
environment.

The other search strategies that we consider Section 5 do not consistently
yield an easily interpretable aggregation. They often explore too
ineffectively to uncover a near-optimal estimate of the value function. The
action clusters are hence more diffuse and mixed. The local features used for
decision making are also much less coherent.

## References

## Appendix C

In this appendix, we provide additional experimental results to motivate our
approach for adapting the exploration rate of the value of information.

We begin by specifying a double-deep-$Q$ network for mapping game frames into
action-value magnitudes and expected environment costs (see Appendix C.1). We
then significantly augment the capabilities of this network, since the games
that we consider are rather complex and agent skill acquisition can be slow.
We integrate tree-based searches, with fast roll-outs, to evaluate potential
action strings and how they enable the agent to complete various objectives.
We also use uncertainty-based searches to force the agent into under-
investigated regions of the state-action space. The overall exploration
process is guided by the value of information with pseudo-arc-length path-
following.

We then present experimental results on over forty game environments (see
Appendix C.2). We show that our network and exploration mechanism outperforms
state-of-the-art alternatives on each game. It also completes games more
effectively than human players in many instances.

## C.1. Simulation Preliminaries

## C.1.1. Deep Value-of-Information Search

For the games that we used in Section 5, the environments were simplistic
enough to permit manually defining the state-action space. This is not the
case for the games that we consider in this appendix. The environments here
are typically much more visually rich, which prohibits easily specifying and
extracting gameplay features.

Here, we use double-deep-$Q$ networks [vanHasseltH-conf2016a] with prioritized
experience replay [SchaulT-conf2016a, HorganD-conf2018a] to implicitly uncover
game-specific state features from images. Such networks utilize continuous-
valued features to regress action-value magnitudes and infer discrete action
choices for each game frame.

Due to the large number of the environments that we consider, we are unable to
manually provide dense reward signals. We often rely on game-supplied scores,
which can be sparse and delayed. These scores can also be deceptive, in the
sense that they do not necessarily reflect the agent’s true progress. They
therefore do not always provide enough supervision that enable the agents to
complete multifaceted objectives. Even our game-tailored metrics can have
these flaws. Deep-$Q$-based approaches can thus stall early during learning,
including the version that we use.

Somewhat analogous to expert iteration [AnthonyT-coll2017a], we consider a
simultaneous, on-policy investigation of the state space to overcome stalling.
This process is illustrated in figure C.1. Much like Monte Carlo tree search
[GuoX-coll2014a, SilverD-jour2016a, SilverD-jour2017a], each game frame
becomes a base node of an ever-expanding $k$-ary tree. Possible actions are
chosen for this base node, yielding leaf nodes. The simulation then moves to
the branch with the best action value plus a bonus that depends on a stored
probability for that edge. Each new node on the branch is then processed by
the double-deep-$Q$ network. At the end of each simulation, the leaf node is
evaluated in one two ways. The first is by the deep network. The second is via
a fast, roll-out policy network, which chooses actions until some termination
condition is met. The tentative winning action for the base node is then
selected using a game-specific cost function. Finally, the state-action values
are back-propagated to track the mean value of all evaluations in the sub-tree
below that action.

Even with tree search, large parts of the state-action space may go
uninvestigated. Poor agent behaviors may be encountered in rare, but
important, situations, stymieing progress. We force the agent to explore such
regions via an uncertainty-based constraint [ChentanezN-coll2005a, BellemareM-
coll2016a]. That is, we implement a lightweight convolutional autoencoder,
trained on game frames, which is fed into another deep network that
approximates the game’s transition function by predicting the next frame for
the current action. Whenever the next state is not properly predicted by this
network, around some region about the true state, we add that transition to
the experience replay buffer and impose that the associated action be taken.
We also weight that action’s importance more heavily during value-of-
information search to ensure that it will likely be chosen. Here, we measure
prediction accuracy using our matrix-based [GiraldoLGS-jour2014a, SledgeIJ-
jour2022a] cross-entropy-to-go criterion [SledgeIJ-jour2022b]. This criterion
promotes minimax-optimal convergence, in a dimensionally agnostic way, so it
is well suited for comparing empirical state transitions for high-dimensional
observations.

Both the tree search and uncertainty-based searches supply principled guesses
as to the action that should be taken. We aggregate the scores and treat them
as a modified action-state value-function for value-of-information
exploration. Pseudo-arc-length path-following is employed to automatically
tune the exploration rate.

## C.1.2. Network Architectures

The above training process leverages dual networks. The first is a fast roll-
out architecture for action selection during the tree searches. The second is
a feature backbone for deep-$Q$-based action selection.

For the former, we use three convolutional layers. The input to the first
layer is a 160$\times$144-pixel grayscale image from the GameBoy emulator. It
is acted on by 64 filters that have a stride of 4. The next two layers have
strides of 2 and 1, respectively, with the same number of filters. The
receptive fields are of sizes 8$\times$8, 4$\times$4, and 3$\times$3\. Feature
maps are appropriately mirror-padded where necessary. Rectified-linear
activation functions are applied throughout. After the third layer, we cascade
a convolutional-LSTM cell that has 64 filters each with a receptive field of
3$\times$3\. The recurrent length is 30 game frames, which corresponds to
about half a second of real game-time for a GameBoy running at the default
clock rate. Gradient clipping is used for the LSTM cells to ensure learning
stability and accelerate training [ZhangJ-conf2020a].

The feature backbone that we use for the double-deep-$Q$ network differs from
convention. We consider five blocks of two convolutional layers each with
varying stride amounts. The first layer uses 5$\times$5 filters with strides
of 2, while the second through fifth layers rely on 3$\times$3 convolutions
with unit strides. The number of filters for each layer is fixed to 128 along
the main feature path. Rectified-linear activation functions are applied
throughout. Bi-directional convolutional-LSTM cells are added at the beginning
of the second through fifth blocks to mix feature content across time. These
have 64 filters. The receptive field size is consistent with the other
convolutional layers in each block. The LSTM cells have a frame length of 30.
After the second block, the backbone extracts multi-scale features using a
combination of dilated convolutions [ChenLC-jour2018a] and bi-directional
convolutional-LSTM cells. We use 3$\times$3 kernels with dilation rates of 2
and unit strides. The filter sizes are the same for the convolutional-LSTM
layers. Both layer types use 64 filters each. The outputs of the various
multi-scale blocks are aggregated and flattened in dual fully-connected layers
with 256 processing elements each.

## C.1.3. Learning Protocols

Figure C.1: A visual overview of deep, curiosity-based reinforcement learning
with the value of information. At each time step, the current game state is
fed into a value-of-information-trained deep network that assesses a potential
best action and estimates its action-state-value-function magnitude. This game
state, $s_{t}$, is also used as a local root node that represents the starting
point for a Monte Carlo tree search. Each simulation for this search traverses
the edge with the best action value, $V(s_{t},a_{t+m})$, plus some
augmentation term, $u(p(s_{t},a_{t+m}))$, $m\\!\geq\\!0$, that depends on some
prior probability for that edge. A corresponding action, in this case, button
presses, is used experience a transition to a new state, $s_{t+q}$,
$q\\!>\\!0$, which becomes a leaf node of the tree. If this leaf node is not a
terminal state, then it may be expanded. The new node is processed once by the
deep network and the output probabilities are stored as priors for each
action. At the end of the simulation, the leaf node is evaluated in one of two
ways. The first is by using the deep network, which supplies an action-state
magnitude, $Q_{\theta}(s_{t+q},a_{t+m})$. The second is via a fast roll-out
policy network, where a winning action sequence is chosen using a function
$r_{\theta^{\prime}}(s_{t+q},a_{t+m})$. The action values are then updated to
track the average value of all evaluations in the explored sub-trees. After
this back-propagation occurs, the best-performing action for the current game
state is additionally evaluated from the context of how well it improves the
agent’s understanding of the state transition dynamics. This yields a final
action response.

Both of our networks have several parameters. In each case, the discount
factor is set to 0.99. The learning rate is 0.001 and decreases exponentially
to 0.00003 across 50000 episodes. Each episode is anywhere from 50 to 2500
steps. The number of steps between the target network updates is 5000. The
network relies on mini-batch sizes of 32, which helps preempt terminating at
local optima [HardtM-conf2016a]. ADAM, with the default parameters, is used
for training [KingmaDP-conf2015a]. Nearly identical parameter values are
employed for the alternate approaches that we evaluate. For some approaches,
though, we use RMSProp [MukkamalaMC-conf2017a] to be consistent with the
recommendations of the authors.

Our double-deep-$Q$ network relies on prioritized experience replay. In all of
our simulations, we use a prioritization constant of 0.6, an importance-
sampling exponential factor of 0.4, and an proportional prioritization offset
of 0.01. A replay capacity of 750000 state transitions is used to provide
large state-action coverage [FedusW-conf2020a]. As noted above, we add state
transitions suggested by the uncertainty-based search to this buffer. We
augment the buffer by 500000 entries to handle for these transitions. The
replay memory is sampled to update the network every four steps. Mini-batches
of size 32 are again used. The same protocols are considered for the alternate
learning approaches except where different experience replay mechanisms are
explicitly considered.

Action exploration is conducted via epsilon-greedy search in the alternate
deep-$Q$-learning approaches. We consider a either a scheduled exploration
rate or an adaptive version. In the former case, we linearly decrease the
exploration rate from 0.99 to 0.1 over 1500 episodes. For the latter case, we
use a cross-entropy-based adjustment combined with an initial annealing
schedule. Whenever the cross-entropy between two probabilistic policies is at
or above 0.35, then the exploration rate is decreased by a multiplicative
factor of 0.925. If the policy cross-entropy is above that threshold, then the
exploration factor is multiplicatively increased by 1.025. We perform this
test for every pair of policies separated by 20 episodes to discern if many
updates are being made to the policy entries. Maximum and minimum exploration
rates, for this case, are 0.99 and 0.1, respectively.

For our network, we use the value of information to choose actions. Pseudo-
arc-length path-following is applied to update the exploration rate
automatically. We set the policy accuracy to 0.01. Decreasing the value beyond
this threshold did little to improve policy performance and simply increases
the optimization time. For the exploration rate, we consider an initial value
of 0.99. Lower values increase that chance that solution-surface backtracking
will be needed to find the optimal bifurcation. Learning can significantly
stagnate during a backtracking period.

In the continuous state-action-space case, our criterion involves estimating a
Shannon mutual information term. This is not trivial, given the potentially
high intrinsic dimensionality of the spaces, which precludes the use of
kernel-density estimation. Variational approximation schemes would also
encounter issues, since they too converge at a rate which depends on the space
dimension. We therefore rely on our group’s matrix-based Rényi’s mutual
information estimator [GiraldoLGS-jour2014a] posed in reproducing-kernel
Hilbert spaces. This estimator satisfies all of the properties that Rényi
considered for mutual information [RenyiA-coll1976a]. Like our cross-entropy
version [SledgeIJ-jour2022a], its convergence rate is independent of the
sample dimensionality, due to the provable connections with kernel mean
embeddings [SriperumbudurBK-conf2008a, FukumizuK-coll2011a]. Our work in
[SledgeIJ-jour2022a] shows that this estimator is additionally minimax
optimal. We have also demonstrated our group’s matrix-based estimators are
differentiable and that automated differentiation schemes can be reliably used
to form accurate gradients for mini-batches. Our group’s estimator
[GiraldoLGS-jour2014a] therefore is well suited for extending value-of-
information-based path-following to the continuous case.

Our group’s matrix-based mutual information estimator has two parameters that
must be set. The first is the kernel bandwidth for the chosen kernel that is
used to map samples to a functional space of probability measures. We use
Gaussian kernels with bandwidths of 0.5. The second is the exponential factor,
or order, of the estimator. We select an order of 1.01 so that Rényi’s mutual
information becomes almost equivalent to Shannon mutual information.

The uncertainty-based search compares a model of the environment dynamics to
those that are observed. To specify this model, we continuously update a
recurrent-convolutional autoencoder network, where the encoder topology is the
same as the feature backbone in our double-deep-$Q$ network. The bottleneck
features from the autoencoder are fed into a fully-connected layer to predict
the next-state features conditioned on those of the current state and the
chosen action. Our matrix-based cross-entropy criterion [SledgeIJ-jour2022a]
is used to compare the posterior distribution over dynamics models after
observing the state transition and the distribution over possible environment
dynamics models given the preceding history of observed states and actions.
Gaussian kernels, with bandwidths of 0.35, map the samples to an infinite-
dimensional function space for comparison. We leverage mini-batches of 32
samples to iteratively estimate the cross-entropy scores. Those scores that
are a standard deviation away from a moving average are added to the replay
memory. ADAM, with the default parameter values, is again used to update the
network parameters.

The results we present are obtained from thirty Monte Carlo simulations
performed for each method. Learning is terminated after 50000 episodes. We
then average the results and normalize them against both random play and human
play. This was done to capture the dominant trends of each method for the
various games. Due to the large number of methods and quantities being
compared, we only plot averages. We also only report the average performance
for each game since we consider a large number of environments.

## C.2. Simulation Supplement

We now compare our deep, value-of-information approach with alternatives.
These include deep-$Q$ networks [MnihV-conf2016a], double-deep-$Q$ networks
[vanHasseltH-conf2016a] and their prioritized [SchaulT-conf2016a, HorganD-
conf2018a] and noisy [FortunatoM-conf2018a, PlappertM-conf2018a] versions, A3C
[MnihV-conf2016a], and Rainbow [HesselM-conf2018a, ObandoCeronJS-conf2021a].
We use epsilon-greedy exploration, for each network other than our own, with
either fixed annealing rates or adaptive schedules driven by policy cross-
entropy thresholds.

Average Player Performance

Expert Player Performance

fstreamBomberman-1-1-Beat-small.mp4dict/Type/Filespec/F (Bomberman-1-1-Beat-
small.mp4)/UF (Bomberman-1-1-Beat-small.mp4)/EF <</F
>>dict/Type/RichMediaInstance/Subtype/Video/Asset /Params
<</FlashVars(source=Bomberman-1-1-Beat-
small.mp4&skin=SkinOverAllNoFullNoCaption.swfskinAutoHide=trueskinBackgroundColor=0x5F5F5FskinBackgroundAlpha=0.75)>>dict/Type/RichMediaConfiguration/Subtype/Video/Instances
[]dict/Type/RichMediaContent/Assets <</Names [(Bomberman-1-1-Beat-small.mp4)
]>>/Configurations []dict/Activation <</Condition/XA/Presentation
<</Style/Embedded>>>>/Deactivation
<</Condition/PI>>1156.3706pt51.3117pt0.0pt/Subtype/RichMedia/BS <</W
0/S/S>>/Contents (embedded video file:Bomberman-1-1-Beat-small.mp4)/NM
(rma:Bomberman-1-1-Beat-small.mp4)/AP <</N >>/RichMediaSettings
/RichMediaContent fstreamBattletoads-1-1-Beat-small.mp4dict/Type/Filespec/F
(Battletoads-1-1-Beat-small.mp4)/UF (Battletoads-1-1-Beat-small.mp4)/EF <</F
>>dict/Type/RichMediaInstance/Subtype/Video/Asset /Params
<</FlashVars(source=Battletoads-1-1-Beat-
small.mp4&skin=SkinOverAllNoFullNoCaption.swfskinAutoHide=trueskinBackgroundColor=0x5F5F5FskinBackgroundAlpha=0.75)>>dict/Type/RichMediaConfiguration/Subtype/Video/Instances
[]dict/Type/RichMediaContent/Assets <</Names [(Battletoads-1-1-Beat-small.mp4)
]>>/Configurations []dict/Activation <</Condition/XA/Presentation
<</Style/Embedded>>>>/Deactivation
<</Condition/PI>>1156.3706pt50.589pt0.0pt/Subtype/RichMedia/BS <</W
0/S/S>>/Contents (embedded video file:Battletoads-1-1-Beat-small.mp4)/NM
(rma:Battletoads-1-1-Beat-small.mp4)/AP <</N >>/RichMediaSettings
/RichMediaContent fstreamDigDug-1-2-Beat-small.mp4dict/Type/Filespec/F
(DigDug-1-2-Beat-small.mp4)/UF (DigDug-1-2-Beat-small.mp4)/EF <</F
>>dict/Type/RichMediaInstance/Subtype/Video/Asset /Params
<</FlashVars(source=DigDug-1-2-Beat-
small.mp4&skin=SkinOverAllNoFullNoCaption.swfskinAutoHide=trueskinBackgroundColor=0x5F5F5FskinBackgroundAlpha=0.75)>>dict/Type/RichMediaConfiguration/Subtype/Video/Instances
[]dict/Type/RichMediaContent/Assets <</Names [(DigDug-1-2-Beat-small.mp4)
]>>/Configurations []dict/Activation <</Condition/XA/Presentation
<</Style/Embedded>>>>/Deactivation
<</Condition/PI>>1156.3706pt51.3117pt0.0pt/Subtype/RichMedia/BS <</W
0/S/S>>/Contents (embedded video file:DigDug-1-2-Beat-small.mp4)/NM
(rma:DigDug-1-2-Beat-small.mp4)/AP <</N >>/RichMediaSettings /RichMediaContent
fstreamRType2-1-1-Beat-small.mp4dict/Type/Filespec/F (RType2-1-1-Beat-
small.mp4)/UF (RType2-1-1-Beat-small.mp4)/EF <</F
>>dict/Type/RichMediaInstance/Subtype/Video/Asset /Params
<</FlashVars(source=RType2-1-1-Beat-
small.mp4&skin=SkinOverAllNoFullNoCaption.swfskinAutoHide=trueskinBackgroundColor=0x5F5F5FskinBackgroundAlpha=0.75)>>dict/Type/RichMediaConfiguration/Subtype/Video/Instances
[]dict/Type/RichMediaContent/Assets <</Names [(RType2-1-1-Beat-small.mp4)
]>>/Configurations []dict/Activation <</Condition/XA/Presentation
<</Style/Embedded>>>>/Deactivation
<</Condition/PI>>1156.3706pt50.589pt0.0pt/Subtype/RichMedia/BS <</W
0/S/S>>/Contents (embedded video file:RType2-1-1-Beat-small.mp4)/NM
(rma:RType2-1-1-Beat-small.mp4)/AP <</N >>/RichMediaSettings /RichMediaContent
fstreamCastlevania-1-1-Beat-small.mp4dict/Type/Filespec/F
(Castlevania-1-1-Beat-small.mp4)/UF (Castlevania-1-1-Beat-small.mp4)/EF <</F
>>dict/Type/RichMediaInstance/Subtype/Video/Asset /Params
<</FlashVars(source=Castlevania-1-1-Beat-
small.mp4&skin=SkinOverAllNoFullNoCaption.swfskinAutoHide=trueskinBackgroundColor=0x5F5F5FskinBackgroundAlpha=0.75)>>dict/Type/RichMediaConfiguration/Subtype/Video/Instances
[]dict/Type/RichMediaContent/Assets <</Names [(Castlevania-1-1-Beat-small.mp4)
]>>/Configurations []dict/Activation <</Condition/XA/Presentation
<</Style/Embedded>>>>/Deactivation
<</Condition/PI>>1156.3706pt51.3117pt0.0pt/Subtype/RichMedia/BS <</W
0/S/S>>/Contents (embedded video file:Castlevania-1-1-Beat-small.mp4)/NM
(rma:Castlevania-1-1-Beat-small.mp4)/AP <</N >>/RichMediaSettings
/RichMediaContent fstreamSnowBrosJr-1-1-Beat-small.mp4dict/Type/Filespec/F
(SnowBrosJr-1-1-Beat-small.mp4)/UF (SnowBrosJr-1-1-Beat-small.mp4)/EF <</F
>>dict/Type/RichMediaInstance/Subtype/Video/Asset /Params
<</FlashVars(source=SnowBrosJr-1-1-Beat-
small.mp4&skin=SkinOverAllNoFullNoCaption.swfskinAutoHide=trueskinBackgroundColor=0x5F5F5FskinBackgroundAlpha=0.75)>>dict/Type/RichMediaConfiguration/Subtype/Video/Instances
[]dict/Type/RichMediaContent/Assets <</Names [(SnowBrosJr-1-1-Beat-small.mp4)
]>>/Configurations []dict/Activation <</Condition/XA/Presentation
<</Style/Embedded>>>>/Deactivation
<</Condition/PI>>1156.3706pt51.3117pt0.0pt/Subtype/RichMedia/BS <</W
0/S/S>>/Contents (embedded video file:SnowBrosJr-1-1-Beat-small.mp4)/NM
(rma:SnowBrosJr-1-1-Beat-small.mp4)/AP <</N >>/RichMediaSettings
/RichMediaContent fstreamBaseball-1-1-Beat-small.mp4dict/Type/Filespec/F
(Baseball-1-1-Beat-small.mp4)/UF (Baseball-1-1-Beat-small.mp4)/EF <</F
>>dict/Type/RichMediaInstance/Subtype/Video/Asset /Params
<</FlashVars(source=Baseball-1-1-Beat-
small.mp4&skin=SkinOverAllNoFullNoCaption.swfskinAutoHide=trueskinBackgroundColor=0x5F5F5FskinBackgroundAlpha=0.75)>>dict/Type/RichMediaConfiguration/Subtype/Video/Instances
[]dict/Type/RichMediaContent/Assets <</Names [(Baseball-1-1-Beat-small.mp4)
]>>/Configurations []dict/Activation <</Condition/XA/Presentation
<</Style/Embedded>>>>/Deactivation
<</Condition/PI>>1156.3706pt51.3117pt0.0pt/Subtype/RichMedia/BS <</W
0/S/S>>/Contents (embedded video file:Baseball-1-1-Beat-small.mp4)/NM
(rma:Baseball-1-1-Beat-small.mp4)/AP <</N >>/RichMediaSettings
/RichMediaContent fstreamBustAMove2-1-1-Beat-small.mp4dict/Type/Filespec/F
(BustAMove2-1-1-Beat-small.mp4)/UF (BustAMove2-1-1-Beat-small.mp4)/EF <</F
>>dict/Type/RichMediaInstance/Subtype/Video/Asset /Params
<</FlashVars(source=BustAMove2-1-1-Beat-
small.mp4&skin=SkinOverAllNoFullNoCaption.swfskinAutoHide=trueskinBackgroundColor=0x5F5F5FskinBackgroundAlpha=0.75)>>dict/Type/RichMediaConfiguration/Subtype/Video/Instances
[]dict/Type/RichMediaContent/Assets <</Names [(BustAMove2-1-1-Beat-small.mp4)
]>>/Configurations []dict/Activation <</Condition/XA/Presentation
<</Style/Embedded>>>>/Deactivation
<</Condition/PI>>1156.3706pt51.3117pt0.0pt/Subtype/RichMedia/BS <</W
0/S/S>>/Contents (embedded video file:BustAMove2-1-1-Beat-small.mp4)/NM
(rma:BustAMove2-1-1-Beat-small.mp4)/AP <</N >>/RichMediaSettings
/RichMediaContent fstreamKirbysPinballLand-1-3-Beat-
small.mp4dict/Type/Filespec/F (KirbysPinballLand-1-3-Beat-small.mp4)/UF
(KirbysPinballLand-1-3-Beat-small.mp4)/EF <</F
>>dict/Type/RichMediaInstance/Subtype/Video/Asset /Params
<</FlashVars(source=KirbysPinballLand-1-3-Beat-
small.mp4&skin=SkinOverAllNoFullNoCaption.swfskinAutoHide=trueskinBackgroundColor=0x5F5F5FskinBackgroundAlpha=0.75)>>dict/Type/RichMediaConfiguration/Subtype/Video/Instances
[]dict/Type/RichMediaContent/Assets <</Names [(KirbysPinballLand-1-3-Beat-
small.mp4) ]>>/Configurations []dict/Activation <</Condition/XA/Presentation
<</Style/Embedded>>>>/Deactivation
<</Condition/PI>>1156.3706pt51.3117pt0.0pt/Subtype/RichMedia/BS <</W
0/S/S>>/Contents (embedded video file:KirbysPinballLand-1-3-Beat-small.mp4)/NM
(rma:KirbysPinballLand-1-3-Beat-small.mp4)/AP <</N >>/RichMediaSettings
/RichMediaContent fstreamWarioLand-1-1-Beat-small.mp4dict/Type/Filespec/F
(WarioLand-1-1-Beat-small.mp4)/UF (WarioLand-1-1-Beat-small.mp4)/EF <</F
>>dict/Type/RichMediaInstance/Subtype/Video/Asset /Params
<</FlashVars(source=WarioLand-1-1-Beat-
small.mp4&skin=SkinOverAllNoFullNoCaption.swfskinAutoHide=trueskinBackgroundColor=0x5F5F5FskinBackgroundAlpha=0.75)>>dict/Type/RichMediaConfiguration/Subtype/Video/Instances
[]dict/Type/RichMediaContent/Assets <</Names [(WarioLand-1-1-Beat-small.mp4)
]>>/Configurations []dict/Activation <</Condition/XA/Presentation
<</Style/Embedded>>>>/Deactivation
<</Condition/PI>>1156.3706pt51.3117pt0.0pt/Subtype/RichMedia/BS <</W
0/S/S>>/Contents (embedded video file:WarioLand-1-1-Beat-small.mp4)/NM
(rma:WarioLand-1-1-Beat-small.mp4)/AP <</N >>/RichMediaSettings
/RichMediaContent fstreamMortalKombat2-1-1-Beat-small.mp4dict/Type/Filespec/F
(MortalKombat2-1-1-Beat-small.mp4)/UF (MortalKombat2-1-1-Beat-small.mp4)/EF
<</F >>dict/Type/RichMediaInstance/Subtype/Video/Asset /Params
<</FlashVars(source=MortalKombat2-1-1-Beat-
small.mp4&skin=SkinOverAllNoFullNoCaption.swfskinAutoHide=trueskinBackgroundColor=0x5F5F5FskinBackgroundAlpha=0.75)>>dict/Type/RichMediaConfiguration/Subtype/Video/Instances
[]dict/Type/RichMediaContent/Assets <</Names [(MortalKombat2-1-1-Beat-
small.mp4) ]>>/Configurations []dict/Activation <</Condition/XA/Presentation
<</Style/Embedded>>>>/Deactivation
<</Condition/PI>>1156.3706pt51.3117pt0.0pt/Subtype/RichMedia/BS <</W
0/S/S>>/Contents (embedded video file:MortalKombat2-1-1-Beat-small.mp4)/NM
(rma:MortalKombat2-1-1-Beat-small.mp4)/AP <</N >>/RichMediaSettings
/RichMediaContent fstreamDoubleDragon-1-1-Beat-small.mp4dict/Type/Filespec/F
(DoubleDragon-1-1-Beat-small.mp4)/UF (DoubleDragon-1-1-Beat-small.mp4)/EF <</F
>>dict/Type/RichMediaInstance/Subtype/Video/Asset /Params
<</FlashVars(source=DoubleDragon-1-1-Beat-
small.mp4&skin=SkinOverAllNoFullNoCaption.swfskinAutoHide=trueskinBackgroundColor=0x5F5F5FskinBackgroundAlpha=0.75)>>dict/Type/RichMediaConfiguration/Subtype/Video/Instances
[]dict/Type/RichMediaContent/Assets <</Names [(DoubleDragon-1-1-Beat-
small.mp4) ]>>/Configurations []dict/Activation <</Condition/XA/Presentation
<</Style/Embedded>>>>/Deactivation
<</Condition/PI>>1156.3706pt51.3117pt0.0pt/Subtype/RichMedia/BS <</W
0/S/S>>/Contents (embedded video file:DoubleDragon-1-1-Beat-small.mp4)/NM
(rma:DoubleDragon-1-1-Beat-small.mp4)/AP <</N >>/RichMediaSettings
/RichMediaContent fstreamDonkeyKong-1-1-Beat-small.mp4dict/Type/Filespec/F
(DonkeyKong-1-1-Beat-small.mp4)/UF (DonkeyKong-1-1-Beat-small.mp4)/EF <</F
>>dict/Type/RichMediaInstance/Subtype/Video/Asset /Params
<</FlashVars(source=DonkeyKong-1-1-Beat-
small.mp4&skin=SkinOverAllNoFullNoCaption.swfskinAutoHide=trueskinBackgroundColor=0x5F5F5FskinBackgroundAlpha=0.75)>>dict/Type/RichMediaConfiguration/Subtype/Video/Instances
[]dict/Type/RichMediaContent/Assets <</Names [(DonkeyKong-1-1-Beat-small.mp4)
]>>/Configurations []dict/Activation <</Condition/XA/Presentation
<</Style/Embedded>>>>/Deactivation
<</Condition/PI>>1156.3706pt51.3117pt0.0pt/Subtype/RichMedia/BS <</W
0/S/S>>/Contents (embedded video file:DonkeyKong-1-1-Beat-small.mp4)/NM
(rma:DonkeyKong-1-1-Beat-small.mp4)/AP <</N >>/RichMediaSettings
/RichMediaContent fstreamStreetFighter2-1-1-Beat-small.mp4dict/Type/Filespec/F
(StreetFighter2-1-1-Beat-small.mp4)/UF (StreetFighter2-1-1-Beat-small.mp4)/EF
<</F >>dict/Type/RichMediaInstance/Subtype/Video/Asset /Params
<</FlashVars(source=StreetFighter2-1-1-Beat-
small.mp4&skin=SkinOverAllNoFullNoCaption.swfskinAutoHide=trueskinBackgroundColor=0x5F5F5FskinBackgroundAlpha=0.75)>>dict/Type/RichMediaConfiguration/Subtype/Video/Instances
[]dict/Type/RichMediaContent/Assets <</Names [(StreetFighter2-1-1-Beat-
small.mp4) ]>>/Configurations []dict/Activation <</Condition/XA/Presentation
<</Style/Embedded>>>>/Deactivation
<</Condition/PI>>1156.3706pt51.3117pt0.0pt/Subtype/RichMedia/BS <</W
0/S/S>>/Contents (embedded video file:StreetFighter2-1-1-Beat-small.mp4)/NM
(rma:StreetFighter2-1-1-Beat-small.mp4)/AP <</N >>/RichMediaSettings
/RichMediaContent fstreamSuperMarioLand-1-1-Beat-small.mp4dict/Type/Filespec/F
(SuperMarioLand-1-1-Beat-small.mp4)/UF (SuperMarioLand-1-1-Beat-small.mp4)/EF
<</F >>dict/Type/RichMediaInstance/Subtype/Video/Asset /Params
<</FlashVars(source=SuperMarioLand-1-1-Beat-
small.mp4&skin=SkinOverAllNoFullNoCaption.swfskinAutoHide=trueskinBackgroundColor=0x5F5F5FskinBackgroundAlpha=0.75)>>dict/Type/RichMediaConfiguration/Subtype/Video/Instances
[]dict/Type/RichMediaContent/Assets <</Names [(SuperMarioLand-1-1-Beat-
small.mp4) ]>>/Configurations []dict/Activation <</Condition/XA/Presentation
<</Style/Embedded>>>>/Deactivation
<</Condition/PI>>1156.3706pt51.3117pt0.0pt/Subtype/RichMedia/BS <</W
0/S/S>>/Contents (embedded video file:SuperMarioLand-1-1-Beat-small.mp4)/NM
(rma:SuperMarioLand-1-1-Beat-small.mp4)/AP <</N >>/RichMediaSettings
/RichMediaContent fstreamKirbysDreamLand2-1-1-Beat-
small.mp4dict/Type/Filespec/F (KirbysDreamLand2-1-1-Beat-small.mp4)/UF
(KirbysDreamLand2-1-1-Beat-small.mp4)/EF <</F
>>dict/Type/RichMediaInstance/Subtype/Video/Asset /Params
<</FlashVars(source=KirbysDreamLand2-1-1-Beat-
small.mp4&skin=SkinOverAllNoFullNoCaption.swfskinAutoHide=trueskinBackgroundColor=0x5F5F5FskinBackgroundAlpha=0.75)>>dict/Type/RichMediaConfiguration/Subtype/Video/Instances
[]dict/Type/RichMediaContent/Assets <</Names [(KirbysDreamLand2-1-1-Beat-
small.mp4) ]>>/Configurations []dict/Activation <</Condition/XA/Presentation
<</Style/Embedded>>>>/Deactivation
<</Condition/PI>>1156.3706pt51.3117pt0.0pt/Subtype/RichMedia/BS <</W
0/S/S>>/Contents (embedded video file:KirbysDreamLand2-1-1-Beat-small.mp4)/NM
(rma:KirbysDreamLand2-1-1-Beat-small.mp4)/AP <</N >>/RichMediaSettings
/RichMediaContent  Figure C.2: Comparison of a deep, value-of-information-
based agent that uses pseudo-arc-length path following with the current best
reinforcement learning methods in the literature and various exploration-rate-
adjustment strategies. (left) We consider forty Nintendo GameBoy games, about
thirty of which are complicated. The performance of each agent was averaged
across twenty random trials and normalized with respect to random play, at the
0% level, and the average of three expert human players, at the 100% level.
Note that the performance scale is non-linear. The results indicate that our
approach facilitates an efficient search of the state-action space. Our agents
substantially outperform those produced by alternate exploration-rate
adaptations for the same number of processed game frames. In almost all games,
our agents perform on a level that is either comparable to or exceeds that of
average human players. (right) We have provided gameplay videos for sixteen of
the environments to highlight the capabilities of our value-of-information-
based agents. These videos qualitatively demonstrate that the agents learn to
play the various games effectively. The policies used for these videos were
sampled a quarter of the way through training. We recommend viewing this
document within Adobe Acrobat DC; click on an image and enable content to
start playback of the corresponding video.

We use several Nintendo GameBoy environments for this comparison. These games
are visually more complex than those of the Atari arcade learning environments
[BellemareM-conf2015a]. The gameplay mechanics can also can change
dramatically within a given game. Both traits make the GameBoy environments
challenging for learning.

There is, however, one issue with these environments. In some circumstances,
the agents could potentially remember and recall sequences of actions without
much need to generalize. The corresponding learned policies would thus not be
particularly robust. This is, predominantly, a concern for games like _Super
Mario Land_ , _Bust-a-Move_ , _Pac-Man_ , and _Donkey Kong_ , each of which
has a unique starting point and environmental conditions that remain
consistent, more or less, across playthroughs. Many games from the arcade
learning environments also share this issue.

To provide a fair comparison, we consider an approach taken by Nair et al.
[NairA-conf2015a]. During learning, we randomly sample one of a thousand
emulator save states that are taken from the playthrough of two human experts.
The save states are uniformly distributed across time. We then begin agent
training from one of these states and use the above protocols to discern when
to stop. The results that we present are averages compiled after learning has
concluded and the agents are running in an inference-only mode using a fixed
policy. Given that the agents encounter the game in an out-of-order manner, it
should not be possible for them to easily memorize a fixed strategy.

As shown in figure C.2, the deep-value-of-information-based agents appear to
generalize well. Gameplay performance beyond that of human experts is observed
for over a third of the games, and performance above that of an average human
player is observed in two-thirds of the games. None of the other approaches do
as well as ours, though, in any of the environments.

It has been established that deep-$Q$ networks, along with their extensions,
can infer optimal policies [WangZT-conf2022a]. For all of the games that we
consider, though, this did not occur within the episode limit for any of the
runs. The results are worse than value-of-information searches by anywhere
from twenty to over two-hundred percent. Increasing the episode limit did
little to improve performance for these alternatives. Refining the parameter
grid search also does not alter costs much. Similarly, tailoring the initial
parameters to each of the games helps little, as it only yields a modest five
to fifteen percent improvement. One of the few changes that we found to yield
meaningful improvements entails integrating both self-imitation learning [OhJ-
conf2018a] and offline learning [AgarwalR-conf2020a]. Including both learning
styles improves performance from the baseline, reported in figure C.2, by
about thirty percent for all of the alternate methods. Another change was
including recurrent [HochreiterS-coll1996a] and convolutional-recurrent cells
[ShiX-coll2015a] throughout the deep networks to act on temporal
characteristics of the games. Making this change raises baseline performance
by about ten percent. Even with such enhancements, though, the capabilities of
the agents from the alternate networks still typically lags behind those of
our own. Performance is poorer too.

## References