# The Game of Hidden Rules: A New Kind of Benchmark Challenge for Machine
Learning

Eric Pulick1∗, Shubham Bharti1, Yiding Chen1, Vladimir Menkov2
Yonatan Mintz1, Paul Kantor1, Vicki M. Bier1
1University of Wisconsin - Madison, 2Rutgers University
{pulick, sbharti, ychen695, ymintz, pkantor<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

As machine learning (ML) is more tightly woven into society, it is imperative
that we better characterize ML’s strengths and limitations if we are to employ
it responsibly. Existing benchmark environments for ML, such as board and
video games, offer well-defined benchmarks for progress, but constituent tasks
are often complex, and it is frequently unclear how task characteristics
contribute to overall difficulty for the machine learner. Likewise, without a
systematic assessment of how task characteristics influence difficulty, it is
challenging to draw meaningful connections between performance in different
benchmark environments. We introduce a novel benchmark environment that offers
an enormous range of ML challenges and enables precise examination of how task
elements influence practical difficulty. The tool frames learning tasks as a
“board-clearing game,” which we call the Game of Hidden Rules (GOHR). The
environment comprises an expressive rule language and a captive server
environment that can be installed locally. We propose a set of benchmark rule-
learning tasks and plan to support a performance leader-board for researchers
interested in attempting to learn our rules. GOHR complements existing
environments by allowing fine, controlled modifications to tasks, enabling
experimenters to better understand how each facet of a given learning task
contributes to its practical difficulty for an arbitrary ML algorithm.

##  1 Introduction

Learning computational representations of rules has been one of the main
objectives of the field of machine learning (ML) since its inception. In
contrast to pattern recognition and classification (the other main domains of
ML), rule learning is concerned with identifying a policy or computational
representation of the hidden process by which data has been generated. These
sorts of learning tasks have been common in applications of ML to real world
settings such as biological research [10], imitation learning [7], and most
recently game play [13, 21]. Since this process involves sequential
experimentation with the system, much of the recent work exploring rule
learning has focused on using reinforcement learning (RL) for learning rules
as optimal policies of Markov decision processes.

Rules, however, can be quite complex in many applications, and may not map to
a single optimal policy, but instead to a whole set of optimal policies. For
instance, in the case of protein folding, there may be multiple correct ways
in which a potential set of atoms can be folded into a feasible molecule.
While computational and theoretical results exist to characterize which
properties of the models or algorithms may cause these differences, these
results are highly task-dependent, making it difficult to compare relative
task difficulty. Thus, an important question is whether some characteristics
make particular rules easier or harder to learn by a specific algorithm (or in
general). To date, this has been a difficult question to answer, since many
rules of interest in the real world are multifaceted and not well
characterized. For instance, while there are effective RL algorithms that can
play go, chess, and backgammon, it is not clear which specific features of go
and chess make them more difficult to learn in practice than backgammon (e.g.,
is it the number of pieces? size of the board? lack of random elements?). In
order to interrogate these questions, new ways of generating rules and data
must be devised that allow for researchers to examine these characteristics in
a controlled environment.

In this paper, we propose a new data environment called the Game Of Hidden
Rules (GOHR), which aims to help researchers in this endeavor. The main
component of the environment is a game played in a $6\times 6$ board with game
pieces of different shapes and colors. The task of the learner is to clear the
board in each round by moving the game pieces to “buckets” at the corners of
the board according to a hidden rule, known to the researcher but not to the
learner. Our environment allows researchers to express a hidden rule using a
rich syntax that can map to many current tasks of interest in both the
classification and RL settings. A key advantage of our environment is that
researchers can control each aspect of the hidden rules and test them at a
granular level, allowing for experiments that determine exactly which
characteristics make some learning tasks harder than others and which
algorithms are better at learning specific types of rules.

The rest of the paper proceeds as follows. We first describe how our
environment relates to other data-generating environments from the literature
in Section 2. Then, in Section 3, we go into the details of GOHR and the rule
syntax, explaining how the environment can be used to interrogate the effects
of rule structure. We introduce our ML competition and refer readers to
benchmark rules, instructions, and documentation available at our public site
in Section 4. In Section 5, we present sample rules and analysis for an
example algorithm. Finally, we conclude with some discussion on the
implications of our results and on other questions that can be answered by the
GOHR environment in Section 6.

##  2 Literature Review

Learning rules remains a core challenge in many aspects of ML, particularly in
RL settings where the agent must learn iteratively from its environment. Games
have historically served as rich benchmark environments for RL, with novel
challenges in each game environment spurring progress for the field as a
whole. RL has tackled increasingly complex classical board games, such as
backgammon, chess, shogi, and go [23, 5, 19, 20, 21], eventually surpassing
the performance of human experts in each. Of late, video-game environments
have also become drivers of progress in RL. Beginning with human-level
performance in Atari 2600 games [13, 1], machine players have become
competitive with humans in a variety of environments, including real-time-
strategy and multiplayer games such as Quake III, StarCraft II, and Dota 2 [8,
16, 24, 25].

Instrumental in such RL progress has been the growing space of benchmark game
environments and supporting tools, such as the Arcade Learning Environment
[2], General Video Game AI [17], OpenAI Gym [4], Gym Retro [15], Obstacle
Tower [9], Procgen [6], and NetHack environments [11, 18]. Taken together,
these represent an impressive range of new tasks for RL agents, bridging many
gaps and challenges in achieving aspects of artificial intelligence.

We note a clear trend in these benchmark tools away from static games and
toward configurability (e.g. procedurally-generated and customizable
environments), something we believe is critical to better understanding task
difficulty. Many environments demand that agents solve complex tasks inspired
by those a human might encounter in the real world. Such tasks offer well-
defined benchmarks, but often do not support precise, controlled modifications
without affecting other aspects of the learner’s environment. We believe that
GOHR, which allows the experimenter to change the learning task without any
change to the game’s rules, playing environment, or board-clearing objective,
can serve as an important complement to existing benchmarks. GOHR’s mechanics
allow for isolated study of changes in learning tasks and their effects on
practical difficulty, an important prerequisite for the systematic study of ML
algorithms and their suitability for different tasks.

##  3 Game of Hidden Rules

In this section we describe the GOHR’s structure, syntax, and the expressivity
of the rule language. In each episode of our game, the player is presented
with a game board containing a configurable set of game pieces, each drawn
from a standard set of shapes and colors. The player’s objective is to remove
game pieces from play by dragging and dropping them into buckets located at
each corner of the game board. A “hidden rule,” unknown to the player,
determines which pieces may be placed into which buckets at a given point in
the game play. For instance, a rule might assign game pieces to specific
buckets based on their shape or color. If the player makes a move permitted by
the rule, the corresponding game piece is removed from play; otherwise, it
remains in its original location. The episode concludes once the player has
fully satisfied the rule. Typically, this occurs when all game pieces have
been cleared from play, but some rules may be fully satisfied even with some
pieces remaining on the board. The scoring for GOHR rewards players for
completing episodes in as few moves as possible, incentivizing players to
quickly discern the hidden rule.

The GOHR is played on a board with 36 identical cells, arranged in a $6\times
6$ grid. Each cell on the board is indexed with a label, 1-36, and has $x$ and
$y$ coordinates 1-6. Each bucket is indexed with a label, 0-3, with $x,y$
coordinates in the set $\\{(0,0),(0,7),(7,0),(7,7)\\}$. The game board,
including all numeric labels, can be seen in Figure 2.

In each GOHR experiment, the game engine generates game pieces from user-
defined sets of shapes and colors. Depending on the experimental goals, these
sets can be of arbitrary size. If no specification is provided in the
experimental setup, the game engine defaults to a set of 4 shapes (circles,
triangles, squares, stars) and 4 colors (red, blue, black, yellow). The
experiment designer may add shapes or colors to the experiment in the
associated color and shape configuration files. A sample board, built using a
set of 4 shapes and 4 colors, is shown in Figure 2.

Figure 1: Game board diagram, with numeric position labels included.

Figure 2: Game board, configured with 4 colors and 4 shapes, as it would be
seen by a human player.

Boards in the GOHR can be defined in advance of play (to permit precise
experimenter control), or can be generated randomly by the game engine
according to a set of input parameters. This flexibility allows the
experimenter to evaluate the impact of deterministic or randomized “curricula”
(e.g., to determine whether seeing a particular set of boards in a specified
order is conducive to learning). When generating boards randomly, the
experimenter must specify the minimum and maximum numbers of game pieces,
colors, and shapes to appear on each new board; the game engine randomly
selects values in the range [minimum, maximum] for each quantity and generates
boards accordingly. Additional documentation can be found at our public site,
as noted in Section 4.

###  3.1 Rule definition

A rule playable within GOHR must be defined in a standalone file. Each rule is
constructed from one or more rule lines, each of which is built from one or
more atoms. For instance, a two-line rule with five atoms might look like:

(atom 1) (atom 2) (atom 3)

(atom 4) (atom 5)

Only one rule line is active at a time; this active line determines the
current rule state (how game pieces may be placed into buckets for the
player’s next move). In the example above, the rule state is formed by the
contents of either atoms 1, 2, and 3 or atoms 4 and 5, depending on which line
is active. Later sections discuss the mechanisms by which the active rule line
can change during play.

Each atom maps a set of game pieces to a set of permitted buckets and is
defined as follows:

(count, shapes, colors, positions, buckets)

The “count” parameter defines the number of successful moves that the atom
permits (also referred to as its “metering”). Any game pieces matching the
“shapes,” “colors,” and “positions” specified in the atom are accepted in its
corresponding set of “buckets.” Multiple values can be listed for each non-
count field, and are grouped in square brackets. For example, the rule that
“stars and triangles go in bucket 0, squares go in bucket 1, and circles can
go in bucket 2 and bucket 3” would be constructed with the following three
atoms on a single rule line:

(*, [star, triangle], *, *, 0) (*, square, *, *, 1) (*, circle, *, *, [2,3])

The $*$ character denotes a wildcard. In the count field, $*$ denotes that the
atom is not metered; in the shape, color, or position fields, it denotes that
every value for that feature is included in the allowable set for that atom.
In the above example, the atoms apply to any star, triangle, square, or circle
on the board, regardless of their color or position. Since the atoms are not
metered, any shape may be placed in its corresponding bucket at any point in
the game.

###  3.2 Rule expressivity

The above syntax permits an enormous range of rules within the GOHR.
Stationary rules, such as the previous example, are those where the permitted
bucket set for each game piece never changes during play. In that example, any
star or triangle is allowed only in bucket 0, any square allowed only in
bucket 1, etc., for as long as the game is played. Thus, stationary rules
permit the experimenter to study the practical difficulty associated with
learning feature-based patterns–i.e., those related to game-piece color,
shape, position, or a combination thereof. Though stationary rules have no
dependence on play history, these rules can still be made arbitrarily
difficult, such as designating a specific bucket for every possible
combination of a game piece’s features. Importantly, since the set of colors
and shapes used is left to the experimenter, such rules can become arbitrarily
complex.

Non-stationary rules are those in which the permitted bucket set for game
pieces changes during play. Non-stationary rules can involve following a
defined sequence, such as as clearing a triangle, a square, a circle, and then
a star in that order (repeating the sequence as needed). It is also possible
to create non-stationary rules with an implicit priority between objects, such
as clearing all available red pieces before all available blue pieces, or
clearing pieces on the board from top to bottom. Methods for implementing non-
stationary rules are described below.

As mentioned, each atom contains a “count” field dictating the number of
corresponding correct moves that atom permits. For example, the following rule
requires the player to alternate between placing game pieces in the top (0,1)
and bottom (2,3) buckets:

(1, *, *, *, [0,1])

(1, *, *, *, [2,3])

The first rule line is always active at the beginning of a new episode, in
this case allowing any game piece on the board to be placed into either bucket
0 or bucket 1. Once a player makes a move satisfying one (or more) of the
atoms on the active rule line, the counts associated with the satisfied atoms
are decremented by one. An atom with a count of 0 is considered exhausted and
no longer accepts moves. At each move, the game engine evaluates the active
rule line and the current board; if there are no valid moves available to the
player, the engine makes the next rule line active and resets all counts in
the new line. Thus, when all atoms on the active rule line are exhausted,
there are no valid moves available and the engine moves control to the next
rule line. If there are no lines below the current rule line, the first rule
line is made active again. In this example, when the player puts a game piece
in buckets 0 or 1, the first atom becomes exhausted and the second line
becomes active. After placing a piece into either bucket 2 or 3, the second
atom is exhausted and the first line is reset and becomes active again,
repeating this cycle until the board is cleared.

GOHR also permits the experimenter to attach a count to each rule line. When
the line is active, this count decrements each time any atom on the line is
satisfied. For instance, a rule that alternates between uniquely assigning
shapes and colors to buckets would look like:

1 (*, star, *, *, 0) (*, square, *, *, 1) (*, circle, *, *, 2) (*, triangle,
*, *, 3)

1 (*, *, red, *, 0) (*, *, blue, *, 1) (*, *, black, *, 2) (*, *, yellow, *,
3)

If the rule-line count is exhausted, the game engine makes the next line
active, even if there are non-exhausted atoms on that line. For this example,
the active rule line will alternate after each successful move, regardless of
which atom in the active line is satisfied. If no count is provided for a
given rule line, the game engine assumes that the rule line is not metered and
can be used until all atoms on that line are exhausted or no valid move exists
for the game pieces currently on the board.

The GOHR rule syntax allows the experimenter to write expressions in an atom’s
bucket field that define sequences based on previous successful moves. The
game engine stores values for the bucket that most recently accepted any game
piece ($p$) as well as the bucket that most recently accepted an item of each
color ($pc$) and shape ($ps$). A simple rule expressible using these values is
“objects must be placed in buckets in a clockwise pattern, beginning with any
bucket”:

(1, *, *, *, [0,1,2,3])

(*, *, *, *, p+1)

The expressions used in the buckets field are evaluated modulo 4 to ensure
that the resultant expression gives values in the range 0-3. The game engine
also supports the terms “nearby” and “remotest” as bucket definitions, which
allow the experimenter to require that game pieces be put into either the
closest or furthest bucket, respectively, evaluated by Euclidean distance.

The arrangement of atoms allows the experimenter to encode priority between
component tasks within a rule. For instance, the rule that “all red pieces go
into bucket 1, _then_ all blue pieces go into bucket 2” would be expressed as
follows:

(*, *, red, *, 1)

(*, *, blue, *, 2)

Since both the first rule line and associated atom are not metered, they can
never become exhausted, even if there are no more red game pieces left on the
board. However, as noted above, the engine evaluates if there are any valid
moves available to the player given the current rule line; if there are no
valid moves available, the engine shifts control to the next line. In this
example, once the player has cleared all red game pieces from the board, the
engine will make the second rule line active.

##  4 Documentation and Competition

Beyond using GOHR for the study of task characteristics and their impact on
difficulty, we hope that interested researchers will share performance results
on benchmark rules with us so that we can disseminate community-wide benchmark
performance. To this effect, we plan to host a public leader-board through
June 2023 which will present results for benchmark rules, updated on a weekly
basis. The public site, http://sapir.psych.wisc.edu:7150/w2020/captive.html,
houses documentation for downloading and setting up the captive game server
(CGS), configuring and running experiments, a list of benchmark rules beyond
what is presented in Section 5, as well as the public leader-board.

##  5 Sample Analysis

In this section we propose a series of sample rules, a sample ML algorithm
(MLA), performance metrics, and useful data presentation methods.

###  5.1 Sample rules

We present results for the following sample rules, each played using the
default set of 4 shapes and colors. Boards were randomly generated with 9 game
pieces per board and the minimum and maximum parameters for color and shape
set to 4.

  1. 1.

Color Match: Each of the 4 shapes is uniquely assigned to a bucket

(*, star, *, *, 0) (*, triangle, *, *, 1) (*, square, *, *, 2) (*, circle, *,
*, 3)

  2. 2.

Clockwise: The first game piece can go in any bucket, but each subsequent
piece must go in the next clockwise bucket

(1, *, *, *, [0,1,2,3])

(*, *, *, *, (p + 1))

  3. 3.

B23 then B01: Game pieces must be alternatively placed in the bottom and top
buckets

(1, *, *, *, [2,3])

(1, *, *, *, [0,1])

  4. 4.

B3 then B1: Game pieces must be alternatively placed in buckets 3 and 1

(1, *, *, *, 3)

(1, *, *, *, 1)

###  5.2 Sample MLA

We model the GOHR as an episodic Markov decision process (MDP) characterized
by the tuple, $\mathcal{M}=(\mathcal{S},\mathcal{A},R,P,\mu,H)$. $\mathcal{A}$
is the action space, where each action puts the object in row $r$ and column
$c$ in bucket $b$:
$\mathcal{A}=\\{(r,c,b):r\in[6],c\in[6],b\in\\{(0,0),(0,7),(7,0),(7,7)\\}\\}$.
Before introducing the state space, we first formally describe the board. In a
board $B$, the cell at row $r$, column $c$ is characterized by color and
shape: $B[r,c].color\in\\{\text{red, black, blue, green, $\emptyset$}\\}$,
$B[r,c].shape\in\\{\text{star, square, triangle, circle, $\emptyset$}\\}$,
where we define the shape and color of an empty cell to be $\emptyset$.
$\mathcal{S}$ is the state space, where each state
$S_{t}=(B_{0},A_{0},B_{1},A_{1},\cdots,B_{t-1},A_{t-1},B_{t})$ is a sequence
including all the historical boards $B_{i}$’s and actions $A_{i}$’s up to time
step $t$. We define $B_{-1}$ to be an empty board before the board generation
process. $P$ is the deterministic transition probability matrix specified by
the hidden rule. Importantly, when action $A_{t}$ is not accepted, resulting
in no change to the board, we still insert the board $B_{t+1}$ and action
$A_{t}$ to $S_{t+1}$. In that case, $B_{t+1}=B_{t}$. $R$ is the deterministic
reward function. If an action is accepted or the board is already cleared, the
reward is set to be $0$; otherwise, the reward is $-1$. Specifically:
$R(S_{t},A_{t})=0$ if $B_{t+1}\neq B_{t}$ or $B_{t}=B_{-1}$;
$R(S_{t},A_{t})=-1$, o.w. $\mu$ is the initial state distribution. Since the
initial state $S_{0}=(B_{0})$, which only includes the initial board, $\mu$ is
determined by the board generating process in Section 3. $H$ is the time
horizon that characterizes the number time steps in each episode. The MDP
evolves according to Section 3. We define the value function as the sum of
future rewards by taking action according to policy $\pi$, i.e.
$V^{\pi}(S_{t})=\mathbb{E}\left[\sum_{k=t}^{H-1}R(S_{k},A_{k})\right]$, where
the expectation is over the potential randomness of the policy. Similarly, we
define the state-action value function by the sum of future rewards by taking
action $A_{t}$ at state $S_{t}$ and following policy $\pi$ after that, i.e.
$Q^{\pi}(S_{t},A_{t})=R(S_{t},A_{t})+V^{\pi}(S_{t+1})$. Because the step
information has already been encoded in the state, we do not need to use step
$h$ as the subscript for the value function and state-action value function.
The goal of the learner is to find a policy $\pi$ to maximize the expected
cumulative reward $\mathbb{E}_{S_{0}\sim\mu}\left[V^{\pi}(S_{0})\right]$.

Even though the MDP $\mathcal{M}$ has a finite state space $\mathcal{S}$, the
size of $\mathcal{S}$ scales exponentially in $H$, which makes it impractical
to learn a proper policy directly. Instead, we handcraft a feature mapping
$\phi(\cdot,\cdot)$ to extract only the essential information for some
particular hidden rules. The feature function maps each state-action pair
$(S_{t},A)$ to a $3720$-dimensional Boolean vector $\phi(S_{t},A)$. Recall
that each action $A$ chooses a cell $(r,c)$ and puts the object in this cell
in bucket $b$. $\phi(S_{t},A)$ encodes the following information to Boolean
variables: the shape and color information of the cell chosen by $A$, the
target bucket, and the shape, color, and bucket information of the last
accepted action. Products of some of the Boolean variables are also included
in $\phi(S_{t},A)$. Interested readers are referred to Appendix A.1.1 for
additional details on the feature representation.

We use a variant of DQN [12], a model-free algorithm, as our learning
algorithm. DQN models the state-action value function $Q$ as a linear function
in the feature vector $\phi$: $Q(s,a;\theta)=\theta^{\top}\phi(s,a)$ and tries
to estimate the optimal $Q^{*}$ using stochastic gradient updates on moving
loss $L$:

$L(\theta)=\mathbbm{E}\left[(y-Q(s,a;\theta))^{2}\right],$

where $y=r+\max_{a^{\prime}}Q(s^{\prime},a^{\prime};\theta^{\text{target}})$
is the target $Q$ estimate obtained for the sample $(s,a,r,s^{\prime})$. We
distinguish the running parameter iterate $\theta$ and the target parameter
$\theta^{\text{target}}$. Unlike the DQN in [12], $\theta^{\text{target}}$ is
updated less frequently to stabilize the algorithm.

Additionally, the algorithm maintains a buffer memory of size $1000$ for past
experiences and samples a batch of $128$ tuples to calculate gradients at each
time step. We run the DQN with an $\epsilon$-greedy behavior policy. The
$\epsilon$ starts at $0.9$ and terminates at $0.001$. $\epsilon$ decays
exponentially with step-size $200$. More precisely,
$\epsilon=0.001+(0.9-0.001)\exp(-\frac{\text{number of moves}}{200})$. For
each rule we run $100$ trials, with each trial including $200$ episodes of
length $H=100$. The full learning algorithm is described in Appendix A.1.2 and
relevant hardware information is described in Appendix A.1.3.

###  5.3 Metrics and sample results

For any given rule and MLA, difficulty can be evaluated by examining the
cumulative error count made by the MLA during each independent learning run.
Given a sufficient number of episodes (200 in this analysis), we found that
the cumulated error eventually flattened for all learning runs of our sample
DQN; we refer to the cumulated error after 200 episodes as the Terminal
Cumulated Error (TCE) for that learning run. For other rules or algorithms,
longer learning runs might be necessary. As an example, Figure 3 shows the
cumulated error, tallied by episode, of our sample DQN for 100 separate
learning runs of the Color Match rule. Median learning curves, also plotted by
episode, across all four sample rules can be found in Figure 4. We found
median cumulated error plots to be a useful tool for visualizing differences
in difficulty among a set of rules, with higher curves indicating greater
difficulty. Box-and-whisker plots for the distributions of TCE for each sample
rule are shown in Figure 5, with higher distributions again indicating greater
difficulty.

Figure 3: Cumulated error curves for 100 MLA learning runs of the Color Match
rule. The y-axis is logarithmic to capture the highly skewed nature of the
distribution. The marginal plot to the right displays a kernel density
estimate for the Terminal Cumulated Error for this rule and MLA. Figure 4:
Median cumulated errors at each episode across 100 MLA learning runs for each
sample rule. The shaded regions denote the 95% confidence intervals for the
medians, calculated using 50,000 bootstraps. Figure 5: Box-and-whisker plots
of TCE for each learning run for all sample rules. The chart has a broken
y-axis with a scale change to capture the most extreme outliers. The colored
area is the interquartile range (IQR), with whiskers displaying the most
extreme data point within 1.5 IQRs of the upper and lower quartiles.

Although the heavily-skewed TCE distribution seen for Color Match was not seen
for all sample rules, it highlights the need for non-parametric tests when
comparing rules. To perform pairwise comparison of rule difficulty, for
instance between arbitrary rules $A$ and $B$, we recommend using the Mann-
Whitney-Wilcoxon U-Test [14] with TCE as the point-metric. The test compares
every TCE value associated with rule $A$ against every TCE value associated
with rule $B$; the associated test statistic sums the number of times that
values from $A$ exceed values from $B$, with ties counting for 0.5. We found
that one-sided U-Tests ranked rules identically ($p<0.002$) to the difficulty
order given by the height of the median cumulated error curves in Figure 4.
The sample rules were chosen to illustrate a range of rules possible within
the rule game, not with a particular variation in task characteristics in
mind; we expect interested researchers to design targeted sets of rules
investigating certain characteristics of learning tasks and to perform similar
comparisons to assess their practical difficulty.

In addition to comparing the difficulty of two different rules for a given
algorithm, the U-Test also supports comparison between different MLAs. The
U-test test statistics can be used to form an “ease ratio,” representing the
ratio of learning runs that, for example, rule $A$ was found easier than rule
$B$ by a given MLA. We propose aggregating ease ratios for many MLAs across
the set of benchmark rules to create a tournament graph as described in [22].
The ranking method corrects for the fact that algorithms $R$ and $S$ may have
solved a different subset of rules, leading to the possibility that $R$
encountered a larger fraction of “easy” rules (where rule difficulty can be
assessed by the TCE of all algorithms that attempt a particular rule).
Additional information regarding the methods to be used in ranking competition
submissions can be found at the public site.

##  6 Discussion

The GOHR tool provides a capability for studying the performance of MLAs in a
novel and principled way. Using the expressive rule syntax, researchers can
make precise changes to rules of interest to study how they affect algorithm
performance. As suggested in Section 5, this approach can be used to compare
the performance of different algorithms on any specific set of rules and to
see the effect of rule characteristics (position, properties, static/dynamic)
on MLA performance. This is a useful complement to present competitions among
ML algorithms on existing board games and video games that can only look at
complex tasks without the same granularity. We note here that the GOHR can
also be played by human rule learners, enabling comparison of human learning
and ML on an equal footing. For additional discussion on this please refer to
[3].

Each choice of ML parametrization, learning model, and optimization is
expected to produce different results. With the GOHR, we believe it will be
possible to interrogate how these choices interact with specific rule
characteristics to result in differences in practical performance. With this
goal in mind, we are sharing the complete suite of tools with all interested
researchers. We hope that researchers using the GOHR tool for ML research will
share their findings to help this inquiry.

Given our current analysis and discussion, we believe there are at least two
interesting broad research questions that can be answered with the GOHR
environment. First, can a given ML algorithm learn many substantially
different rules, thus approaching a general learning. Second, when results for
multiple algorithms are available, is it possible to cluster rules into
difficulty classes based on practical algorithm performance.

## Acknowledgments and Disclosure of Funding

Support for this research was provided by the University of Wisconsin-Madison
Office of the Vice Chancellor for Research and Graduate Education with funding
from the Wisconsin Alumni Research Foundation, and by the National Science
Foundation under Grant No. 2041428. Any opinions, findings, and conclusions or
recommendations expressed in this material are those of the author(s) and do
not necessarily reflect the views of the sponsors. We also thank Mr. Kevin Mui
for building the first instance of the GOHR, to support research on human
learning.

## References

  * Badia et al. [2020] Adrià Puigdomènech Badia, Bilal Piot, Steven Kapturowski, Pablo Sprechmann, Alex Vitvitskyi, Zhaohan Daniel Guo, and Charles Blundell.  Agent57: Outperforming the Atari Human Benchmark.  In _Proceedings of the 37th International Conference on Machine Learning_ , pages 507–517. PMLR, November 2020.  URL https://proceedings.mlr.press/v119/badia20a.html.  ISSN: 2640-3498.
  * Bellemare et al. [2013] M. G. Bellemare, Y. Naddaf, J. Veness, and M. Bowling.  The Arcade Learning Environment: An Evaluation Platform for General Agents.  _Journal of Artificial Intelligence Research_ , 47:253–279, June 2013.  ISSN 1076-9757.  doi: 10.1613/jair.3912.  URL https://www.jair.org/index.php/jair/article/view/10819.
  * Bier et al. [2019] Vicki Bier, Paul B. Kantor, Gary Lupyan, and Xiaojin Zhu.  Can We Distinguish Machine Learning from Human Learning?  Technical report, 2019.  URL http://arxiv.org/abs/1910.03466.  _eprint: 1910.03466.
  * Brockman et al. [2016] Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba.  OpenAI Gym, June 2016.  URL http://arxiv.org/abs/1606.01540.  Number: arXiv:1606.01540 arXiv:1606.01540 [cs].
  * Campbell et al. [2002] Murray Campbell, A.Joseph Hoane, and Feng-hsiung Hsu.  Deep Blue.  _Artificial Intelligence_ , 134(1-2):57–83, January 2002.  ISSN 00043702.  doi: 10.1016/S0004-3702(01)00129-1.  URL https://linkinghub.elsevier.com/retrieve/pii/S0004370201001291.
  * Cobbe et al. [2020] Karl Cobbe, Chris Hesse, Jacob Hilton, and John Schulman.  Leveraging Procedural Generation to Benchmark Reinforcement Learning.  In _Proceedings of the 37th International Conference on Machine Learning_ , pages 2048–2056. PMLR, November 2020.  URL https://proceedings.mlr.press/v119/cobbe20a.html.  ISSN: 2640-3498.
  * Hussein et al. [2018] Ahmed Hussein, Mohamed Medhat Gaber, Eyad Elyan, and Chrisina Jayne.  Imitation Learning: A Survey of Learning Methods.  _ACM Computing Surveys_ , 50(2):1–35, March 2018\.  ISSN 0360-0300, 1557-7341.  doi: 10.1145/3054912.  URL https://dl.acm.org/doi/10.1145/3054912.
  * Jaderberg et al. [2019] Max Jaderberg, Wojciech M. Czarnecki, Iain Dunning, Luke Marris, Guy Lever, Antonio Garcia Castañeda, Charles Beattie, Neil C. Rabinowitz, Ari S. Morcos, Avraham Ruderman, Nicolas Sonnerat, Tim Green, Louise Deason, Joel Z. Leibo, David Silver, Demis Hassabis, Koray Kavukcuoglu, and Thore Graepel.  Human-level performance in 3D multiplayer games with population-based reinforcement learning.  _Science_ , 364(6443):859–865, May 2019.  ISSN 0036-8075, 1095-9203.  doi: 10.1126/science.aau6249.  URL https://www.science.org/doi/10.1126/science.aau6249.
  * Juliani et al. [2019] Arthur Juliani, Ahmed Khalifa, Vincent-Pierre Berges, Jonathan Harper, Ervin Teng, Hunter Henry, Adam Crespi, Julian Togelius, and Danny Lange.  Obstacle Tower: A Generalization Challenge in Vision, Control, and Planning.  Technical Report arXiv:1902.01378, arXiv, July 2019.  URL http://arxiv.org/abs/1902.01378.  arXiv:1902.01378 [cs] type: article.
  * Khatib et al. [2011] Firas Khatib, Seth Cooper, Michael D. Tyka, Kefan Xu, Ilya Makedon, Zoran Popović, David Baker, and Foldit Players.  Algorithm discovery by protein folding game players.  _Proceedings of the National Academy of Sciences_ , 108(47):18949–18953, November 2011.  ISSN 0027-8424, 1091-6490.  doi: 10.1073/pnas.1115898108.  URL https://pnas.org/doi/full/10.1073/pnas.1115898108.
  * Küttler et al. [2020] Heinrich Küttler, Nantas Nardelli, Alexander Miller, Roberta Raileanu, Marco Selvatici, Edward Grefenstette, and Tim Rocktäschel.  The NetHack Learning Environment.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, _Advances in Neural Information Processing Systems_ , volume 33, pages 7671–7684. Curran Associates, Inc., 2020.  URL https://proceedings.neurips.cc/paper/2020/file/569ff987c643b4bedf504efda8f786c2-Paper.pdf.
  * Mnih et al. [2013] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller.  Playing atari with deep reinforcement learning, 2013.  URL https://arxiv.org/abs/1312.5602.
  * Mnih et al. [2015] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Bellemare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis.  Human-level control through deep reinforcement learning.  _Nature_ , 518(7540):529–533, February 2015.  ISSN 0028-0836, 1476-4687.  doi: 10.1038/nature14236.  URL http://www.nature.com/articles/nature14236.
  * Nachar [2008] Nadim Nachar.  The Mann-Whitney U: A Test for Assessing Whether Two Independent Samples Come from the Same Distribution.  _Tutorials in Quantitative Methods for Psychology_ , 4(1):13–20, March 2008.  ISSN 1913-4126.  doi: 10.20982/tqmp.04.1.p013.  URL http://www.tqmp.org/RegularArticles/vol04-1/p013.
  * Nichol et al. [2018] Alex Nichol, Vicki Pfau, Christopher Hesse, Oleg Klimov, and John Schulman.  Gotta Learn Fast: A New Benchmark for Generalization in RL.  Technical Report arXiv:1804.03720, arXiv, April 2018.  URL http://arxiv.org/abs/1804.03720.  arXiv:1804.03720 [cs, stat] type: article.
  * OpenAI et al. [2019] OpenAI, Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemysław Dębiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, Rafal Józefowicz, Scott Gray, Catherine Olsson, Jakub Pachocki, Michael Petrov, Henrique P. d O. Pinto, Jonathan Raiman, Tim Salimans, Jeremy Schlatter, Jonas Schneider, Szymon Sidor, Ilya Sutskever, Jie Tang, Filip Wolski, and Susan Zhang.  Dota 2 with Large Scale Deep Reinforcement Learning.  Technical Report arXiv:1912.06680, arXiv, December 2019.  URL http://arxiv.org/abs/1912.06680.  arXiv:1912.06680 [cs, stat] type: article.
  * Perez-Liebana et al. [2016] Diego Perez-Liebana, Spyridon Samothrakis, Julian Togelius, Tom Schaul, Simon M. Lucas, Adrien Couetoux, Jerry Lee, Chong-U Lim, and Tommy Thompson.  The 2014 General Video Game Playing Competition.  _IEEE Transactions on Computational Intelligence and AI in Games_ , 8(3):229–243, September 2016.  ISSN 1943-068X, 1943-0698.  doi: 10.1109/TCIAIG.2015.2402393.  URL http://ieeexplore.ieee.org/document/7038214/.
  * Samvelyan et al. [2021] Mikayel Samvelyan, Robert Kirk, Vitaly Kurin, Jack Parker-Holder, Minqi Jiang, Eric Hambro, Fabio Petroni, Heinrich Kuttler, Edward Grefenstette, and Tim Rocktäschel.  MiniHack the Planet: A Sandbox for Open-Ended Reinforcement Learning Research.  In J. Vanschoren and S. Yeung, editors, _Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks_ , volume 1, 2021.  URL https://datasets-benchmarks-proceedings.neurips.cc/paper/2021/file/fa7cdfad1a5aaf8370ebeda47a1ff1c3-Paper-round1.pdf.
  * Silver et al. [2016] David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis.  Mastering the game of Go with deep neural networks and tree search.  _Nature_ , 529(7587):484–489, January 2016.  ISSN 0028-0836, 1476-4687.  doi: 10.1038/nature16961.  URL http://www.nature.com/articles/nature16961.
  * Silver et al. [2017] David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, Yutian Chen, Timothy Lillicrap, Fan Hui, Laurent Sifre, George van den Driessche, Thore Graepel, and Demis Hassabis.  Mastering the game of Go without human knowledge.  _Nature_ , 550(7676):354–359, October 2017.  ISSN 0028-0836, 1476-4687.  doi: 10.1038/nature24270.  URL http://www.nature.com/articles/nature24270.
  * Silver et al. [2018] David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap, Karen Simonyan, and Demis Hassabis.  A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play.  _Science_ , 362(6419):1140–1144, December 2018\.  ISSN 0036-8075, 1095-9203.  doi: 10.1126/science.aar6404.  URL https://www.science.org/doi/10.1126/science.aar6404.
  * Strang et al. [2022] Alexander Strang, Karen C. Abbott, and Peter J. Thomas.  The Network HHD: Quantifying Cyclic Competition in Trait-Performance Models of Tournaments.  _SIAM Review_ , 64(2):360–391, May 2022.  ISSN 0036-1445, 1095-7200.  doi: 10.1137/20M1321012.  URL https://epubs.siam.org/doi/10.1137/20M1321012.
  * Tesauro [1994] Gerald Tesauro.  TD-Gammon, a Self-Teaching Backgammon Program, Achieves Master-Level Play.  _Neural Computation_ , 6(2):215–219, March 1994\.  ISSN 0899-7667, 1530-888X.  doi: 10.1162/neco.1994.6.2.215.  URL https://direct.mit.edu/neco/article/6/2/215-219/5771.
  * Vinyals et al. [2017] Oriol Vinyals, Timo Ewalds, Sergey Bartunov, Petko Georgiev, Alexander Sasha Vezhnevets, Michelle Yeo, Alireza Makhzani, Heinrich Küttler, John Agapiou, Julian Schrittwieser, John Quan, Stephen Gaffney, Stig Petersen, Karen Simonyan, Tom Schaul, Hado van Hasselt, David Silver, Timothy Lillicrap, Kevin Calderone, Paul Keet, Anthony Brunasso, David Lawrence, Anders Ekermo, Jacob Repp, and Rodney Tsing.  StarCraft II: A New Challenge for Reinforcement Learning.  Technical Report arXiv:1708.04782, arXiv, August 2017.  URL http://arxiv.org/abs/1708.04782.  arXiv:1708.04782 [cs] type: article.
  * Vinyals et al. [2019] Oriol Vinyals, Igor Babuschkin, Wojciech M. Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H. Choi, Richard Powell, Timo Ewalds, Petko Georgiev, Junhyuk Oh, Dan Horgan, Manuel Kroiss, Ivo Danihelka, Aja Huang, Laurent Sifre, Trevor Cai, John P. Agapiou, Max Jaderberg, Alexander S. Vezhnevets, Rémi Leblond, Tobias Pohlen, Valentin Dalibard, David Budden, Yury Sulsky, James Molloy, Tom L. Paine, Caglar Gulcehre, Ziyu Wang, Tobias Pfaff, Yuhuai Wu, Roman Ring, Dani Yogatama, Dario Wünsch, Katrina McKinney, Oliver Smith, Tom Schaul, Timothy Lillicrap, Koray Kavukcuoglu, Demis Hassabis, Chris Apps, and David Silver.  Grandmaster level in StarCraft II using multi-agent reinforcement learning.  _Nature_ , 575(7782):350–354, November 2019.  ISSN 0028-0836, 1476-4687.  doi: 10.1038/s41586-019-1724-z.  URL http://www.nature.com/articles/s41586-019-1724-z.

##  Appendix A Appendix

###  A.1 Details of the reinforcement learning algorithm

####  A.1.1 Feature representation

The feature vector $\phi(S,A)$ is constructed with the following four
different types of components:

  1. 1.

The 12 current-step unary features $\phi_{u}(S,A)$, where $u$ can be a color,
a shape, or a bucket. If $u$ is a color:

$\phi_{u}(S_{t},A)=\mathbbm{1}{\\{B_{t}[A.r,A.c].\text{color}=u\\}}.$

If $u$ is a shape:

$\phi_{u}(S_{t},A)=\mathbbm{1}{\\{B_{t}[A.r,A.c].\text{shape}=u\\}}.$

If $u$ is a bucket:

$\phi_{u}(S_{t},A)=\mathbbm{1}{\\{A.b=u\\}}.$

  2. 2.

The 48 current-step binary features, a set of binary features that depend on
the current board configuration
$\phi_{u,v}:\mathcal{S}\times\mathcal{A}\rightarrow\\{0,1\\}$ where $(u,v)$
can be a (color, shape), (color, bucket) or (shape, bucket) tuple. These
features $\phi_{u,v}(S_{t},A)$ are defined as follows:

$u,v\in$ | $\phi_{u,v}(S_{t},A)$
---|---
color $\times$ shape | $\mathbbm{1}{\\{B_{t}[A.r,A.c].\text{color}=u\\}}\wedge\mathbbm{1}{\\{B_{t}[A.r,A.c].\text{shape}=v\\}}$
color $\times$ bucket | $\mathbbm{1}{\\{B_{t}[A.r,A.c].\text{color}=u\\}}\wedge\mathbbm{1}{\\{A.b=v\\}}$
shape $\times$ bucket | $\mathbbm{1}{\\{B_{t}[A.r,A.c].\text{shape}=u\\}}\wedge\mathbbm{1}{\\{A.b=v\\}}$

  3. 3.

The 60 last-successful-step and current-step binary features, a set of binary
features constructed from the board and action information at the last
successful step and the current step. For a time step $t>0$, let

$\ell(t)=\max\\{\tau\in\\{-1,0,\cdots,t-1\\}\text{ s.t. }B_{t}\neq
B_{\tau}\\}$

be the latest successful time step. Since $B_{-1}$ is an empty board,
$B_{-1}\neq B_{t},\,\forall t\geq 0$ until the game is over, so $\ell(t)$ is
well defined.

The features are defined as follows:
$\phi_{(u),v}:\mathcal{S}\times\mathcal{A}\rightarrow\\{0,1\\}$, where $(u)$
is extracted from the board and action information at the last successful time
step, and $v$ is extracted from the board and action information at the
current time step. Note that $u$ can be the empty set $\emptyset$ when
$\ell(t)=-1$.

$(u),v\in$ | $\phi_{(u),v}(S_{t},A)$
---|---
(color∅) $\times$ color | $\mathbbm{1}{\\{B_{\ell(t)}[A_{\ell(t)}.r,A_{\ell(t)}.c].\text{color}=u\\}}\wedge\mathbbm{1}{\\{B_{t}[A.r,A.c].\text{color}=v\\}}$
(shape∅) $\times$ shape | $\mathbbm{1}{\\{B_{\ell(t)}[A_{\ell(t)}.r,A_{\ell(t)}.c].\text{shape}=u\\}}\wedge\mathbbm{1}{\\{B_{t}[A.r,A.c].\text{shape}=v\\}}$
(bucket∅) $\times$ bucket | $\mathbbm{1}{\\{A_{\ell(t)}.b=u\\}}\wedge\mathbbm{1}{\\{A.b=v\\}}$

where $x^{\emptyset}=x\cup\\{\emptyset\\},\,\forall x\in\text{\\{color, shape,
bucket\\}}$

  4. 4.

The 3600 last-successful-step and current-step 4-ary features, a set of 4-ary
features constructed from the board and action information at the last
successful step and the current step.

$\phi_{(u,v),y,z}:\mathcal{S}\times\mathcal{A}\rightarrow\\{0,1\\}$

where $(u,v)$ are extracted from the board and action information at the last
successful time step, and $y,z$ are extracted from the current time step.
These features, $\phi_{(u,v),y,z}(S_{t},A)$, are defined as follows:

$(u,v),y,z\in$ | $\phi_{(u,v),y,z}(S_{t},A)$
---|---
$\begin{aligned} &(\text{shape}^{\emptyset},\text{color}^{\emptyset})\\\ \times&\text{shape},\text{color}\end{aligned}$ | $\begin{aligned} &\mathbbm{1}{\\{B_{\ell(t)}[A_{\ell(t)}.r,A_{\ell(t)}.c].\text{shape}=u\\}}\\\ \wedge&\mathbbm{1}{\\{B_{\ell(t)}[A_{\ell(t)}.r,A_{\ell(t)}.c].\text{color}=v\\}}\\\ \wedge&\mathbbm{1}{\\{B_{t}[A.r,A.c].\text{shape}=y\\}}\wedge\mathbbm{1}{\\{B_{t}[A.r,A.c].\text{color}=z\\}}\end{aligned}$
$\begin{aligned} &(\text{shape}^{\emptyset},\text{color}^{\emptyset})\\\ \times&\text{shape},\text{bucket}\end{aligned}$ | $\begin{aligned} &\mathbbm{1}{\\{B_{\ell(t)}[A_{\ell(t)}.r,A_{\ell(t)}.c].\text{shape}=u\\}}\\\ \wedge&\mathbbm{1}{\\{B_{\ell(t)}[A_{\ell(t)}.r,A_{\ell(t)}.c].\text{color}=v\\}}\\\ \wedge&\mathbbm{1}{\\{B_{t}[A.r,A.c].\text{shape}=y\\}}\wedge\mathbbm{1}{\\{A.b=z\\}}\end{aligned}$
$\begin{aligned} &(\text{shape}^{\emptyset},\text{color}^{\emptyset})\\\ \times&\text{color},\text{bucket}\end{aligned}$ | $\begin{aligned} &\mathbbm{1}{\\{B_{\ell(t)}[A_{\ell(t)}.r,A_{\ell(t)}.c].\text{shape}=u\\}}\\\ \wedge&\mathbbm{1}{\\{B_{\ell(t)}[A_{\ell(t)}.r,A_{\ell(t)}.c].\text{color}=v\\}}\\\ \wedge&\mathbbm{1}{\\{B_{t}[A.r,A.c].\text{color}=v\\}}\wedge\mathbbm{1}{\\{A.b=z\\}}\end{aligned}$
$\begin{aligned} &(\text{shape}^{\emptyset},\text{bucket}^{\emptyset})\\\ \times&\text{shape},\text{color}\end{aligned}$ | $\begin{aligned} &\mathbbm{1}{\\{B_{\ell(t)}[A_{\ell(t)}.r,A_{\ell(t)}.c].\text{shape}=u\\}}\wedge\mathbbm{1}{\\{A_{\ell(t)}.b=v\\}}\\\ \wedge&\mathbbm{1}{\\{B_{t}[A.r,A.c].\text{shape}=y\\}}\wedge\mathbbm{1}{\\{B_{t}[A.r,A.c].\text{color}=z\\}}\end{aligned}$
$\begin{aligned} &(\text{shape}^{\emptyset},\text{bucket}^{\emptyset})\\\ \times&\text{shape},\text{bucket}\end{aligned}$ | $\begin{aligned} &\mathbbm{1}{\\{B_{\ell(t)}[A_{\ell(t)}.r,A_{\ell(t)}.c].\text{shape}=u\\}}\wedge\mathbbm{1}{\\{A_{\ell(t)}.b=v\\}}\\\ \wedge&\mathbbm{1}{\\{B_{t}[A.r,A.c].\text{shape}=y\\}}\wedge\mathbbm{1}{\\{A.b=z\\}}\end{aligned}$
$\begin{aligned} &(\text{shape}^{\emptyset},\text{bucket}^{\emptyset})\\\ \times&\text{color},\text{bucket}\end{aligned}$ | $\begin{aligned} &\mathbbm{1}{\\{B_{\ell(t)}[A_{\ell(t)}.r,A_{\ell(t)}.c].\text{shape}=u\\}}\wedge\mathbbm{1}{\\{A_{\ell(t)}.b=v\\}}\\\ \wedge&\mathbbm{1}{\\{B_{t}[A.r,A.c].\text{color}=y\\}}\wedge\mathbbm{1}{\\{A.b=z\\}}\end{aligned}$
$\begin{aligned} &(\text{color}^{\emptyset},\text{bucket}^{\emptyset})\\\ \times&\text{shape},\text{color}\end{aligned}$ | $\begin{aligned} &\mathbbm{1}{\\{B_{\ell(t)}[A_{\ell(t)}.r,A_{\ell(t)}.c].\text{color}=u\\}}\wedge\mathbbm{1}{\\{A_{\ell(t)}.b=v\\}}\wedge\\\ &{\mathbbm{1}{\\{B_{t}[A.r,A.c].\text{shape}=y\\}}\wedge\mathbbm{1}{\\{B_{t}[A.r,A.c].\text{color}=z\\}}}\end{aligned}$
$\begin{aligned} &(\text{color}^{\emptyset},\text{bucket}^{\emptyset})\\\ \times&\text{shape},\text{bucket}\end{aligned}$ | $\begin{aligned} &\mathbbm{1}{\\{B_{\ell(t)}[A_{\ell(t)}.r,A_{\ell(t)}.c].\text{color}=u\\}}\wedge\mathbbm{1}{\\{A_{\ell(t)}.b=v\\}}\\\ \wedge&{\mathbbm{1}{\\{B_{t}[A.r,A.c].\text{shape}=y\\}}\wedge\mathbbm{1}{\\{A.b=z\\}}}\end{aligned}$
$\begin{aligned} &(\text{color}^{\emptyset},\text{bucket}^{\emptyset})\\\ \times&\text{color},\text{bucket}\end{aligned}$ | $\begin{aligned} &\mathbbm{1}{\\{B_{\ell(t)}[A_{\ell(t)}.r,A_{\ell(t)}.c].\text{color}=u\\}}\wedge\mathbbm{1}{\\{A_{\ell(t)}.b=v\\}}\\\ \wedge&{\mathbbm{1}{\\{B_{t}[A.r,A.c].\text{color}=y\\}}\wedge\mathbbm{1}{\\{A.b=z\\}}}\end{aligned}$

For any $(S,A)$-tuple, the final feature vector $\phi(S,A)$ is created by
stacking up all of the above features, which gives a feature function
$\phi:\mathcal{S}\times\mathcal{A}\rightarrow\\{0,1\\}^{3720}$.

####  A.1.2 Learning algorithm

Input : target iteration $T$, episode count $M$, buffer size $N$, batch size
$B$.

Initialize experience replay buffer memory $\mathcal{D}$ with capacity $N$.

Initialize the iterate parameters $\theta^{\text{target}}_{1}\leftarrow
0,\theta_{1,1}\leftarrow 0$.

for target iteration $\tau=1,\cdots,T$ do

for episode $e=1,\cdots,M$ do

Draw $s_{1}\sim\mu$.

for time step $t=1,\cdots,H$ do

Draw
$a_{t}\sim\epsilon\cdot\text{Unif}(A)+(1-\epsilon)\cdot\mathbbm{1}_{A}\\{a=\max_{a^{\prime}}Q(s_{t},a^{\prime};\theta_{e,t})\\}$.

Take action $a_{t}$ and observe reward $r_{t}$ and observation $x_{t+1}$.

Set $s_{t+1}\leftarrow(s_{t},a_{t},x_{t+1})$ and enque
$\left(s_{t},a_{t},r_{t},s_{t+1}\right)$ to $\mathcal{D}$.

Uniformly sample a batch
$\\{\left(s_{j},a_{j},r_{j},s^{\prime}_{j}\right)\\}|_{j=1}^{B}$ from
$\mathcal{D}$ and

set $\forall j\in[B]$, $y_{j}=r_{j}+\mathbbm{1}\\{j\text{ is
terminal}\\}\cdot\gamma\max_{a^{\prime}}Q(s^{\prime}_{j},a^{\prime};\theta^{\text{target}}_{\tau})$

Update $\theta_{e,t+1}$ using $Q$-objective
$\frac{1}{B}\sum_{j=1}^{B}\left(y_{j}-Q(s_{j},a_{j};\theta)\right)^{2}\big{|}_{\theta=\theta_{e,t}}.$

end for

Update the parameter for next episode
$\theta_{e+1,1}\leftarrow\theta_{e,H+1}$.

end for

Update the target parameter
$\theta^{\text{target}}_{\tau+1}\leftarrow\theta_{M,H+1}$.

end for

Algorithm 1 Deep Q-learning(DQN) with Experience Replay

####  A.1.3 Training hardware

For all experiments, we used a local server (at the University of Wisconsin -
Madison) running Ubuntu 20.04 LTS, with 2 Intel Xeon Silver 4214R CPUs (2.40
GHz) and 196GB of RAM. No GPUs were used in our experiments.

###  A.2 Code Licensing

The source code for the GOHR, provided at our public site, is licensed under
the Apache License version 2.0.