# Regret Minimization for Partially Observable Deep Reinforcement Learning

Peter Jin  Kurt Keutzer  Sergey Levine

###### Abstract

Deep reinforcement learning algorithms that estimate state and state-action
value functions have been shown to be effective in a variety of challenging
domains, including learning control strategies from raw image pixels. However,
algorithms that estimate state and state-action value functions typically
assume a fully observed state and must compensate for partial observations by
using finite length observation histories or recurrent networks. In this work,
we propose a new deep reinforcement learning algorithm based on counterfactual
regret minimization that iteratively updates an approximation to an advantage-
like function and is robust to partially observed state. We demonstrate that
this new algorithm can substantially outperform strong baseline methods on
several partially observed reinforcement learning tasks: learning first-person
3D navigation in Doom and Minecraft, and acting in the presence of partially
observed objects in Doom and Pong.

deep reinforcement learning, partial observability, regret

##  1 Introduction

Many reinforcement learning problems of practical interest have the property
of partial observability, where observations of state are generally non-
Markovian. Practical deep reinforcement learning algorithms fall into two
broad classes, neither of which satisfactorily deals with partial
observability despite the prevalance of partial observations in the real
world. One class of algorithms consists of value function-based methods such
as deep Q-learning (Mnih et al., 2013, 2015), which are known to be highly
sample efficient but generally assume a Markovian observation space. The other
class of algorithms consists of Monte Carlo policy gradient methods such as
trust region policy optimization (Schulman et al., 2015), which do not need to
assume Markovian observations but are less sample efficient than value
function-based methods. Some policy gradient methods such as advantage actor-
critic (Mnih et al., 2016) introduce the Markov assumption through a critic or
state-dependent baseline to improve sample efficiency.

There are two common workarounds for the problem of partial observation: (a)
learning policies and value functions on finite length observation histories,
and (b) learning recurrent policies and recurrent value functions. Finite
length observation histories concatenate the most recent raw observations into
a stack of observations, and are a simple but effective technique to
approximate the appearance of full observability. Recurrent functions can
potentially incorporate an infinite observation history, but they can be
harder to optimize. When using either finite length observation histories or
recurrent functions, the same value function-based methods and policy gradient
methods are employed with their respective tradeoffs in partially observable
domains.

We are interested in developing methods that combine the best of both value
function-based methods and policy gradient methods for partial observable
domains. That is, can we develop methods that are sample efficient but are
also robust to partial observation spaces?

Our contribution is a new model-free deep reinforcement learning algorithm
based on the principle of regret minimization which does not require access to
a Markovian state. Our method learns a policy by estimating an advantage-like
function which approximates a quantity called the counterfactual regret.
Counterfactual regret is central to the family of counterfactual regret
minimization (CFR) (Zinkevich et al., 2007) algorithms for solving incomplete
information games. Hence we call our algorithm “advantage-based regret
minimization” (ARM).

We evaluate our approach on three partially observable visual reinforcement
learning tasks: first-person 3D navigation in Doom and Minecraft (Kempka et
al., 2016; Johnson et al., 2016), avoiding partially observed objects in Doom,
and playing Pong with partial observation perturbations (Bellemare et al.,
2013). In our experiments, we find that our method is more robust and offers
substantial improvement over prior methods on partially observable tasks.

##  2 Related Work

Deep reinforcement learning algorithms have been demonstrated to achieve
excellent results on a range of complex tasks, including playing games (Mnih
et al., 2015; Oh et al., 2016) and continuous control (Schulman et al., 2015;
Lillicrap et al., 2016; Levine et al., 2016). Prior deep reinforcement
learning algorithms either learn state or state-action value functions (Mnih
et al., 2013), learn policies using policy gradients (Schulman et al., 2015),
or perform a combination of the two using actor-critic architectures (Mnih et
al., 2016). Policy gradient methods typically do not need to assume a
Markovian state, but tend to suffer from poor sample complexity, due to their
inability to use off-policy data. Methods based on learning Q-functions can
use replay buffers to include off-policy data, accelerating learning
(Lillicrap et al., 2016). However, learning Q-functions with Bellman error
minimization typically requires a Markovian state space. When learning from
partial observations such as images, the inputs might not be Markovian. Mnih
et al. (2013) introduced the concatenation of short observation sequences.
Prior methods (Hausknecht & Stone, 2017; Oh et al., 2016; Mnih et al., 2016;
Heess et al., 2015) have proposed to mitigate this issue by learning recurrent
critics and Q-functions, that depend on entire histories of observations. The
recurrent deterministic policy gradient (Heess et al., 2015) for partially
observable control uses a similar DDPG-style estimator as used in ARM (see
Section 3.3). However, all of these changes increase the size of the input
space, increase variance, or make the optimization problem more complex. Our
method instead learns cumulative advantage functions that depend only on the
current observation, but can still handle non-Markovian problems.

The form of our advantage function update resembles positive temporal
difference methods (Peng et al., 2016; van Hasselt & Wiering, 2007).
Additionally, our update rule for a modified cumulative Q-function resembles
the average Q-function (Anschel et al., 2017) used for variance reduction in
Q-learning. In both cases, the theoretical foundations of our method are based
on cumulative regret minimization, and the motivation is substantively
different. Previous work by Ross et al. (2011); Ross & Bagnell (2014) has
connected regret minimization to reinforcement learning, imitation learning,
and structured prediction, although not with counterfactual regret
minimization. Regression regret matching (Waugh et al., 2015) is based on a
closely related idea, which is to directly approximate the regret with a
linear regression model, however the use of a linear model is limited in
representation compared to deep function approximation.

Finally, regret and value functions both typically take the form of
expectations in reinforcement learning. An alternative view of value functions
in RL is through the lens of value distributions (Bellemare et al., 2017). A
connection between regret and distributional RL could lead to very interesting
future work.

##  3 Advantage-based Regret Minimization

In this section, we provide some background on counterfactual regret
minimization, describe ARM in detail, and give some intuition for why ARM
works.

###  3.1 Counterfactual Regret Minimization (CFR)

First, we give a reinforcement learning-centric exposition of counterfactual
regret minimization (CFR) (Zinkevich et al., 2007; Bowling et al., 2015).

The CFR model for partial observation is as follows. Let $\mathcal{S}$ be the
state space. Let $\mathcal{I}$ be the space of _information sets_ : an
information set $I\in\mathcal{I}$ is a set of states $s\in I$, where
$s\in\mathcal{S}$, such that only the information set $I$ is directly
observable, and the individual states contained in $I$ are hidden. An
information set $I$ is therefore a kind of _aggregate state_.

In CFR, an extensive-form game is repeatedly played between $N$ players,
indexed by $i$. We consider an iterative learning setting, where at the $t$-th
learning iteration, the $i$-th player follows a fixed policy $\pi_{t}^{i}$,
choosing actions $a\in\mathcal{A}$ conditioned on information sets
$I\in\mathcal{I}$ according to their policy $\pi_{t}^{i}(a|I)$. Let
$\sigma_{t}$ denotes the players’ joint policy (their strategy profile). For
any strategy profile $\sigma$, the $i$-th player has an expected value for
playing the game, $J^{i}(\sigma)$. Let $\sigma_{t}^{-i}$ represent the joint
policy of all players except the $i$-th player; similarly, let the tuple
$(\pi_{t}^{i},\sigma_{t}^{-i})$ be the product of the $i$-th player’s policy
$\pi_{t}^{i}$ and the other players’ joint policy $\sigma_{t}^{-i}$.

The $i$-th player’s _overall regret_ after $T$ learning iterations is defined:

$\displaystyle(R_{T}^{i})^{\text{(overall)}}$
$\displaystyle=\max_{\pi_{*}^{i}}\sum_{t=1}^{T}J^{i}(\pi_{*}^{i},\sigma_{t}^{-i})-J^{i}(\pi_{t}^{i},\sigma_{t}^{-i}).$
(1)

What is the interpretation of the overall regret? It is essentially how much
better the $i$-th player could have done, had it always followed an optimal
policy in hindsight instead of the actual sequence of policies $\pi_{t}^{i}$
it executed. Intuitively, the difference
$J^{i}(\pi_{*}^{i},\sigma_{t}^{-i})-J^{i}(\pi_{t}^{i},\sigma_{t})$ is the
suboptimality of $\pi_{t}^{i}$ compared to $\pi_{*}^{i}$, and the sum of the
suboptimalities over learning iterations yields the area inside the learning
curve. In other words, a smaller overall regret implies better sample
efficiency.

Let $Q_{\sigma_{t}}^{i}(I,a)$ be the _counterfactual value_ of the $i$-th
player, where the $i$-th player is assumed to reach $I$ and always chooses the
action $a$ in the aggregate state $I$, and otherwise follows the policy
$\pi_{t}^{i}$, while all other players follow the strategy profile
$\sigma_{t}^{-i}$. Similarly, let the expected counterfactual value be
calculated as
$V_{\sigma_{t}}^{i}(I)=\sum_{a\in\mathcal{A}}\pi_{t}^{i}(a|I)Q_{\sigma_{t}}^{i}(I,a)$.
Let $(R_{T}^{i})^{\text{(CF)}}(I,a)$ be the _counterfactual regret_ of the
$i$-th player, which is the sum of the advantage-like quantities
$Q_{\sigma_{t}}^{i}(I,a)-V_{\sigma_{t}}^{i}(I)$ after $T$ learning iterations:

$\displaystyle(R_{T}^{i})^{\text{(CF)}}(I,a)$
$\displaystyle=\sum_{t=1}^{T}Q_{\sigma_{t}}^{i}(I,a)-V_{\sigma_{t}}^{i}(I).$
(2)

Similarly, the _immediate counterfactual regret_ can be obtained from the
counterfactual regret by maximization over the player’s action space:

$\displaystyle(R_{T}^{i})^{\text{(immCF)}}(I)$
$\displaystyle=\max_{a\in\mathcal{A}}\sum_{t=1}^{T}Q_{\sigma_{t}}^{i}(I,a)-V_{\sigma_{t}}^{i}(I).$
(3)

The immediate counterfactual regret (Equation (3)) possesses a similar
interpretation to the overall regret (Equation (1)), except that the immediate
counterfactual regret and its constituent terms are additionally functions of
the aggregate state $I$.

Suppose that one were to briefly consider each aggregate state $I$ as a
separate, independent subproblem. By naively treating the counterfactual
regret $(R_{T}^{i})^{\text{(CF)}}(I,a)$ for each $I$ as analogous to regret in
an online learning setting, then at each learning iteration one may simply
plug the counterfactual regret into a regret matching policy update (Hart &
Mas-Colell, 2000):

$\displaystyle(\pi_{t+1}^{i})^{\text{RM}}(a|I)$
$\displaystyle=\frac{\max(0,(R_{t}^{i})^{\text{(CF)}}(I,a))}{\sum_{a^{\prime}\in\mathcal{A}}\max(0,(R_{t}^{i})^{\text{(CF)}}(I,a^{\prime}))}.$
(4)

In the online learning setting, the regret matching policy achieves regret
that increases with rate $O(\sqrt{T})$ in the number of iterations $T$ (Cesa-
Bianchi & Lugosi, 2003; Gordon, 2007); we can then say that the regret
matching policy is _regret minimizing_.

It turns out that updating players’ policies in the extensive game setting by
iteratively minimizing the immediate counterfactual regrets according to
Equation (4) will also minimize the overall regret
$(R_{T}^{i})^{\text{(overall)}}$ with upper bound
$O(|\mathcal{I}|\sqrt{|\mathcal{A}|T})$. The overall regret’s $O(\sqrt{T})$
dependence on the number of iterations $T$ is not impacted by the structure of
the information set space $\mathcal{I}$, which is why CFR can be said to be
robust to a certain kind of partial observability. This result forms the basis
of the counterfactual regret minimization algorithm and was proved by
Zinkevich et al. (2007).

Since we are interested in the application of CFR to reinforcement learning,
we can write down “1-player” versions of the components above: the
counterfactual value, reinterpreted as a _stationary_ state-action value
function $Q_{\pi|I\mapsto a}(I,a)$, where the action $a$ is always chosen in
the aggregate state $I$, and the policy $\pi$ is otherwise followed (Bellemare
et al., 2016); the counterfactual regret, including its recursive definition:

$\displaystyle R_{T}^{\text{(CF)}}(I,a)$
$\displaystyle=\sum_{t=1}^{T}Q_{\pi_{t}|I\mapsto a}(I,a)-V_{\pi_{t}|I}(I)$ (5)
$\displaystyle=R_{T-1}^{\text{(CF)}}(I,a)+Q_{\pi_{T}|I\mapsto
a}(I,a)-V_{\pi_{T}|I}(I)$ (6)

where $V_{\pi_{t}|I}(I)=\sum_{a\in\mathcal{A}}\pi_{t}(a|I)Q_{\pi_{t}|I\mapsto
a}(I,a)$; and the regret matching policy update:

$\displaystyle\pi_{t+1}^{\text{RM}}(a|I)$
$\displaystyle=\frac{\max(0,R_{t}^{\text{(CF)}}(I,a))}{\sum_{a^{\prime}\in\mathcal{A}}\max(0,R_{t}^{\text{(CF)}}(I,a^{\prime}))}.$
(7)

###  3.2 CFR+

CFR+ (Tammelin, 2014) consists of a modification to CFR, in which instead of
calculating the full counterfactual regret as in Equation (6), instead the
counterfactual regret is recursively positively clipped:

$\displaystyle R_{T}^{\text{(CF+)}}(I,a)$ (8)
$\displaystyle=[R_{T-1}^{\text{(CF+)}}(I,a)]_{+}+Q_{\pi_{T}|I\mapsto
a}(I,a)-V_{\pi_{T}|I}(I)$

where $[x]_{+}=\max(0,x)$ is the positive clipping operator. Comparing
Equation (6) with Equation (8), the only difference in CFR+ is that the
previous iteration’s quantity is positively clipped in the recursion. This
simple change turns out to yield a large practical improvement in the
performance of the algorithm (Bowling et al., 2015). One intuition for why the
positive clipping of CFR+ can improve upon CFR is that because
$[R_{T-1}^{\text{(CF+)}}]_{+}$ is nonnegative, it provides a kind of “optimism
under uncertainty,” adding a bonus to some transitions while ignoring others.
The CFR+ update has also been shown to do better than CFR when the best action
in hindsight changes frequently (Tammelin et al., 2015). In the rest of this
work we will solely build upon the CFR+ update.

###  3.3 From CFR and CFR+ to ARM

Recall that CFR and CFR+ model partial observation in extensive games with a
space $\mathcal{I}$ of information sets or aggregate states. Because we are
interested in general observation spaces $\mathcal{O}$ in partially observed
Markov decision processes (MDPs), we naively map CFR and CFR+ onto MDPs and
replace $\mathcal{I}$ with $\mathcal{O}$. It is known that Markov or
stochastic games can be converted to extensive form (Littman, 1994; Sandholm &
Singh, 2012; Kroer & Sandholm, 2014), and an MDP is a 1-player Markov game.
Because we are also interested in high dimensional observations such as
images, we estimate a counterfactual regret function approximation (Waugh et
al., 2015) parameterized as a neural network.

The exact form of the counterfactual regret (either Equation (6) or Equation
(8)), after translating aggregate states $I$ to observations $o$, utilizes a
stationary action-value function $Q_{\pi|o\mapsto a}(o,a)$. It is unclear how
to learn a truly stationary action-value function, although Bellemare et al.
(2016) propose a family of consistent Bellman operators for learning locally
stationary action-value functions. We posit that the approximation
$Q_{\pi|o\mapsto a}(o,a)\approx Q_{\pi}(o,a)$, where $Q_{\pi}(o,a)$ is the
usual action-value function, is acceptable when observations are rarely seen
more than once in a typical trajectory.

The above series of approximations finally yields a learnable function using
deep reinforcement learning; this function is a “clipped cumulative advantage
function”:

$\displaystyle A^{+}_{T}(o,a)$
$\displaystyle=\max(0,A^{+}_{T-1}(o,a))+A_{\pi_{T}}(o,a)$ (9)

where $A_{\pi}(o,a)$ is the usual advantage function. Advantage-based regret
minimization (ARM) is then the resulting batch-mode deep RL algorithm that
updates the policy to the regret matching distribution on the cumulative
clipped advantage function:

$\displaystyle\pi_{t+1}(a|o)$
$\displaystyle=\frac{\max(0,A^{+}_{t}(o,a))}{\sum_{a^{\prime}\in\mathcal{A}}\max(0,A^{+}_{t}(o,a^{\prime}))}.$
(10)

At the $t$-th batch iteration of ARM, a batch of data is collected by sampling
trajectories using the current policy $\pi_{t}$, followed by two processing
steps: (a) fit $A^{+}_{t}$ using Equation (9), then (b) set the next
iteration’s policy $\pi_{t+1}$ using Equation (10).

Below, we will use the subscript $k$ to refer to a timestep within a
trajectory, while the subscript $t$ refers to the batch iteration. To
implement Equation (9) with deep function approximation, we define two value
function approximations, $V_{\pi_{t}}(o_{k};\theta_{t})$ and
$Q^{+}_{t}(o_{k},a_{k};\omega_{t})$, as well as a target value function
$V^{\prime}(o_{k};\varphi)$, where $\theta_{t}$, $\omega_{t}$, and $\varphi$
are the learnable parameters. The cumulative clipped advantage function is
represented as
$A^{+}_{t}(o_{k},a_{k})=Q^{+}_{t}(o_{k},a_{k};\omega_{t})-V_{\pi_{t}}(o_{k};\theta_{t})$.
Within each sampling iteration, the value functions are fitted using
stochastic gradient descent by sampling minibatches and performing gradient
steps. In practice, we use Adam to perform the optimization (Kingma & Ba,
2015). The state-value function $V_{\pi_{t}}(o_{k};\theta_{t})$ is fit using
$n$-step returns with a moving target value function
$V^{\prime}(o_{k+n};\varphi)$, essentially using the estimator of the deep
deterministic policy gradient (DDPG) (Lillicrap et al., 2016). In the same
minibatch, $Q^{+}_{t}(o_{k},a_{k};\theta_{t})$ is fit to a similar loss, but
with an additional target reward bonus that incorporates the previous
iteration’s cumulative clipped advantage, $\max(0,A^{+}_{t-1}(o_{k},a_{k}))$.
The regression targets $v_{k}$ and $q_{k}^{+}$ are defined in terms of the
$n$-step returns
$g_{k}^{n}=\sum_{k^{\prime}=k}^{k+n-1}\gamma^{k^{\prime}-k}r_{k^{\prime}}+\gamma^{n}V^{\prime}(o_{k+n};\varphi)$:

$\displaystyle v_{k}$ $\displaystyle\triangleq g_{k}^{n}$ (11) $\displaystyle
q_{k}$ $\displaystyle\triangleq r_{k}+\gamma g_{k+1}^{n-1}$ (12)
$\displaystyle\phi_{k}$ $\displaystyle\triangleq
Q^{+}_{t-1}(o_{k},a_{k};\omega_{t-1})-V_{\pi_{t-1}}(o_{k};\theta_{t-1})$ (13)
$\displaystyle q_{k}^{+}$ $\displaystyle\triangleq\max(0,\phi_{k})+q_{k}.$
(14)

Altogether, each minibatch step of the optimization subproblem consists of the
following three parameter updates:

$\displaystyle\theta_{t}^{(\ell+1)}$
$\displaystyle\leftarrow\theta_{t}^{(\ell)}-\frac{\alpha}{2}\nabla_{\theta_{t}^{(\ell)}}(V_{\pi_{t}}(o_{k};\theta_{t}^{(\ell)})-v_{k})^{2}$
(15) $\displaystyle\omega_{t}^{(\ell+1)}$
$\displaystyle\leftarrow\omega_{t}^{(\ell)}-\frac{\alpha}{2}\nabla_{\omega_{t}^{(\ell)}}(Q^{+}_{t}(o_{k},a_{k};\omega_{t}^{(\ell)})-q_{k}^{+})^{2}$
(16) $\displaystyle\varphi^{(\ell+1)}$
$\displaystyle\leftarrow\varphi^{(\ell)}+\tau(\theta_{t}^{(\ell+1)}-\varphi^{(\ell)}).$
(17)

The advantage-based regret minimization algorithm is summarized in Algorithm
1.

We note again that we use a biased value function estimator, whereas only the
full returns are guaranteed to be unbiased in non-Markovian settings. In the
high-dimensional domains we evaluated on, the most practical choice of deep
advantage or value function approximation is based on biased but lower
variance estimation, such as the $n$-step returns we use in practice (Schulman
et al., 2016; Gu et al., 2017). We also note that ARM is essentially CFR with
different design choices to facilitate function approximation. CFR is proven
to converge in domains with non-Markovian information set spaces when using
tabular representations, suggesting that our use of biased advantage
estimation does not fundamentally preclude the applicability or effectiveness
of ARM on non-Markovian domains.

Algorithm 1 Advantage-based regret minimization (ARM).

initialize $\pi_{1}\leftarrow\text{uniform}$,
$\theta_{0},\omega_{0}\leftarrow\text{arbitrary}$

for $t$ in $1,\ldots$ do

collect batch of trajectory data $\mathcal{D}_{t}\sim\pi_{t}$

initialize $\theta_{t}\leftarrow\theta_{t-1}$,
$\omega_{t}\leftarrow\omega_{t-1}$, $\varphi\leftarrow\theta_{t-1}$

for $\ell$ in $0,\ldots$ do

sample transitions:

$(o_{k},a_{k},r_{k},o_{k+1})\sim\mathcal{D}_{t}$

$\delta_{k}\leftarrow 1-\mathbb{I}[o_{k}~{}\text{is terminal}]$

calculate $n$-step returns:

$g_{k}^{n}\leftarrow\sum_{k^{\prime}=k}^{k+n-1}\gamma^{k^{\prime}-k}r_{k^{\prime}}+\gamma^{n}\delta_{k+n}V^{\prime}(o_{k+n};\varphi)$

calculate target values:

if $t=1$ then

$\phi_{k}\leftarrow 0$

else

$\phi_{k}\leftarrow
Q^{+}_{{t-1}}(o_{k},a_{k};\omega_{t-1})-V_{\pi_{t-1}}(o_{k};\theta_{t-1})$

end if

$v(o_{k})\leftarrow g_{k}^{n}$

$q^{+}(o_{k},a_{k})\leftarrow\max(0,\phi_{k})+r_{k}+\gamma g_{k+1}^{n-1}$

update $\theta_{t}$ (Equation (15))

update $\omega_{t}$ (Equation (16))

update $\varphi$ (Equation (17))

end for

set
$\pi_{t+1}(a|o)\propto\max(0,Q^{+}_{t}(o,a;\omega_{t})-V_{\pi_{t}}(o;\theta_{t}))$

end for

###  3.4 ARM vs. Existing Policy Gradient Methods

We note that the fundamental operation in CFR-like algorithms, including ARM,
is exemplified by the counterfactual regret update in Equation (6) which
superficially looks quite similar to a policy gradient-style update: the
update is in the direction of a Q-value minus a baseline. However, we can take
the analogy between ARM and policy gradient methods further and show that ARM
represents an inherently different update compared to existing policy gradient
methods.

Recent work has shown that policy gradient methods and Q-learning methods are
connected via maximum entropy RL (O’Donoghue et al., 2017; Haarnoja et al.,
2017; Nachum et al., 2017; Schulman et al., 2017). One such perspective is
from the soft policy iteration framework for batch-mode reinforcement learning
(Haarnoja et al., 2018), where at the $t$-th batch iteration the updated
policy is obtained by minimizing the average KL-divergence between the
parametric policy class $\Pi$ and a target policy $f_{t}$. Below is the soft
policy iteration update, where the subscript $t$ refers to the batch
iteration:

$\displaystyle\pi_{t+1}=\arg\min_{\pi\in\Pi}\mathbb{E}_{o\sim\rho_{t}}[D_{\text{KL}}(\pi(\cdot|o)\|f_{t}(\cdot|o))]$
$\displaystyle=\arg\min_{\pi\in\Pi}\mathbb{E}_{o\sim\rho_{t},a\sim\pi(\cdot|o)}[\log(\pi(a|o))-\log(f_{t}(a|o))].$
(18)

Using the connection between policy gradient methods and Q-learning, we define
the policy gradient target policy as a Boltzmann or softmax distribution on
the entropy regularized advantage function $A^{\text{$\beta$-soft}}$:

$\displaystyle f_{t}^{\text{PG}}(a|o)$
$\displaystyle\triangleq\frac{\exp(\beta
A_{t}^{\text{$\beta$-soft}}(o,a))}{\sum_{a^{\prime}\in\mathcal{A}}\exp(\beta
A_{t}^{\text{$\beta$-soft}}(o,a^{\prime}))}.$ (19)

Now, parameterizing the policy $\pi$ in terms of an explicit parameter
$\theta$, we obtain the expression for the existing policy gradient update,
where $b(o)$ is a baseline function:

$\displaystyle\Delta\theta^{\text{PG}}$
$\displaystyle\propto\mathbb{E}_{o\sim\rho_{t},a\sim\pi(\cdot|o;\theta)}\Big{[}\nabla_{\theta}\log(\pi(o|a;\theta))\cdot$
(20)
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\big{(}-(1/\beta)\log(\pi(o|a;\theta))$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}+A_{t}^{\text{$\beta$-soft}}(o,a)-b(o)\big{)}\Big{]}.$

The non-entropy-regularized policy gradient arises in the limit
$\beta\to\infty$, at which point $(1/\beta)$ vanishes.

Note that an alternative choice of target policy $f_{t}$ will lead to a
different kind of policy gradient update. A policy gradient algorithm based on
ARM instead proposes a target policy based on the regret matching
distribution:

$\displaystyle f_{t}^{\text{ARM}}(a|o)$
$\displaystyle\triangleq\frac{\max(0,A_{t}^{+}(o,a))}{\sum_{a^{\prime}\in\mathcal{A}}\max(0,A_{t}^{+}(o,a^{\prime}))}.$
(21)

Similarly, we can express the ARM-like policy gradient update, where again
$b(o)$ is a baseline:

$\displaystyle\Delta\theta^{\text{ARM}}$
$\displaystyle=\mathbb{E}_{o\sim\rho_{t},a\sim\pi(\cdot|o;\theta)}\Big{[}\nabla_{\theta}\log(\pi(o|a;\theta))\cdot$
(22)
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\big{(}-\log(\pi(o|a;\theta))$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}+\log(\max(0,A_{t}^{+}(o,a)))-b(o)\big{)}\Big{]}.$

Comparing Equations (20) and (22), we see that the ARM-like policy gradient
(Equation (22)) has a logarithmic dependence on the clipped advantage-like
function $\max(0,A^{+})$, whereas the existing policy gradient (Equation (20))
is only linearly dependent on the advantage function
$A^{\text{$\beta$-soft}}$. This difference in logarithmic vs. linear
dependence is responsible for a large part of the inherent distinction of ARM
from existing policy gradient methods. In particular, the logarithmic
dependence in an ARM-like update may be less sensitive to advantage
overestimation compared to existing policy gradient methods, perhaps serving a
similar purpose to the double Q-learning estimator (van Hasselt et al., 2016)
or consistent Bellman operators (Bellemare et al., 2016).

We also see that for the existing policy gradient (Equation (20)), the
$-(1/\beta)\log(\pi(a|o;\theta))$ term, which arises from the policy entropy,
is vanishing for large $\beta$. On the other hand, for the ARM-like policy
gradient (Equation (22)), there is no similar vanishing effect on the
equivalent policy entropy term, suggesting that ARM may perform a kind of
entropy regularization by default.

In practice we cannot implement an ARM-like policy gradient exactly as in
Equation (22), because the positive clipping $\max(0,A^{+})$ can yield
$\log(0)$. However we believe this is not an intrinsic obstacle and leave the
question of how to implement an ARM-like policy gradient to future work.

###  3.5 Comparing ARM with Other Methods in Partially Observable Domains

The regret matching policy which is fundamental to ARM can be interpreted as a
more nuanced form of exploration compared to the epsilon-greedy policy used
with Q-learning. In partially observable domains, the optimal policy may
generally be stochastic (Jaakkola et al., 1994). So $\epsilon$-greedy policies
which put a substantial probability mass on $\arg\max_{a}Q(o,a)$, e.g. by
setting $\epsilon=0.01$, can be suboptimal, especially compared to more
general distributions on discrete actions, such as ARM’s regret matching
policy. The softmax policy typically learned by policy gradient methods is
also quite general, but can still put too much probability mass on one action
without compensation by an explicit entropy bonus as done in maximum entropy
reinforcement learning.

Policy gradient methods have an overall regret bound of $R_{T}\leq
B^{2}/\eta+\eta G^{2}T$ derived from stochastic gradient descent, where $B$ is
an upper bound on the policy parameter $\ell^{2}$-norm, $G^{2}$ is an upper
bound on the second moments of the stochastic gradients, and $\eta$ is the
learning rate (Dick, 2015), Assuming an optimal learning rate
$\eta=B/(G\sqrt{T})$, the policy gradient regret bound becomes $R_{T}\leq
2BG\sqrt{T}$. CFR has an overall regret bound of
$R_{T}\leq\Delta|\mathcal{I}|\sqrt{|\mathcal{A}|T}$, where $\Delta$ is the
positive range of returns, and $|\mathcal{I}|$ and $|\mathcal{A}|$ are
cardinalities of the information set space and action space, respectively
(Zinkevich et al., 2007). Both regret bounds have $O(\sqrt{T})$ dependence on
$T$. As mentioned earlier, policy gradient methods can also be robust to
partial observation, but unlike in the case of CFR, the dependence of the
policy gradient regret bound on an optimal learning rate and on gradient
variance may affect policy gradient convergence in the presence of estimation
error. On the other hand, the constants in the CFR regret bound are constant
properties of the environment.

For Q-learning per se, we are not aware of any known regret bound. Szepesvári
proved that an upper bound on the convergence rate of Q-learning
(specifically, the convergence rate of $\|Q_{T}(s,a)-Q^{*}(s,a)\|_{\infty}$),
assuming a fixed exploration strategy, depends on an exploration condition
number, which is the ratio of minimum to maximum state-action occupation
frequencies (Szepesvári, 1998), and which describes how “balanced” the
exploration strategy is. If partial observability leads to imbalanced
exploration due to confounding of states from perceptual aliasing (McCallum,
1997), then Q-learning should be negatively affected in convergence and
possibly in absolute performance.

##  4 Experiments

Because we hypothesize that ARM should perform well in partially observable
domains, we conduct our experiments on visual tasks that naturally provide
partial observations of state. Our evaluations use feedforward convnets with
frame history inputs; our hyperparameters are listed in Section A1 of the
Supplementary Material. We are interested in comparing ARM with other
advantage-structured methods, primarily: (a) double deep Q-learning with
dueling network streams (van Hasselt et al., 2016; Wang et al., 2016), which
possesses an advantage-like parameterization of its Q-function and assumes
Markovian observations; and (b) TRPO (Schulman et al., 2015, 2016), which
estimates an empirical advantage using a baseline state-value function and can
handle non-Markovian observations.

###  4.1 Learning First-person 3D Navigation

We first evaluate ARM on the task of learning first-person navigation in 3D
maze-like tasks from two domains: ViZDoom (Kempka et al., 2016) based on the
game Doom, and Malmö (Johnson et al., 2016) based on the game Minecraft. Doom
and Minecraft both feature an egocentric viewpoint, 3D perspective, and rich
visual textures. We expect that both domains exhibit a substantial degree of
partial observability since only the immediate field-of-view of the
environment is observable by the agent due to first-person perspective.

In Doom MyWayHome, the agent is randomly placed in one of several rooms
connected in a maze-like arrangement, and the agent must reach an item that
has a fixed visual appearance and is in a fixed location before time runs out.
For Minecraft, we adopt the teacher-student curriculum learning task of
Matiisen et al. (2017), consisting of 5 consecutive “levels” that successively
increase the difficulty of completing the simple task of reaching a gold
block: the first level (“L1”) consists of a single room; the intermediate
levels (“L2”–“L4”) consist of a corridor with lava-bridge and wall-gap
obstacles; and the final level (“L5”) consists of a $2\times 2$ arrangement of
rooms randomly separated by lava-bridge or wall-gap obstacles. Examples of the
MyWayHome and the Minecraft levels are shown in Figure 1.

Our results on Doom and Minecraft are in Figures 2 and 3. Unlike previous
evaluations which augmented raw pixel observations with extra information
about the game state, e.g. elapsed time ticks or remaining health (Kempka et
al., 2016; Dosovitskiy & Koltun, 2017), in our evaluation we forced all
networks to learn using only visual input. Despite this restriction, ARM is
still able to quickly learn policies with minimal tuning of hyperparameters
and to reach close to the maximum achievable score in under 1 million
simulator steps, which is quite sample efficient. On MyWayHome, we observed
that ARM generally learned a well-performing policy more quickly than other
methods. Additionally, we found that ARM is able to take advantage of an off-
policy replay memory when learning on MyWayHome by storing the trajectories of
previous sampling batches and applying an importance sampling correction to
the $n$-step return estimator; please see Section A2 in the Supplementary
Material.

We performed our Minecraft experiments using fixed curriculum learning
schedules to evaluate the sample efficiency of different algorithms: the agent
is initially placed in the first level (“L1”), and the agent is advanced to
the next level whenever a preselected number of simulator steps have elapsed,
until the agent reaches the last level (“L5”). We found that ARM and dueling
double DQN both were able to learn on an aggressive “fast” schedule of only
62500 simulator steps between levels. TRPO required a “slow” schedule of 93750
simulator steps between levels to reliably learn. ARM was able to consistently
learn a well performing policy on all of the levels, whereas double DQN
learned more slowly on some of the intermediate levels. ARM also more
consistently reached a high score on the final, most difficult level (“L5”).

|  |
---|---|---
Figure 1:  Screenshots from (left) Doom MyWayHome, (middle) Minecraft level 1,
and (right) Minecraft level 4.  Figure 2:  Evaluation on the Doom MyWayHome
task.

Figure 3:  Evaluation on a Minecraft curriculum learning task. The simulator
step counts at which each level begins are labeled and demarcated with dashed
vertical lines.

###  4.2 Learning with Partially Observed Objects

Previously in Section 3.5, we argued that the convergence results for CFR
suggest that reducing the size of the observation space could improve the
convergence of CFR compared to methods based on policy gradients or
Q-learning. We would expect that by controlling the degree of partial
observability in a fixed task, one could expect the relative sample efficiency
or performance of ARM to improve compared to other methods.

Whereas the navigation tasks in Section 4.1 only dealt with first-person
motion in static 3D environments, tasks that add other objects which may move
and are not always visible to the agent intuitively ought to be less
observable. To test the effect of the degree of partial observability on fixed
tasks with objects, we conduct experiments with at least two variants of each
task: one experiment is based on the unmodified task, but the other
experiments occlude or mask essential pixels in observed frames to raise the
difficulty of identifying relevant objects.

We evaluate ARM and other methods on two tasks with objects: Doom Corridor via
ViZDoom, and Atari Pong via the Arcade Learning Environment (Bellemare et al.,
2013). In Corridor, the agent is placed in a narrow 3D hallway and must avoid
getting killed by any of several shooting monsters scattered along the route
while trying to reach the end of the hallway. In Pong, the agent controls a
paddle and must hit a moving ball past the computer opponent’s paddle on the
other side of the screen.

In our implementation of Corridor, which we call “Corridor+,” we restrict the
action space of the agent to only be able to turn left or right and to move to
one side. Because the agent spawns facing the end of the hallway, the agent
has to learn to first turn to its side to orient itself sideways before
moving, while also trying to avoid getting hit from behind by monsters in
close proximity. To induce partial observability in Corridor, we mask out a
large square region in the center of the frame buffer. An example of this
occlusion is shown in Figure 4. Because the only way for the agent to progress
toward the end of the hallway is by moving sideways, the monsters that are
closest to the agent, and hence the most dangerous, will appear near the
center of the agent’s field-of-view. So the center pixels are the most natural
ones to occlude in Corridor+.

For Pong, we choose a rectangular area in the middle of the frame between the
two players’ paddles, then we set all pixels in the rectangular area to the
background color. An illustration of the occlusion is shown in Figure 4. When
the ball enters the occluded region, it completely disappears from view so its
state cannot be reconstructed using a limited frame history. Intuitively, the
agent needs to learn to anticipate the trajectory of the ball in the absence
of visual cues of the ball’s position and velocity.

It is also known that for Atari games in general, with only 4 observed frames
as input, it is possible to predict hundreds of frames into the future on some
games using only a feedforward dynamics model (Oh et al., 2015). By default,
all of our networks receive as input a frame history of length 4. This
suggests that limiting the frame history length in Pong is another effective
perturbation for reducing observability. When the frame history length is
limited to one, then reconstructing the velocity of moving objects in Pong
becomes more difficult (Hausknecht & Stone, 2017).

Our results on Corridor+ are shown in Figure 5. Among all our experiments, it
is on Corridor+ that TRPO performs the best compared to all other methods. One
distinguishing feature of TRPO is its empirical full return estimator, which
is unbiased on non-Markovian observations, but which can have greater variance
than the $n$-step return estimator used in deep Q-learning and ARM. On
Corridor+, there appears to be a benefit to using the unbiased full returns
over the biased $n$-step returns, which speaks to the non-Markovian character
of the Corridor+ task. It is also evident on Corridor+ that the performance of
deep Q-learning suffers when the observability is reduced by occlusion, and
that by comparison ARM is relatively unaffected, despite both methods using
biased $n$-step returns with the same value of $n$ ($n=5$). This suggests that
even when ARM is handicapped by the bias of its return estimator, ARM is
intrinsically more robust to the non-Markovian observations that arise from
partial observability. One possible direction to improve ARM is through
alternative return estimators (Schulman et al., 2016; Wang et al., 2017).

Our results on Pong are shown in Figure 6. The convergence of ARM on all three
variants of Pong suggests that ARM is not affected much by partial observation
in this domain. As expected, when observability is reduced in the limited
frame history and occlusion experiments, deep Q-learning performs worse and
converges more slowly than ARM. TRPO is generally less sample efficient than
either ARM or DQN, although like ARM it seems to be resilient to the partial
observation perturbations.

|  |  |
---|---|---|---
Figure 4:  Screenshots from Atari Pong (left two) and Doom Corridor+ (right
two), unmodified and with occlusion.

Figure 5:  Results on Doom Corridor+: (left) unmodified, (right) with
occlusion.

Figure 6:  Results on Atari Pong: (left) unmodified, (middle) with limited
frame history, (right) with occlusion.

##  5 Discussion

In this paper, we presented a novel deep reinforcement learning algorithm
based on counterfactual regret minimization (CFR). We call our method
advantage-based regret minimization (ARM). Similarly to prior methods that
learn state or state-action value functions, our method learns a cumulative
clipped advantage function of observation and action. However, in contrast to
these prior methods, ARM is well suited to partially observed or non-Markovian
environments, making it an appealing choice in a number of difficult domains.
When compared to baseline methods, including deep Q-learning and TRPO, on
partially observable tasks such as first-person navigation in Doom and
Minecraft and interacting with partially observed objects in Doom and Pong,
ARM is robust to the degree of partial observability and can achieve
substantially better sample efficiency and performance. This illustrates the
value of ARM for partially observable problems. In future work, we plan to
further explore applications of ARM to more complex tasks, including
continuous action spaces.

## Acknowledgements

We thank Tambet Matiisen for providing the Malmö curriculum learning tasks,
Deepak Pathak for help with ViZDoom experiments, and Tuomas Haarnoja, Richard
Li, and Haoran Tang for helpful discussions. This work was partially supported
by Berkeley DeepDrive, ADEPT Lab industrial sponsors and affiliates Intel,
Google, Siemens, and SK Hynix, DARPA Award Number HR0011-12-2-0016, and ASPIRE
Lab industrial sponsors and affiliates Intel, Google, HPE, Huawei, LGE, Nokia,
NVIDIA, Oracle, and Samsung.

## References

  * Anschel et al. (2017) Anschel, O., Baram, N., and Shimkin, N.  Averaged-DQN: Variance Reduction and Stabilization for Deep Reinforcement Learning.  In _Proceedings of the 34th International Conference on Machine Learning_ , pp. 176–185, 2017.
  * Bellemare et al. (2013) Bellemare, M. G., Naddaf, Y., Veness, J., and Bowling, M.  The Arcade Learning Environment: An evaluation platform for general agents.  _Journal of Artificial Intelligence Research_ , 47:253–279, 2013.
  * Bellemare et al. (2016) Bellemare, M. G., Ostrovski, G., Guez, A., Thomas, P. S., and Munos, R.  Increasing the Action Gap: New Operators for Reinforcement Learning.  In _AAAI Conference on Artificial Intelligence_ , 2016.
  * Bellemare et al. (2017) Bellemare, M. G., Dabney, W., and Munos, R.  A Distributional Perspective on Reinforcement Learning.  In _Proceedings of the 34th International Conference on Machine Learning_ , 2017.
  * Bowling et al. (2015) Bowling, M., Burch, N., Johanson, M., and Tammelin, O.  Heads-up limit hold’em poker is solved.  _Science_ , 347(6218):145–149, 2015.
  * Cesa-Bianchi & Lugosi (2003) Cesa-Bianchi, N. and Lugosi, G.  Potential-Based Algorithms in On-Line Prediction and Game Theory.  _Machine Learning_ , 51(3):239–261, 2003.
  * Dick (2015) Dick, T.  Policy Gradient Reinforcement Learning Without Regret.  Master’s thesis, University of Alberta, 2015.
  * Dosovitskiy & Koltun (2017) Dosovitskiy, A. and Koltun, V.  Learning to Act by Predicting the Future.  In _International Conference on Learning Representations_ , 2017.
  * Gordon (2007) Gordon, G. J.  No-regret Algorithms for Online Convex Programs.  In _Advances in Neural Information Processing Systems_ , 2007.
  * Gu et al. (2017) Gu, S., Lillicrap, T., Ghahramani, Z., Turner, R. E., Schölkopf, B., and Levine, S.  Interpolated Policy Gradient: Merging On-Policy and Off-Policy Gradient Estimation for Deep Reinforcement Learning.  _arXiv preprint arXiv:1706.00387_ , 2017.
  * Haarnoja et al. (2017) Haarnoja, T., Tang, H., Abbeel, P., and Levine, S.  Reinforcement Learning with Deep Energy-Based Policies.  In _International Conference on Machine Learning_ , 2017.
  * Haarnoja et al. (2018) Haarnoja, T., Zhou, A., Abbeel, P., and Levine, S.  Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor.  In _Proceedings of the 35th International Conference on Machine Learning_ , 2018.
  * Hart & Mas-Colell (2000) Hart, S. and Mas-Colell, A.  A Simple Adaptive Procedure Leading to Correlated Equilibrium.  _Econometrica_ , 68(5):1127–1150, 2000.
  * Hausknecht & Stone (2017) Hausknecht, M. and Stone, P.  Deep Recurrent Q-Learning for Partially Observable MDPs.  _arXiv preprint arXiv:1507.06527_ , 2017.
  * Heess et al. (2015) Heess, N., Hunt, J. J., Lillicrap, T. P., and Silver, D.  Memory-based control with recurrent neural networks.  _arXiv preprint arXiv:1512.04455_ , 2015.
  * Jaakkola et al. (1994) Jaakkola, T., Singh, S. P., and Jordan, M. I.  Reinforcement Learning Algorithm for Partially Observable Markov Decision Problems.  In _Advances in Neural Information Processing Systems_ , 1994.
  * Johnson et al. (2016) Johnson, M., Hofmann, K., Hutton, T., and Bignell, D.  The Malmo Platform for Artificial Intelligence Experimentation.  In _Proceedings of the 25th International Joint Conference on Artificial Intelligence_ , 2016.
  * Kempka et al. (2016) Kempka, M., Wydmuch, M., Runc, G., Toczek, J., and Jaśkowski, W.  ViZDoom: A Doom-based AI Research Platform for Visual Reinforcement Learning.  _arXiv preprint arXiv:1605.02097_ , 2016.
  * Kingma & Ba (2015) Kingma, D. P. and Ba, J. L.  Adam: A Method for Stochastic Optimization.  In _International Conference on Learning Representations_ , 2015.
  * Kroer & Sandholm (2014) Kroer, C. and Sandholm, T.  Extensive-Form Game Abstraction With Bounds.  In _Proceedings of the 15th ACM Conference on Economics and Computation_ , 2014.
  * Levine et al. (2016) Levine, S., Finn, C., Darrell, T., and Abbeel, P.  End-to-end training of deep visuomotor policies.  _The Journal of Machine Learning Research_ , 17(1):1334–1373, 2016.
  * Lillicrap et al. (2016) Lillicrap, T. P., Hunt, J. J., Pritzel, A., Heess, N., Erez, T., Tassa, Y., Silver, D., and Wierstra, D.  Continuous control with deep reinforcement learning.  In _International Conference on Learning Representations_ , 2016.
  * Littman (1994) Littman, M. L.  Markov games as a framework for multi-agent reinforcement learning.  In _Proceedings of the 11th International Conference on Machine Learning_ , pp. 157–163, 1994.
  * Matiisen et al. (2017) Matiisen, T., Oliver, A., Cohen, T., and Schulman, J.  Teacher-Student Curriculum Learning.  _arXiv preprint arXiv:1707.00183_ , 2017.
  * McCallum (1997) McCallum, A. K.  Efficient Exploration in Reinforcement Learning with Hidden State.  In _AAAI Fall Symposium on Model-directed Autonomous Systems_ , 1997\.
  * Mnih et al. (2013) Mnih, V., Kavukcuoglu, K., Silver, D., Graves, A., Antonoglou, I., Wierstra, D., and Riedmiller, M.  Playing Atari with Deep Reinforcement Learning.  _arXiv preprint arXiv:1312.5602_ , 2013.
  * Mnih et al. (2015) Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidjeland, A. K., Ostrovski, G., et al.  Human-level control through deep reinforcement learning.  _Nature_ , 518(7540):529–533, 2015.
  * Mnih et al. (2016) Mnih, V., Badia, A. P., Mirza, M., Graves, A., Lillicrap, T., Harley, T., Silver, D., and Kavukcuoglu, K.  Asynchronous methods for deep reinforcement learning.  In _International Conference on Machine Learning_ , pp. 1928–1937, 2016.
  * Nachum et al. (2017) Nachum, O., Norouzi, M., Xu, K., and Schuurmans, D.  Bridging the Gap Between Value and Policy Based Reinforcement Learning.  In _Advances in Neural Information Processing Systems_ , 2017.
  * O’Donoghue et al. (2017) O’Donoghue, B., Munos, R., Kavukcuoglu, K., and Mnih, V.  Combining policy gradient and Q-learning.  _arXiv preprint arXiv:1611.01626_ , 2017.
  * Oh et al. (2015) Oh, J., Guo, X., Lee, H., Lewis, R. L., and Singh, S.  Action-Conditional Video Prediction using Deep Networks in Atari Games.  In _Advances in Neural Information Processing Systems_ , 2015.
  * Oh et al. (2016) Oh, J., Chockalingam, V., Singh, S., and Lee, H.  Control of memory, active perception, and action in minecraft.  In _Proceedings of The 33rd International Conference on Machine Learning_ , pp. 2790–2799, 2016.
  * Peng et al. (2016) Peng, X. B., Berseth, G., and van de Penne, M.  Terrain-Adaptive Locomotion Skills Using Deep Reinforcement Learning.  _ACM Transactions on Graphics_ , 35(4):81, 2016\.
  * Ross & Bagnell (2014) Ross, S. and Bagnell, J. A.  Reinforcement and Imitation Learning via Interactive No-Regret Learning.  _arXiv preprint arXiv:1406.5979_ , 2014.
  * Ross et al. (2011) Ross, S., Gordon, G. J., and Bagnell, J. A.  A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning.  In _Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics_ , pp. 627–635, 2011.
  * Sandholm & Singh (2012) Sandholm, T. and Singh, S.  Lossy Stochastic Game Abstraction with Bounds.  In _Proceedings of the 13th ACM Conference on Economics and Computation_ , 2012.
  * Schulman et al. (2015) Schulman, J., Levine, S., Abbeel, P., Jordan, M., and Moritz, P.  Trust region policy optimization.  In _Proceedings of the 32nd International Conference on Machine Learning (ICML-15)_ , pp. 1889–1897, 2015.
  * Schulman et al. (2016) Schulman, J., Moritz, P., Levine, S., Jordan, M. I., and Abbeel, P.  High-Dimensional Continuous Control Using Generalized Advantage Estimation.  _arXiv preprint arXiv:1506.02438_ , 2016.
  * Schulman et al. (2017) Schulman, J., Chen, X., and Abbeel, P.  Equivalence Between Policy Gradients and Soft Q-Learning.  _arXiv preprint arXiv:1704.06440_ , 2017.
  * Szepesvári (1998) Szepesvári, C.  The Asymptotic Convergence-Rate of Q-learning.  In _Advances in Neural Information Processing Systems_ , 1998.
  * Tammelin (2014) Tammelin, O.  Solving Large Imperfect Information Games Using CFR+.  _arXiv preprint arXiv:1407.5042_ , 2014.
  * Tammelin et al. (2015) Tammelin, O., Burch, N., Johanson, M., and Bowling, M.  Solving Heads-up Limit Texas Hold’em.  In _Proceedings of the 24th International Joint Conference on Artificial Intelligence_ , 2015.
  * van Hasselt & Wiering (2007) van Hasselt, H. and Wiering, M. A.  Reinforcement Learning in Continuous Action Spaces.  In _Proceedings of the 2007 IEEE Symposium on Approximate Dynamic Programming and Reinforcement Learning_ , pp. 272–279, 2007.
  * van Hasselt et al. (2016) van Hasselt, H., Guez, A., and Silver, D.  Deep Reinforcement Learning and Double Q-Learning.  In _AAAI Conference on Artificial Intelligence_ , 2016.
  * Wang et al. (2016) Wang, Z., Schaul, T., Hessel, M., van Hasselt, H., Lanctot, M., and de Freitas, N.  Dueling Network Architectures for Deep Reinforcement Learning.  In _Proceedings of the 33rd International Conference on Machine Learning_ , pp. 1995–2003, 2016.
  * Wang et al. (2017) Wang, Z., Bapst, V., Heess, N., Mnih, V., Munos, R., Kavukcuoglu, K., and de Freitas, N.  Sample Efficient Actor-Critic with Experience Replay.  _arXiv preprint arXiv:1611.01224_ , 2017.
  * Waugh et al. (2015) Waugh, K., Morrill, D., Bagnell, J. A., and Bowling, M.  Solving Games with Functional Regret Estimation.  In _Workshops at the Twenty-Ninth AAAI Conference on Artificial Intelligence_ , 2015.  Supplementary material in _arXiv preprint arXiv:1411.7974_.
  * Zinkevich et al. (2007) Zinkevich, M., Johanson, M., Bowling, M. H., and Piccione, C.  Regret Minimization in Games with Incomplete Information.  In _Advances in Neural Information Processing Systems_ , 2007.

##  A1 Experimental Details

For each experiment, we performed 5 trials for each method (some TRPO
experiments on Pong are for 3 trials).

###  A1.1 Hyperparameters

Our hyperparameter choices for each method are listed below. For all methods
using Adam, we roughly tuned the learning rate to find the largest that
consistently converged in unmodified variants of tasks.

####  A1.1.1 ARM

Please see Tables 1 and 2 for hyperparameters used with ARM. Note that our
choice of ARM hyperparameters yields an equivalent number of minibatch
gradient steps per sample as used by deep Q-learning, i.e. 1 Adam minibatch
gradient step per 4 simulator steps; c.f. Table 4 for the deep Q-learning
hyperparameters. We kept hyperparameters (other than the learning rate and the
number of steps $n$) constant across tasks.

Table 1:  Hyperparameters for ARM.
Hyperparameter | Atari | Doom | Minecraft
---|---|---|---
Adam learning rate | $1\mathrm{e}^{-4}$ | $1\mathrm{e}^{-5}$ | $1\mathrm{e}^{-5}$
Adam minibatch size | $32$ | $32$ | $32$
batch size | $12500$ | $12500$ | $12500$
gradient steps | $3000$ | $3000$ | $3000$
moving average ($\tau$) | $0.01$ | $0.01$ | $0.01$
$n$-steps | $1$ | $5$ | $5$
Table 2:  Hyperparameters for off-policy ARM.
Hyperparameter | Doom
---|---
Adam learning rate | $1\mathrm{e}^{-5}$
Adam minibatch size | $32$
batch size | $1563$
gradient steps | $400$
importance weight clip | $1$
moving average ($\tau$) | $0.01$
$n$-steps | $5$
replay memory max | $25000$

####  A1.1.2 A2C

Please see Table 3 for hyperparameters used with A2C. We found that increasing
the number of steps $n$ used to calculate the $n$-step returns was most
important for getting A2C/A3C to converge on Doom MyWayHome.

Table 3:  Hyperparameters for A2C.
Hyperparameter | Doom
---|---
Adam learning rate | $1\mathrm{e}^{-4}$
Adam minibatch size | $640$
entropy bonus ($\beta$) | $0.01$
gradient clip | $0.5$
$n$-steps | $40$
num. workers | $16$

####  A1.1.3 DQN

Please see Table 4 for hyperparameters used with deep Q-learning. Dueling
double DQN uses the tuned hyperparameters (van Hasselt et al., 2016; Wang et
al., 2016). In particular, we found that dueling double DQN generally
performed better and was more stable when learning on Atari with the tuned
learning rate $6.25\times 10^{-5}\approx 6\times 10^{-5}$ from Wang et al.
(2016), compared to the slightly larger learning rate of $1\times 10^{-4}$
used by ARM.

Table 4:  Hyperparameters for dueling + double deep Q-learning.
Hyperparameter | Atari | Doom | Minecraft
---|---|---|---
Adam learning rate | $6\mathrm{e}^{-5}$ | $1\mathrm{e}^{-5}$ | $1\mathrm{e}^{-5}$
Adam minibatch size | $32$ | $32$ | $32$
final exploration | $0.01$ | $0.01$ | $0.01$
gradient clip | $10$ | — | —
$n$-steps | $1$ | $5$ | $5$
replay memory init | $50000$ | $50000$ | $12500$
replay memory max | $10^{6}$ | $240000$ | $62500$
sim steps/grad step | $4$ | $4$ | $4$
target update steps | $30000$ | $30000$ | $12500$

####  A1.1.4 TRPO

Please see Table 5 for hyperparameters used with TRPO. We generally used the
defaults, such as the KL step size of $0.01$ which we found to be a good
default. Decreasing the batch size improved sample efficiency on Doom and
Minecraft without adversely affecting the performance of the learned policies.

Table 5:  Hyperparameters for TRPO.
Hyperparameter | Atari | Doom | Minecraft
---|---|---|---
batch size | $100000$ | $12500$ | $6250$
CG dampening | $0.1$ | $0.1$ | $0.1$
CG iterations | $10$ | $10$ | $10$
KL step size | $0.01$ | $0.01$ | $0.01$

###  A1.2 Environment and Task Details

Our task-specific implementation details are described below.

####  A1.2.1 Atari

For the occluded variant of Pong, we set the middle region of the $160\times
210$ screen with $x,y$ pixel coordinates $[55\ldots 105),[34\ldots 194)$ to
the RGB color $(144,72,17)$. The image of occluded Pong in Figure 4 from the
main text has a slightly darker occluded region for emphasis.

We use the preprocessing and convolutional network model of Mnih et al.
(2013). Specifically, we view every 4th emulator frame, convert the raw frames
to grayscale, and perform downsampling to generate a single observed frame.
The input observation of the convnet is a concatenation of the most recent
frames (either 4 frames or 1 frame). The convnet consists of an $8\times 8$
convolution with stride 4 and 16 filters followed by ReLU, a $4\times 4$
convolution with stride 2 and 32 filters followed by ReLU, a linear map with
256 units followed by ReLU, and a linear map with $|\mathcal{A}|$ units where
$|\mathcal{A}|$ is the action space cardinality ($|\mathcal{A}|=6$ for Pong).

####  A1.2.2 Doom

Our modified environment “Doom Corridor+” is very closely derived from the
default “Doom Corridor” environment in ViZDoom. We primarily make two
modifications: (a) first, we restrict the action space to the three keys
$\\{MoveRight,TurnLeft,TurnRight\\}$, for a total of $2^{3}=8$ discrete
actions; (b) second, we set the difficulty (“Doom skill”) to the maximum of 5.

For the occluded variant of Corridor+, we set the middle region of the
$160\times 120$ screen with $x,y$ pixel coordinates $[30\ldots 130),[10\ldots
110)$ to black, i.e. $(0,0,0)$.

For Corridor+, we scaled rewards by a factor of $0.01$. We did not scale
rewards for MyWayHome.

The Doom screen was rendered at a resolution of $160\times 120$ and downsized
to $84\times 84$. Only every 4th frame was rendered, and the input observation
to the convnet is a concatenation of the last 4 rendered RGB frames for a
total of 12 input channels. The convnet contains 3 convolutions with 32
filters each: the first is size $8\times 8$ with stride 4, the second is size
$4\times 4$ with stride 2, and the third is size $3\times 3$ with stride 1.
The final convolution is followed by a linear map with 1024 units. A second
linear map yields the output. Hidden activations are gated by ReLUs.

####  A1.2.3 Minecraft

Our Minecraft tasks are based on the tasks introduced by Matiisen et al.
(2017), with a few differences. Instead of using a continuous action space, we
used a discrete action space with 4 move and turn actions. To aid learning on
the last level (“L5”), we removed the reward penalty upon episode timeout and
we increased the timeout on “L5” from 45 seconds to 75 seconds due to the
larger size of the environment. We scaled rewards for all levels by $0.001$.

We use the same convolutional network architecture for Minecraft as we use for
ViZDoom. The Minecraft screen was rendered at a resolution of $320\times 240$
and downsized to $84\times 84$. Only every 5th frame was rendered, and the
input observation of the convnet is a concatenation of the last 4 rendered RGB
frames for a total of 12 input channels.

##  A2 Off-policy ARM via Importance Sampling

Our current approach to running ARM with off-policy data consists of applying
an importance sampling correction directly to the $n$-step returns. Given the
behavior policy $\mu$ under which the data was sampled, the current policy
$\pi_{t}$ under which we want to perform estimation, and an importance
sampling weight clip $c$ for variance reduction, the corrected $n$-step return
we use is:

$\displaystyle g_{k}^{n}(\mu\|\pi_{t})$
$\displaystyle=\sum_{k^{\prime}=k}^{k+n-1}\gamma^{k^{\prime}-k}\left(\prod_{\ell=k}^{k^{\prime}}w_{\mu\|\pi_{t}}(a_{\ell}|o_{\ell})\right)r_{k^{\prime}}$
(23) $\displaystyle~{}~{}~{}~{}~{}+\gamma^{n}V^{\prime}(o_{k+n};\varphi)$

where the truncated importance weight $w_{\mu\|\pi_{t}}(a|o)$ is defined:

$\displaystyle w_{\mu\|\pi_{t}}(a|o)$
$\displaystyle=\min\left(c,\frac{\pi_{t}(a|o)}{\mu(a|o)}\right).$ (24)

Note that the target value function $V^{\prime}(o_{k+n};\varphi)$ does not
require an importance sampling correction because $V^{\prime}$ already
approximates the on-policy value function $V_{\pi_{t}}(o_{k+n};\theta_{t})$.
Our choice of $c=1$ in our experiments was inspired by Wang et al., (2017). We
found that $c=1$ worked well but note other choices for $c$ may also be
reasonable.

When applying our importance sampling correction, we preserve all details of
the ARM algorithm except for two aspects: the transition sampling strategy (a
finite memory of previous batches are cached and uniformly sampled) and the
regression targets for learning the value functions. Specifically, the
regression targets $v_{k}$ and $q_{k}^{+}$ (Equations (11)–(14) in the main
text) are modified to the following:

$\displaystyle v_{k}$ $\displaystyle=g_{k}^{n}(\mu\|\pi_{t})$ (25)
$\displaystyle q_{k}$
$\displaystyle=(1-w_{\mu\|\pi_{t}}(a_{k}|o_{k}))r_{k}+g_{k}^{n}(\mu\|\pi_{t})$
(26) $\displaystyle\phi_{k}$
$\displaystyle=Q^{+}_{t-1}(o_{k},a_{k};\omega_{t-1})-V_{\pi_{t-1}}(o_{k};\theta_{t-1})$
(27) $\displaystyle q^{+}_{k}$ $\displaystyle=\max(0,\phi_{k})+q_{k}.$ (28)

##  A3 Additional Experiments

###  A3.1 Recurrence in Doom MyWayHome

We evaluated the effect of recurrent policy and value function estimation in
the maze-like MyWayHome scenario of ViZDoom. For the recurrent policy and
value function, we replaced the first fully connected operation with an LSTM
featuring an equivalent number of hidden units (1024). We found that
recurrence has a small positive effect on the convergence of A2C, but was much
less significant than the choice of algorithm; compare Figure 2 in the main
text with Figure 7 below.

Figure 7:  Comparing A2C with a feedforward convolutional network (blue) and a
recurrent convolutional-LSTM network (orange) on the ViZDoom scenario
MyWayHome.

###  A3.2 Atari 2600 games

Although our primary interest is in partially observable reinforcement
learning domains, we also want to check that ARM works in nearly fully
observable and Markovian environments, such as Atari 2600 games. We consider
two baselines: double deep Q-learning, and double deep fitted Q-iteration
which is a batch counterpart to double DQN. We find that double deep
Q-learning is a strong baseline for learning to play Atari games, although ARM
still successfully learns interesting policies. One major benefit of
Q-learning-based methods is the ability to utilize a large off-policy replay
memory. Our results on a suite of Atari games are in Figure 8.

Figure 8:  Comparing double deep Q-learning (orange), double deep fitted
Q-iteration (red), and ARM (blue) on a suite of seven Atari games from the
Arcade Learning Environment.


# MineObserver 2.0: A Deep Learning & In-Game Framework for Assessing Natural
Language Descriptions of Minecraft Imagery

Jay Mahajan, Samuel Hum, Jack Henhapl, Diya Yunus, Matthew Gadbury, Emi Brown,
Jeff Ginger, H. Chad Lane

###### Abstract

MineObserver 2.0 is an AI framework that uses Computer Vision and Natural
Language Processing for assessing the accuracy of learner-generated
descriptions of Minecraft images that include some scientifically relevant
content. The system automatically assesses the accuracy of participant
observations, written in natural language, made during science learning
activities that take place in Minecraft. We demonstrate our system working in
real-time and describe a teacher support dashboard to showcase observations,
both of which advance our previous work. We present the results of a study
showing that MineObserver 2.0 improves over its predecessor both in perceived
accuracy of the system’s generated descriptions as well as in usefulness of
the system’s feedback. In future work we intend improve system-generated
descriptions, give teachers more control and upgrade the system to perform
continuous learning to more effectively and rapidly respond to novel
observations made by learners.

## Introduction

There are few challenges more important to educators and parents than helping
children come to a better understanding of the world. Central to this goal is
to promote their abilities to articulate what they see and observe about the
natural world and to explore those observations through the lens of science
(Arias and Davis 2016).

In previous work we presented a prototype AI system called MineObserver
(Mahajan et al. 2022) that sought to assess learner observations in the
popular game Minecraft. In this paper, we report on several significant
updates to that system (MineObserver 2.0) that improve it along several
critical aspects. In the context of video game research, MineObserver 2.0 is a
framework that uses machine learning image captioning and a Minecraft plugin
that assists users in Minecraft environments designed to promote science
learning. The system seeks to both assess learner observations of these worlds
and deliver feedback intended to improve their ability to make accurate and
productive observations primarily in the context of Astronomy learning.

## Background

### Minecraft

Minecraft is an exceptionally popular game. Since its release in 2009, the
user base has exploded with over 140M players and 241M logins per month and
consistently ranks in the top 5 most popular games for
children.111https://news.xbox.com/en-us/wp-
content/uploads/sites/2/2021/04/Minecraft-Franchise-Fact-Sheet_April-2021.pdf
It spans many platforms and its players have a range of interests, ages and
experience. It is referred to as a ”sandbox” game because it can be used in
several different modes and contexts and often participants come up with their
own challenges and meanings when playing alone or with others. The Java
Edition of the game has an enormous community following and is very
modifiable, which makes it an ideal candidate to create more complex teaching
and learning simulations like the one exhibited in this paper.

### Minecraft as a Learning Environment

As an extremely modifiable game, Minecraft can be used as a learning
environment. Several studies (Lane and Yi 2017; Bos et al. 2014; Lim 2020; de
Andrade, Poplin, and Sousa de Sena 2020) have used Minecraft to teach a
variety of topics including (but not limited to) basic mathematics, civic
engagement, and even music. Nearly each study found that Minecraft’s
flexibility allowed the students to be more creative and have more freedom
than a traditional classroom setting. A key component of learning environments
is the ability to collaborate with other learners. This is easily achieved
since Minecraft can be played with multiple users which can encourages
collaboration including collecting difficult achievements, building large
structures, and even exploring worlds that are treacherous together. Each of
these tasks can be done alone, but would require a great deal of time and
effort on one single player. Moreover, modifying the game via a Java plugin,
programmers can create new tools or achievements that require multiple users
in order to achieve a rich collaborative experience.

### Minecraft for Science Learning

The research shared in this paper is part of the NSF-funded project WHIMC
(What-If Hypothetical Implementations in Minecraft). WHIMC investigates the
use of Minecraft as an educational tool for science learning, with an emphasis
on Astronomy content that engages children and promotes interest in STEM (Lane
et al. 2022). WHIMC is implemented as a Minecraft (Java Edition) server
consisting of a space station hub and a collection of worlds to visit. On
these worlds, learners interactively explore the scientific consequences of
alternative versions of Earth via “what if?” questions (e.g., “What if the
earth had no moon?”) as well as feasible representations of several known
exoplanets. It is hoped that such experiences will act as triggers of interest
(Yi, Gadbury, and Lane 2021), which are required in order for interest to be
sustained over time (Renninger and Hidi 2015).

A key component of the project is to analyze how learners interact with the
environment and assess their engagement with and understanding of science
content. Players are invited to participate in exploration challenges where
they can learn about and measure pertinent science characteristics of
simulated worlds (such as temperature and radiation). In addition to
measurements, learners also make written observations about things they think
are noteworthy or interesting in some way, which appear as floating text. For
example, without a moon and its gravitational pull, the Earth’s rotation would
be much faster than it is now. This would cause fierce winds on the surface of
Earth. To withstand the force of such wind trees would need to be shorter,
wider, and stronger (Comins 1993). An example of an observation for this
phenomena is shown in Figure 1. We note that the combination of a screenshot
and a description forms the basis for our data set described in the next
section.

Figure 1: A sample observation of tree variation on a version of Earth with no
moon.

WHIMC provides a framework for making observations like a scientist. In
particular, based on our prior work to assess learner observations (Yi,
Gadbury, and Lane 2020), we identified five key categories for observations:

  1. 1.

Factual: observations are comprised of nouns without any elaboration.

  2. 2.

Descriptive: observations related to color, temperature, quantity, and other
physical attributes such as weight or size.

  3. 3.

Comparative: observations comparing one natural phenomenon to another.

  4. 4.

Analogies: observations comparing natural phenomena with another similar
structure or object (an advanced form of comparative).

  5. 5.

Inferences: observations where a hypothesis or explanation is proposed (the
most advanced form, rare for middle school students to do spontaneously).

Observations are also visible to all players on the server, so they might
prompt other learners to take notice. In addition, the WHIMC server captures
additional data, including player coordinate and directional facing data to
better understand what students were observing at the time.

### MineObserver

Previously, MineObserver introduced a AI-method to assess Minecraft imagery
from students in a Minecraft world. This method used Image Captioning and
cosine similarity to check if a student was correctly observing the intended
structure, building, etc. This initial effort was not implemented in-game and
instead acted like an outside grader. Moreover, the feedback system lacked
depth and did not adequately focus on improving learner observation skills.
Our current work improves on this method by directly interacting with the
student while improving all aspects of the framework (captioning, feedback,
etc.) to give the students a better learning experience and more directly
support their emerging skills in making scientific observations.

## MineObserver 2.0 AI Framework

Our AI framework can be broken down into three major parts: the Photographer,
the AI Architecture, and the Visualizer. The sequence is as follows. The
student makes a visual observation which consists of the student’s in-game
coordinates and a caption. Next, the Photographer teleports to the student’s
coordinates and takes a screenshot of the student’s POV. The Photographer then
sends the student’s POV and caption to our AI Architecture. The AI
Architecture uses the student’s POV and caption to predict how accurate the
observation is and gives feedback to the student. The AI Architecture also
sends the feedback and a score to the Visualizer. At the end, the student
receives feedback via the Photographer and the Visualizer displays the
observation made by the student with the AI’s feedback. The feedback aims to
help an individual student’s observation skills while the Visualizer acts an
intervention tool for the teacher to further guide a class of students to
highlight, focus, and understand which observations are strong, weak, average,
etc. Our entire framework can visually depicted in Figure 2

Figure 2: MineObserver 2.0’s AI Framework. Note that the Photographer and AI
Architecture are hosted on AWS EC2 instances for ease of access.

### Photographer

To enable real-time captioning and feedback in game, we introduce the
Photographer. The Photographer is a Minecraft client (a separate account with
an independent login) that teleports to a learner’s coordinates to capture
their point of view via screenshot. This client is tied via unique ID to a
spigot-plugin that sends data to our AI Architecture and displays the AI’s
result to the student in real time, right after they make the observation. To
make the Photographer readily available, we host our entire client on an AWS
EC2 instance. The student will never physically see the Photographer client in
action as it is always in invisible ”spectator” mode. This way we avoid
interrupting the student’s gameplay when making observations.

### AI Architecture

The AI Architecture consists of three parts: a Image Caption model, a RoBERTa
(Liu et al. 2019) model and the feedback system. From the Photographer, the
Image Caption takes the student’s POV, we pass the image to a Image Caption
model to generate a caption. In this case, the generated caption acts like an
expert observer which can be used to compare against the student’s
observation. Using the student’s and generated captions, we pass them through
the RoBERTa model. At the end, we use the data from the RoBERTa model to
generate feedback and pass the results to the teacher and student. To make the
AI Architecture available, we create a REST API and host it on an AWS EC2
instance. We summarize our AI Architecture in Figure 3.

Figure 3: MineObserver 2.0’s AI Architecture.

### Image Captioning Model

Since Minecraft primarily focuses on building and crafting structures, we
decided to use an Image Captioning model that can focus on parts of the
images. This led us to use an attention based model similar to (Xu et al.
2015). In our case, we used a Convolutional Neural Network (CNN) and a Long
Short Term Memory (LSTM) (Hochreiter and Schmidhuber 1997) with visual
attention. While the approach mentioned above uses a pre-trained CNN on
ImageNet (Deng et al. 2009), we found that this resulted in poor performance
thus we train both the CNN and LSTM.

During testing time, instead of using a greedy approach to decode our image,
we use beam search with $k=3$ possible candidates. This allows us to consider
the entire sequence rather than individual words when generating our captions.

### RoBERTa model

As stated previously, students engaging with the WHIMC platform make
observations while exploring different Minecraft maps. These observations are
important: they simultaneously reflect how deeply engaged the learner is in
the experience and reveal (to an extent) the level of understanding they have
for the science concepts. Our agent must assess the content of these
observations to guide their pedagogical actions.

To accomplish this, We utilize the RoBERTa model fine-tuned on the Semantic
Textual Similarity benchmark (STSb) and Natural Language Inference (NLI)
dataset to encode the image caption generated by the CNN and the student’s
observation. Facebook’s RoBERTa model has been shown to outperform BERT on the
General Language Understanding Evaluation (GLUE) benchmark, Stanford Question
Answer Dataset (SQuAD), and ReAding Comprehension from Examinations (RACE)
dataset (Liu et al. 2019). In addition, fine-tuning the model with STSb and
NLI has been shown to improve sentence encodings for common text similarity
tasks (Reimers and Gurevych 2019).

For our purposes, we use RoBERTa to perform cosine similarity between the
student’s caption and the generated caption which produces a score that allows
us to understand how closely related the two captions are. We also use this
model to perform keyword detection which will be later used in our feedback
system.

### Feedback system

Using the RoBERTa model, we request $\lambda$ keywords from the generated
caption and collect the cosine similarity score. We set a threshold for the
cosine similarity $\gamma$ to decide how similar the captions are. If the
score is at or above the threshold, then we return the following phase:
”Excellent work, you noticed the {keywords} here!”. And similarly if the score
is less than the threshold, then we return the following phase: ”Try again!
Did you notice the {keywords}?”. In our case, the keywords acts as primary
features in the image to focus on. That way, when the student does not meet
the threshold score, our system can guide the student to focus on those parts
of the observation and try again. At the end, we send the results back to the
student (via Photographer) and the teacher (via Visualizer).

### Visualizer

The Visualizer is a tool for the instructors to guide students when they make
observations. Every time an observation is made, the Visualizer instantly
picks it up and displays the student’s username, observation, AI-generated
observation, and feedback. At the end of the session, the instructor can
export all of the data to a folder that contains the images and a CSV of all
text data. The goal of the visualizer is to support instructors in initiating
discussions with students on observations made and evaluate students’
performance and engagement with relevant scientific content. Figure 4 shows
how our Visualizer looks.

Figure 4: Main UI of the Visualizer. Each of students’ observations are listed
with their POV, the observation made, the AI’s generated caption, and the
feedback from the AI’s system. At the end, an instructors can export the
results to get a folder of images and a CSV of all the Visualizer data

## Experiments

### Dataset

Since there was no existing dataset of Minecraft images paired with their
observations, we had to create our own. We collected hundreds of images of
size $1920$ x $1080$ across the WHIMC server and the internet, captioned them
using Amazon Mechanical Turk or manually, and labeled the type of observation
(e.g Descriptive, Comparative, or Inferential). To target our intended users
of this system, we had children from ages 8-14 also caption a set of images
and filter out any captions that were either off-topic or extraneous. An
important aspect of the WHIMC project is to broaden participation. As such, a
substantial amount of our observation training data came from summer camps
with participants that are from historically underrepresented groups in STEM.
Eventually, our dataset consisted of over two thousand unique datapoints which
was sufficient to capture main points of interest in the WHIMC server.

### Pre-processing & Data Augmentation

Before we load images into our model, we center-cropped them to $1024$ x
$1024$ and resized them to be $256$ x $256$ since most of the intended
locations of interest lied in the center of the image. When training the
model, we augmented our data by adding random horizontal flips and randomly
rotated our image by -5 to 5 degrees.

### Training

The only part of our framework that is required to be trained is our Image
Caption model. We coded our model using PyTorch (Paszke et al. 2019). For our
CNN, we decided to use ResNet (He et al. 2015) as our main choice as it is
performed against other CNN models such AlexNet (Krizhevsky, Sutskever, and
Hinton 2012) and VGGNet (Simonyan and Zisserman 2014) while being relative
light-weight compared to models such as DenseNet (Huang et al. 2018).

### Implementation

We trained our entire model via backpropagation by using an Adam optimizer
(Kingma and Ba 2014), with a learning rate of 3e-4, and used a cross-entropy
loss function for 150 iterations. We used an Nvidia Tesla T4 GPU to train our
model quickly.

For our purposes, we decided to detect $\lambda=2$ keywords from the generated
caption and let the cosine similarity threshold to $\gamma=0.5$.

## Results

Significance Test | degrees of freedom | p-value | Significant at $\alpha=0.05$
---|---|---|---
Mean student’s rating of AI’s generated caption | 56.806 | 0.03196 | ✓
Mean student’s rating of AI’s feedback | 49.521 | 0.001719 | ✓
Table 1: Summary of 2-Welch t-test for each experiment. In each case, we compare our model against MineObserver. $n=61$ Model | BLEU-1 | BLEU-2 | BLEU-3 | BLEU-4 | METEOR
---|---|---|---|---|---
MineObserver | 0.197 | 0.0294 | 0.0117 | 0 | 0.12165
Ours | 0.2 | 0.033 | 0.0095 | 0.0055 | 0.14647
Table 2: Standard Image Captioning Metrics

### Summer Camps

Our tool was used as an integral component of our summer camps, which took
place from June until August. A total of 73 participants ages 8 to 14 where
ages 8 to 10 made up 40% and ages 11 to 14 made up 60% of the student age
group. Each camp consisted of roughly 15 hours of instructional time focused
on teaching science and astronomy concepts, as well as building in response to
habitation requirements. They visited a variety of ”what-if” simulations of
earth, from ”what if earth had two moons” to exoplanet gas giants like
Gliese-436b. Along the way students learn about science variables like gravity
or atmospheric composition and engage in making scientific observations to
later develop and investigate a hypothesis. Many students struggle to know
what or how to observe and sometimes get distracted or off-task, our system
helps to remedy this. Additional information on our curriculum and approach to
teaching and learning with AI and technology can be found at (redacted URL).

For each camp, we conducted a double blind experiment. Each of the camps
received either our work or the previous work’s framework. Neither did the
students nor the instructors knew which work was running at a camp. To ensure
a fair comparison, we adjusted the prior work to work at run-time rather after
the camp. We conducted this for each of the 6 camps where we explain to the
students what AI is via a video and talk and point out that the tool is there
to help them. Students first used a simple web interface to each contribute 5
practice observations of still images from our simulation worlds to our future
training dataset. They then made a variable amount of observations
individually on their own in-game. We summarize the results in table 1 and in
table 2.

### Accuracy of Generated Captions of Minecraft Images

We first asked students about the AI’s accuracy when generating a caption
(observation) to determine if the attention-based image captioning was a
useful improvement:

How accurate was the AI’s generated observations?

The students rated the AI’s overall accuracy of the generated observations
from 1 (not accurate) to 5 (very accurate).

In this case, a 2-sample mean Welch t-test (Welch 1947) would be appropriate
to compare the students who had our version against the students who had the
previous work (MineObserver). Thus, our null and alternative hypothesis can be
framed as:

$H_{o}:\textit{The mean students' rating of the AI's generated}$

obervations does not differ between our work and the prior  work.

$H_{a}:\textit{The mean students' rating of the AI's generated}$

obervations for our work is greater than the previous work.

If we let $\mu_{R}$ be the mean students’ rating of the AI’s generated
observation, then mathematically we can expresses this as:

$H_{o}:\mu_{Ra}=\mu_{Rb}$ $H_{a}:\mu_{Ra}>\mu_{Rb}$

Where $a$ is our work and $b$ is the previous work.

With a degrees of freedom of 56.806, we receive a t-value of 1.8896 which
corresponds to a p-value of 0.03196. At $\alpha=0.05$, this is statistically
significant thus we reject the null hypothesis and suggest that the student’s
mean rating of the AI’s generated observations for our work is better than the
previous work. This can be seen in table 1 in our second row.

To further prove that our image captioning model was more accurate, we also
computed several pre-existing image captioning metrics. We showcase these in
table 2. In almost of all of the metrics, our work beats the previous work.

### Feedback Accuracy

Similarly, we asked the students to rate the feedback given by the AI’s
feedback system. This would ultimately test if students prefer the keyword
feedback rather than the generic feedback from the previous work. We posed the
following statement to the students:

The feedback from the AI was useful.

The students rated this statement from 1 to 5 where a rating of 1 would
correspond to not useful feedback and a rating of 5 would correspond to very
useful feedback.

In this case, a 2-sample mean Welch t-test would be appropriate to compare the
students who had our version against the students who had previous work. Thus,
our null and alternative hypothesis can be framed as:

$H_{o}:\textit{The mean students' rating of the AI's feedback does }$

not differ between our work and the prior work.

$H_{a}:\textit{The mean students' rating of the AI's feedback for }$

our work is greater than the previous work.

If we let $\mu_{F}$ be the mean students’ rating of the AI’s feedback, then
mathematically we can expresses this as:

$H_{o}:\mu_{Fa}=\mu_{Fb}$ $H_{a}:\mu_{Fa}>\mu_{Fb}$

Where $a$ is our work and $b$ is the previous work.

With a degrees of freedom of 49.521, we receive a t-value of 3.0733 which
corresponds to a p-value of 0.001719. At $\alpha=0.05$, this is statistically
significant thus we reject the null hypothesis and suggest that the student’s
mean rating of the AI’s generated observations for our work is better than the
previous work. This can be seen table 1 in our third row.

## Other Related Results

### In-Game Performance

The experience in game is seamless. A player will make an observation
(depicted in figure 5) and will get feedback about their caption about 20
seconds later. Once the observation is created the Photographer is put to
work. From the student’s point of view, they will not see anything; the
Photographer is invisible.

Figure 5: An observation to be graded by MineObserver 2.0’s AI

Once the feedback has been generated and returned by the Photographer, the
player receives a message in chat with feedback about the player’s caption as
well as a caption generated by the AI. An example of the response can be seen
in figure 6.

Figure 6: An example of feedback from the AI’s feedback system

To make sure that the gameplay felt smooth, we asked the students to rate the
speed of the AI system from 1 to 5 where a rating of 1 would suggest that the
AI was too slow to reply whereas a rating of 5 would suggest that the AI was
very quick. Bar chart (figure 7) shows the overall result of this question.

$1$$2$$3$$4$$5$$5$$10$$15$$20$RatingFrequencyAI’s in-game speed rated by WHIMC
Students Figure 7: Bar Graph of AI’s in-game speed rated by WHIMC Summer Camp
Students.

The student gave a median score of 3. This suggest that the in-game speed was
adequate but can be improved for a better experience. One suggestion to have
more than one Photographer client active to handle the students’ activity.

### Visualizer Results

Qualitative data was collected via short post-session reflection interviews
with five different instructors to assess the effectiveness of using the
visualizer dashboard. The instructors relayed that the visualizer was helpful
in two major ways. First, it was able to help the them more easily identify
which students needed interventions to help stay focused and/or make better
observations. This allowed them to focus more on teaching the content of the
camps rather than try to visually spot or analyze logs to determine which
students were struggling in the middle of session. Second, the instructors
used the visualizer to conduct a post-assessment of each day. If a camp had
too many students to allow an instructor to pay attention to the dashboard in
the moment they could instead leave it on and examine the aggregate visualizer
results afterwards. This enabled them to focus on how the overall class
performance and reflect on how to address gaps in knowledge or skill during
the following camp day. Overall, the instructors unanimously agreed that the
visualizer accomplished its primary goal of identifying which students needed
intervention in the context of making sufficient observations. That said the
interface is still fairly rudimentary and has presents many opportunities for
improvement, including (1) cross-platform compatibility via being able to be
run as a web app, (2) ability to sort or summarize results for a given time
period, (3) the addition of learner profiles to track progress and engagement
over time, which could in turn inform the AI, and (4) identify and highlight
links that may be common trends or collaboration between participants.

## Future Work & Conclusion

There are several ideas we wish to add or improve to MineObserver 2.0. This
includes styling our image caption model, continuous learning, and stronger
feedback.

### Styling our Image Captioning Model

Many generative models, such as StyleGAN (Karras, Laine, and Aila 2018) allow
for generative styles. In our case, we might seek a way to style our image
caption model to style based on the type of observation. This would enhance
our framework by allowing the student or teacher to choose how they should be
graded based on the type of observation.

### Continuous Learning

After an observation is made by a student, our framework stores any relevant
info to the Visualizer where a teacher can take a look and track student
progress. However, since WHIMC is continuously in development, we can use the
data from the Visualizer to re-train our image caption model if generated
captions are not strong enough. This would allow our model to continually
learn as the server grows over time.

### Stronger Feedback

Currently, feedback to the learner is limited, typically only directing
attention to pertinent visual features nearby and general questions. Future
iterations may be able to challenge them with a question to prompt new or
additional observations based on their past interests or behaviors, as well as
additional engagement with the supporting AI agent or teacher.

### Additional Applications

Our tool was developed for the specific context of written observations
attached to in-game visuals but may be able to be adapted for alternative use
scenarios, including other Minecraft learning simulations or game play. Users
could intentionally employ the tool as a kind of note-taking and learner
support system while building or exploring. More broadly the ability to take
screenshots in a semi-automated fashion based on a Minecraft command interrupt
could form the basis of far more complicated pedagogical agents. The plugin
and AI essentially mimics and automates the functionality of the camera tool
and notebook in Minecraft Education Edition, and could potentially be adapted
to create solo-learner self-guided learning experiences. Seeing the great
potential we’ve released our code as open source on Github.

## Acknowledgements

The authors would like to thank the participants and instructors who provided
support for the data collection and fellow researchers on the project for help
with the coding and statistics. This material is based upon work supported by
the National Science Foundation under Grants 1713609 and 1906873.

## References

  * Arias and Davis (2016) Arias, A. M.; and Davis, E. A. 2016.  Making and recording observations.  _Science and Children_ , 53(8): 54–60.
  * Bos et al. (2014) Bos, B.; Wilder, L.; Cook, M.; and O’Donnell, R. 2014.  Learning Mathematics through Minecraft.  _Teaching Children Mathematics_ , 21(1): 56 – 59.
  * Comins (1993) Comins, N. F. 1993.  What if the moon didn’t exist: voyages to earths that might have been.  _New York_.
  * de Andrade, Poplin, and Sousa de Sena (2020) de Andrade, B.; Poplin, A.; and Sousa de Sena, Ã. 2020.  Minecraft as a Tool for Engaging Children in Urban Planning: A Case Study in Tirol Town, Brazil.  _ISPRS International Journal of Geo-Information_ , 9(3): 170.
  * Deng et al. (2009) Deng, J.; Dong, W.; Socher, R.; Li, L.-J.; Li, K.; and Fei-Fei, L. 2009.  ImageNet: A large-scale hierarchical image database.  In _2009 IEEE Conference on Computer Vision and Pattern Recognition_ , 248–255.
  * He et al. (2015) He, K.; Zhang, X.; Ren, S.; and Sunr, J. 2015.  Deep Residual Learning for Image Recognition.  arXiv:1512.0338.
  * Hochreiter and Schmidhuber (1997) Hochreiter, S.; and Schmidhuber, J. 1997.  Long Short-Term Memory.  Neural Computation:1735–1780.
  * Huang et al. (2018) Huang, G.; Liu, Z.; van der Maaten, L.; and Weinberger, K. Q. 2018.  Densely Connected Convolutional Networks.  arXiv:1608.06993.
  * Karras, Laine, and Aila (2018) Karras, T.; Laine, S.; and Aila, T. 2018.  A Style-Based Generator Architecture for Generative Adversarial Networks.
  * Kingma and Ba (2014) Kingma, D. P.; and Ba, J. 2014.  Adam: A Method for Stochastic Optimization.  arXiv:1412.6980.
  * Krizhevsky, Sutskever, and Hinton (2012) Krizhevsky, A.; Sutskever, I.; and Hinton, G. E. 2012.  ImageNet Classification with Deep Convolutional Neural Networks.  NeurIPS:1512.0338.
  * Lane et al. (2022) Lane, H. C.; Gadbury, M.; Ginger, J.; Yi, S.; Comins, N.; Henhapl, J.; and Rivera-Rogers, A. 2022.  Triggering STEM Interest With Minecraft in a Hybrid Summer Camp.  _Technology, Mind, and Behavior_ , 3(4: Winter).  Https://tmb.apaopen.org/pub/5pkfd4sc.
  * Lane and Yi (2017) Lane, H. C.; and Yi, S. 2017.  Chapter 7 - Playing With Virtual Blocks: Minecraft as a Learning Environment for Practice and Research.  In Blumberg, F. C.; and Brooks, P. J., eds., _Cognitive Development in Digital Contexts_ , 145–166. San Diego: Academic Press.  ISBN 978-0-12-809481-5.
  * Lim (2020) Lim, K. 2020.  Redstone Jamminâ€™: Conversational Analysis from a Collaborative Music-Making Activity in Minecraft.  _Journal of Virtual Worlds Research_ , 13.
  * Liu et al. (2019) Liu, Y.; Ott, M.; Goyal, N.; Du, J.; Joshi, M.; Chen, D.; Levy, O.; Lewis, M.; Zettlemoyer, L.; and Stoyanov, V. 2019.  RoBERTa: A Robustly Optimized BERT Pretraining Approach.  arXiv:1907.11692.
  * Mahajan et al. (2022) Mahajan, J.; Hum, S.; Ginger, J.; and Lane, H. C. 2022.  MineObserver: A Deep Learning Framework for Assessing Natural Language Descriptions of Minecraft Imagery.  In _The International FLAIRS Conference Proceedings, 35_. FloridaOJ.
  * Paszke et al. (2019) Paszke, A.; Gross, S.; Massa, F.; Lerer, A.; Bradbury, J.; Chanan, G.; Killeen, T.; Lin, Z.; Gimelshein, N.; Antiga, L.; Desmaison, A.; KÃ¶pf, A.; Yang, E.; DeVito, Z.; Raison, M.; Tejani, A.; Chilamkurthy, S.; Steiner, B.; Fang, L.; Bai, J.; and Chintala, S. 2019.  PyTorch: An Imperative Style, High-Performance Deep Learning Library.
  * Reimers and Gurevych (2019) Reimers, N.; and Gurevych, I. 2019.  Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks.  arXiv:1908.10084.
  * Renninger and Hidi (2015) Renninger, K. A.; and Hidi, S. E. 2015.  _The power of interest for motivation and engagement_.  Routledge.
  * Simonyan and Zisserman (2014) Simonyan, K.; and Zisserman, A. 2014.  Very Deep Convolutional Networks for Large-Scale Image Recognition.
  * Welch (1947) Welch, B. L. 1947.  THE GENERALIZATION OF â€˜STUDENT’Sâ€™ PROBLEM WHEN SEVERAL DIFFERENT POPULATION VARLANCES ARE INVOLVED.  _Biometrika_ , 34(1-2): 28–35.
  * Xu et al. (2015) Xu, K.; Ba, J.; Kiros, R.; Cho, K.; Courville, A.; Salakhutdinov, R.; Zemel, R.; and Bengio, Y. 2015.
  * Yi, Gadbury, and Lane (2020) Yi, S.; Gadbury, M.; and Lane, H. C. 2020.  Coding and analyzing scientific observations from middle school students in Minecraft.
  * Yi, Gadbury, and Lane (2021) Yi, S.; Gadbury, M.; and Lane, H. C. 2021.  Identifying and Coding STEM Interest Triggers in a Summer Camp.  In _Proceedings of the 15th International Conference of the Learning Sciences-ICLS 2021._ International Society of the Learning Sciences.