# Reinforcement Learning with Subspaces
using Free Energy Paradigm

Milad Ghorbani, Reshad Hosseini, Seyed Pooya Shariatpanahi, and Majid Nili
Ahmadabadi The authors are with the School of ECE, College of Engineering,
University of Tehran, Tehran, Iran (email<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>mnili@ut.ac.ir).

###### Abstract

In large-scale problems, standard reinforcement learning algorithms suffer
from slow learning speed. In this paper, we follow the framework of using
subspaces to tackle this problem. We propose a free-energy minimization
framework for selecting the subspaces and integrate the policy of the state-
space into the subspaces. Our proposed free-energy minimization framework
rests upon Thompson sampling policy and behavioral policy of subspaces and the
state-space. It is therefore applicable to a variety of tasks, discrete or
continuous state space, model-free and model-based tasks. Through a set of
experiments, we show that this general framework highly improves the learning
speed. We also provide a convergence proof.

###### Index Terms:

Bounded rationality, information theory, free energy principle, Thompson
sampling, generalization in subspaces, reinforcement learning.

##  I Introduction

Reinforcement learning (RL) is the most important paradigm for interactive
learning where an agent learns through interaction with external environment
[1]. In recent years, RL has been studied in real-world tasks like robotics
[2, 3, 4], recommender system applications [5, 6], and human-in-the-loop
applications [7, 8, 9].

The main problem of RL is that at the beginning of the learning process, the
agent has no knowledge and should try all possible actions in all different
states. Large-scale RL problems with multidimensional state-space suffer from
the curse of dimensionality [10]. The main solution to confront this problem
is generalization. Some generalization methods try to cluster similar states
during learning and obtain an abstraction of the main problem and then solve
the abstract problem.

Thompson sampling (see [11]) is a policy that efficiently balances between
exploration and exploitation [12]. In [13], an efficient approach called TCRL,
has been introduced that uses an idea similar to Thompson sampling for finding
suitable clusters during the learning process.

In [14, 15], some approximation methods for state abstraction have been
introduced. Unlike TCRL, these methods do not guarantee to converge to the
optimal policy. However, they are more suitable for large-scale problems since
they need less exploration.

Finding similar states for making abstraction also needs sufficient
exploration and can suffer from the curse of dimensionality. Some other
methods that partially solve this problem use a particular abstract RL problem
called subspace, which is usually fixed in the beginning [16, 17, 18]. A
subspace is created by applying a transformation on the state space that
reduces the number of features. Agent generalizes its experiences when it uses
a subspace instead of the main space. In some states, this generalization may
hinder the agent from having the optimal policy. This problem of subspace
generalization is called perceptual aliasing (PA). Therefore, a concrete model
that integrates policies from subspaces, and the main space was used in the
literature (see [16, 17, 18]). This concrete model often uses subspaces in
early trials to improve the learning speed and then switches to the main space
as the learning process goes on [18]. This idea is also used in curriculum
learning, where an agent learns in a sequence of subtasks before starting the
main task. This sequence usually is generated automatically [19, 20] or
designed by domain experts [21]. The subtasks are often simpler versions of
the main task and used to increase the speed of learning of the main task
through transfer learning [22]. Recently, curriculum learning methods have
shown promising results in solving complex games such as Backgammon [23], Go
[24], and Starcraft [25]. One of the shortcomings of these methods is that
making an appropriate sequence of subtasks itself needs a significant amount
of time [22]. Therefore, the objective of this paper is to determine the
suitable subspace to learn before learning the main task without using any
prior information about different spaces.

In this paper, we investigate the problem of selecting suitable space and also
integrating the policies of subspaces and the main space, and develop a method
based on free energy minimization. Free energy model is used to model the
behavior of decision-maker when it has some information constraints [26, 27].
Negative free energy can also be seen as a criterion for the reliability of a
decision-making model in a particular state [28]. Subspaces have an inherent
information limit which is introduced as PA. Therefore, we propose a method in
which the agent creates models in the main space and some selected subspaces
and then estimates the uncertainty of these models. Then, it uses free energy
model to amalgamate these informations and obtain a good policy to interact
with the environment. The free energy model is used to tackle with natural PA
of subspaces and also limited accuracy of uncertainty estimations which is
inevitable and can cause considerable inefficiencies.

Our proposed framework for subspace generalization is very general. Previous
works by other members of our group exploited the idea of subspaces in model-
free [16, 17] or model-based [18] settings. In contrast, our method is
implementable in different model-free, model-based, and deep RL settings.
Through several experiments, we compare the performance of our method with
other subspace-based methods. Our method significantly has a better
performance than previous subspace-based methods.

##  II Problem Statement and Assumptions

The agent lives in an unknown Markov decision process (MDP) with discrete
action space defined by a tuple $\\{S,A(.),T(.|.,.),R(.,.),\gamma\\}$, where
$S$ is the state space which is discrete or continuous, $A(s)$ is the action
space in the state $s$, $T(s^{\prime}|s,a)$ is the transition probability from
state $s$ to state $s^{\prime}$ by performing action $a$, $R(s,a)$ is the
expected reward for state-action $(s,a)$, and $0\leq\gamma\leq 1$ is a
discount factor for the accumulated reward [29].

Policy is defined as a mapping of state $s$ to action $a$ denoted by
$\pi(a|s)$. The agent’s goal is to find the optimal policy $\pi^{*}(a|s)$,
which is a policy that maximizes the discounted return which is defined as
follows [30]

$G=r_{1}+\gamma r_{2}+\cdots=\sum_{k=0}^{\infty}\gamma^{k}r_{k+1},$ (1)

where $k$ is time-step, $r_{k+1}$ is the instant reward.

##  III Preliminaries

In this section, we first present Thompson sampling for policy estimation in
reinforcement learning. We give an overview of interval estimation methods and
dropout that are used for computing policy using Thompson sampling. Afterward,
we give an overview of using free energy paradigm in decision making, and its
connection to Thompson sampling.

###  III-A Thompson Sampling Policy Estimation

Thompson sampling selects each action in a state according to the probability
of the optimality of that action [31]. This probability can be computed using
belief distributions, that is the probability distribution of values under
model uncertainty, for actions in each state. In reinforcement learning
framework, belief distributions are updated during the learning process. The
policy of Thompson sampling is given by:

$\pi_{TS}(a_{i}|s)=P\bigg{(}\bigcap_{j\neq
i}\Big{\\{}Q(s,a_{i})>Q(s,a_{j})\Big{\\}}\bigg{)}=\\\
\int_{-\infty}^{\infty}p_{Q}(x_{i}|s,a_{i})\prod_{j\neq
i}P(x_{i}>Q(s,a_{j}))dx_{i}=\\\
\int_{-\infty}^{\infty}p_{Q}(x_{i}|s,a_{i})\prod_{j\neq
i}\int_{-\infty}^{x_{i}}p_{Q}(x_{j}|s,a_{j})dx_{j}dx_{i},$ (2)

where $Q(s,a_{i})$ is the value of action $a_{i}$ in state $s$, and
$p_{Q}(.|s,a_{i})$ is the belief distribution for action $a_{i}$ in state $s$.
For computing the policy using Thompson sampling, we need to compute belief
distributions. This can be computed by direct application of Bayes rule, but
it is not usaually used due to its computational complexity [32]. This problem
is tackled commonly by approximate belief distribution. One way to approximate
belief distribution is by computing confidence intervals [33]. In the
following, we review different methods for estimating belief distrubution.
Assuming belief distribution to be Gaussian, its mean and variance can be
obtained from confidence intervals. Dropout is another method to approximate
belief distribution in continuous environments [32].

####  III-A1 Model Free Interval Estimation

The actual value of doing action $a$ in state $s$ is denoted as $Q(s,a)$, and
its estimated value (Q-value) as $\hat{Q}(s,a)$. Model free Q-values are
updated by the following rule in Q-learning:

$\hat{Q}_{t+1}(s_{t+1},a_{t+1})=\hat{Q}_{t}(s_{t},a_{t})+\eta_{t}(s_{t},a_{t})[r_{t}(s_{t},a_{t})+\\\
\gamma\max_{a}\hat{Q}_{t}(s_{t+1},a)-\hat{Q}_{t}(s_{t},a_{t})],$ (3)

where $\eta_{t}(s,a)$ is learning rate, $r_{t}(s,a)$ is immediate reward, and
$t$ is time-step. A confidence interval on $Q(s,a)$ can be obtained by using
the following bound [17], that is valid when sample size $n(a,s)$ is
moderately large or when the reward distribution is Gaussian [17]

$P\left(\hat{Q}(s,a)-\mu<Q(s,a)<\hat{Q}(s,a)+\mu\right)=1-\nu,$ (4)
$\mu=t_{\frac{\nu}{2},n(s,a)-1}\times\frac{\overline{std}(s,a)}{\sqrt{n(s,a)}},$
(5)

where $t_{\frac{\nu}{2},n(s,a)-1}$ is the one-side t-value with
$\frac{\nu}{2}$ confidence level and $n(s,a)-1$ degrees of freedom, $n(s,a)$
is the sample size for action $a$ in state $s$, and $\overline{std}(s,a)$ is
the estimated standard deviation of the underlying reward distribution defined
by:

$\overline{std}(s,a)=\sqrt{\frac{n(s,a)\sum_{t}\tilde{Q}_{t}(s,a)^{2}-(\sum_{t}\tilde{Q}_{t}(s,a))^{2}}{n(s,a)\times(n(s,a)-1)}},$
(6)

where $\tilde{Q}_{t}$ is a monte-carlo sample of $Q$-values and is defined by:

$\tilde{Q}_{t}(s,a)=\sum_{k=k_{s}}^{k_{T}}{\gamma^{k-k_{s}}r_{k}},$ (7)

where $k_{s}$ is the time-step in an episode that agent visits state $s$,
$k_{T}$ is the time-step that the agent visits the terminal state, and $r_{k}$
is the reward that is taken by the agent in the time-step $k$. The bound
introduced in (4) has been used and works reasonably well in many practical
experiments [17, 34].

####  III-A2 Model Based Interval Estimation

Assume the agent is in state $s$, performing action $a$ and goes to state
$s^{\prime}$ and receives immediate reward $r_{t}(s,a)$, and the sample size
for this transition is denoted by $n(s,a,s^{\prime})$. Then, the model
parameters such as approximated transition probability
$\hat{T}(s^{\prime}|s,a)$ and the expected reward $\hat{R}(s,a)$ are updated
by:

$\hat{T}(s^{\prime}|s,a)=\frac{n(s,a,s^{\prime})+1}{n(s,a)+1},$ (8)
$\hat{R}(s,a)=\frac{\hat{R}(s,a)\times
n(s,a,s^{\prime})+r_{t}(s,a)}{n(s,a)+1}.$ (9)

The Q-values are estimated by solving the following Bellman equation[29]:

$\hat{Q}_{\pi}(s,a)=\hat{R}(s,a)+\sum_{s^{\prime}}\hat{T}(s^{\prime}|s,a)\left(\gamma\max_{a^{\prime}}\hat{Q}_{\pi}(s^{\prime},a^{\prime})\right).$
(10)

To obtain confidence intervals for Q-values, confidence intervals of model
parameters such as $\hat{R}(.)$ and $\hat{T}(.)$ are needed. We can use
Hoeffding [35] and Weissman [36] inequalities to obtain these confidence
intervals, respectively.

The lower and upper bounds are estimated using UCRL2 algorithm[33, 18]. The
algorithm solves the following equations to obtain lower $Q_{l}$ and upper
$Q_{u}$ bounds on Q-values:

$\displaystyle\hat{Q}_{u}(s,a)=\left(\hat{R}(s,a)+\epsilon_{R}\right)$ (11)
$\displaystyle+\max_{\tilde{T}(s^{\prime}|s,a)\in
CI_{T}}\sum_{s^{\prime}}\tilde{T}(s^{\prime}|s,a)\left(\gamma\max_{a^{\prime}}\hat{Q}_{u}(s^{\prime},a^{\prime})\right),$
$\displaystyle\hat{Q}_{l}(s,a)=\left(\hat{R}(s,a)-\epsilon_{R}\right)$ (12)
$\displaystyle+\min_{\tilde{T}(s^{\prime}|s,a)\in
CI_{T}}\sum_{s^{\prime}}\tilde{T}(s^{\prime}|s,a)\left(\gamma\max_{a^{\prime}}\hat{Q}_{l}(s^{\prime},a^{\prime})\right).$

In these equations $\epsilon_{R}$ is half of confidence interval for estimated
reward $\hat{R}(s,a)$, and $CI_{T}$ is the confidence set for the estimated
transition probability $\hat{T}(s^{\prime}|s,a)$.

####  III-A3 Dropout for Bayesian Approximation

In continuous domains, one possible approach to calculate Thompson sampling
policy is also confidence interval estimation as explained in [37]. However,
the method of [37] can only be applied for specific continuous domains and it
is not straightforward to generalize the idea for the case of neural networks
like Q-network where a neural network is used for estimating Q-values of
actions. We can obtain a sample of the belief distribution of Q-values by
applying dropout before each weighting layer of the Q-network and computing
its output [32]. An agent who uses Thompson sampling selects the action that
has maximum value among all actions for all networks created by dropout. If
the total number of networks created by dropout $N$ is large enough, Thompson
sampling policy for action $a_{i}$ would be fairly accurate and is given by:

$\pi_{TS}(a_{i}|s)=\frac{n_{s}(a_{i},s)}{N},$ (13)

where $n_{s}(a_{i},s)$ is number of times that action $a_{i}$ is selected by
the network (has the maximum value among all action) with dropout rate of $p$.
The advantage of this method is that it obviates the requirement for interval
estimation for calculating Thompson sampling policy.

###  III-B Free Energy Model of Decision Making

Free energy model is used in the literature to model decision-making under
information constraints (see [27]). The optimization problem for finding the
optimal policy in this context can be given by

$\pi^{*}(a|s)=\operatorname*{arg\,min}_{\pi(a|s)}F(s;\pi(a|s)),$
$F(s;\pi(a|s))=\mathbb{E}_{\pi(a|s)}\left[\frac{1}{\alpha}\log\frac{{\pi(a|s)}}{{p_{0}(a|s)}}-U(a,s)\right],$
(14)

where $F(s)$ is the free energy of an agent in a particular state $s$ when it
uses the policy ${\pi(a|s)}$ and has a reference prior policy ${p_{0}(a|s)}$.
In (14), $U(a,s)$ is the utility of action $a$ in state $s$. The inverse
temperature $\alpha$ is the trade-off constant between the information cost
and the expected utility.

This model is often used to model the behavior of an agent for decision making
under limited computational resources, e.g. when the agent has to choose an
action between too many actions and actually can try a subset of them in a
limited time [38, 26, 39, 40], or when the agent can use multiple experts and
needs to choose one of them quickly even if the selected one is sub-optimal
[41, 42].

The model of (14) does not consider model uncertainty during information
processing, which is necessary to better exploration-exploitation balance. In
order to model uncertainty, one should consider a two-step version of (14). A
latent variable $\theta$ is introduced which determines the environment model
$T_{\theta}(s^{\prime}|a,s)$. The agent has a two-step minimization on the
following nested free energy functional [31]

$\pi^{*}(a|s)=\operatorname*{arg\,min}_{\pi(a|s)}\min_{{p({\theta}|a,s)}}F(s;\pi(a|s),{p({\theta}|a,s)}),\\\
F(s;\pi(a|s),{p({\theta}|a,s)})=\mathbb{E}_{{\pi(a|s)}}\bigg{[}\frac{1}{\alpha}\log{\frac{{\pi(a|s)}}{{p_{0}(a|s)}}}+\\\
\mathbb{E}_{{p({\theta}|a,s)}}\left[\frac{1}{\beta}\log{\frac{{p({\theta}|a,s)}}{{p_{0}({\theta}|a,s)}}}-U(a,{\theta},s)\right]\bigg{]},$
(15)

where $p_{0}(\theta|a,s)$ is the prior belief on the latent variable,
${p({\theta}|a,s)}$ is the biased belief and $\beta$ is a hyperparameter that
indicates how much the agent trusts the prior belief. One can consider the
latent variable $\theta$ as a vector to be the parameters of the model, and
$p(\theta|a,s)$ as a distribution in the space of parameters. When the space
of parameters increrases, solving the two-step optimization problem in (15)
may become intractable.

In [43], this free energy model is used to solve an MDP problem under
information constraints using a free energy iteration method. The free energy
of an MDP problem is a special case of (15) where

$U(a,{\theta},s)={\mathbb{E}_{{T_{\theta}(s^{\prime}|a,s)}}\left[R_{s,a}^{s^{\prime}}-\gamma
F(s^{\prime})\right]}.$ (16)

If we use (16) in (15), we get a generalization to Bellman equation for value
maximization when we have model uncertainties and also information
constraints.

Decision-making in (15) can be seen as a model for transforming the prior
information under policy $p_{0}$ into posterior information $p$ by taking into
account the utility gains (or losses), and the transformation costs arising
from information processing and model uncertainties. It can be proven that for
single-state decision-making problems, Thompson sampling policy is decision
making under this model for the particular case of parameters $\alpha$ and
$\beta$ [31].

##  IV Proposed Method

In this paper, we assume the task is a Markov decision process (MDP) where the
agent wants to both learn the parameters of the task and optimal policy using
the reinforcement learning framework. Apart from the original space which is
MDP, the agent learns the parameters of the subspaces and uses the subspaces
for decision making. A subspace is a sub-dimensional space of the original
space, created by applying an arbitrary transformation on the state-action
space and modifies the space of state-action space as follows

$s_{sub}=\Phi(s),$ (17)

where $\Phi$ is an arbitrary transformation that maps state $s$ to state
$s_{sub}$ with lower number of features. This transformation might be only
feature selection. For example in a 2D maze environment, a subspace can be
x-position in each state. Since subspaces are smaller and have fewer
parameters, the agent learns faster in them which causes better generalization
and expediting the learning process. But, we need to find out which subspace
or the original space should be chosen in each state for getting the best
generalization during the learning process.

In this work, the perspective to find the most appropriate subspace is
minimizing free energy. In the free energy formulation, the utility in each
space is a function of Thompson sampling, and the regularizing term encourages
the policy of the space to be close to an arbitrary behavioral policy and also
remain consistent with the main space utility to avoid perceptual aliasing.
Then, it compares the free energy to select the original space or the most
appropriate subspace and uses the computed policy from free energy
minimization to interact with the environment. Fig. 1 depicts the information
flow in our proposed method which we call free energy with Thompson sampling
utility, abbreviated with FETS in the rest of the paper.

Figure 1:  Information flow of the proposed method. The agent finds the
optimal policy that minimizes free energy and evaluate the optimal free energy
for subspaces and the main space, then it uses the optimal policy of the space
with minimum free energy to interact with the environment.

###  IV-A Selection with Subspaces using Free Energy Model

An agent has several task models (subspaces or the main space), that are
updated using the feedback from the external environment. For the model $m$ of
each space, we use (14) to calculate the free energy of the model, and we
define the utility $U(a,s,m)$ to be negative informational surprise about
optimality of action $a$ in state $s$ in that model. Thompson sampling policy
is equal to optimality of actions (see (2)), so we define the utility as

$U(a,s,m)=\log{\pi_{TS}(a|s,m)}.$ (18)

This utility function (which is a function of Thompson sampling policy)
handles exploration-exploitation trade-off, and has some computational
benefits, because one of the optimizations in (15) which is intractable when
the model parameter space expands, is substituted by the estimation of
Thompson sampling policy. To deal with the PA problem of subspaces, we use the
following constraint that forces the agent to consider the main space utility
in each space

$\mathbb{E}_{\pi(a|s,m)}[U(a,s,m)]-\mathbb{E}_{\pi(a|s,m)}[U(a,s,m_{Main})]<K_{1},$
(19)

where $m$ is a model that can be subspaces or the main space, and $m_{Main}$
is the main space111In the case $m=m_{Main},$ (19) always holds because we do
not have PA in the main space.. The constraint (19) ensures that expected
utility of the main space is not much less than the expected utility of the
subspace. We also want the policy to be close to an arbitrary behavioral
policy, so we consider the following constraint

$\mathbb{D}_{KL}(\pi(a|s,m)||\pi_{B}(a|s,m))<K_{2},$ (20)

where $\pi_{B}(a|s,m)$ is an arbitrary behavioral policy. The constraint (20)
is very useful when we have nonaccurate estimations, because we can limit the
effect of low accuracy estimations of uncertainties to the policy of the agent
by selecting a behavioral policy like $\epsilon$-greedy that does not use the
uncertainty estimations. By considering the utility function of (18) and
constraints (19) and (20), this problem can be cast as following free energy
minimization problem

Algorithm 1 Free Energy Evaluation

Function
FreeEnergy($\pi_{TS}(a|s,m),\pi_{TS}(a|s,m_{Main}),\pi_{B}(a|s,m),\alpha,\beta$)

1:$\pi_{TS}(a|s,m)$ is Thompson sampling policy for model $m$,
$\pi_{TS}(a|s,m_{Main})$ is Thompson sampling policy for the main space,
$\pi_{B}(a|s,m)$ is an arbitrary behavioral policy, $\alpha$ is the parameter
to be restricted to the behavioral policy and $\beta$ is the the
generalization parameter of the agent

2:$U(a,s,m)=\log{\pi_{TS}(a|s,m)}$ $//$ Utility definition (18)

3:$\tilde{U}(a,s,m)=U(a,s,m)-\frac{1}{\beta}(U(a,s,m)-U(a,s,m_{Main}))$

4:$Z(s,m)=\sum_{a}\pi_{B}(a|s,m)e^{\alpha\tilde{U}(a,s,m)}$

5:$\pi^{*}(a|s,m)=\frac{1}{Z(s,m)}\pi_{B}(a|s,m)e^{\alpha\tilde{U}(a,s,m)}$
$//$ Using (23)

6:$F(s,m)=\sum\limits_{a}\pi^{*}(a|s,m)\left[\frac{1}{\alpha}\log\frac{\pi^{*}(a|s,m)}{\pi_{B}(a|s,m)}-\tilde{U}(a,s,m)\right]\newline
$ $//$ Using (21)

7:return $F(s,m),\pi^{*}(a|s,m)$

$\pi^{*}(a|s,m)=\operatorname*{arg\,min}_{\pi(a|s,m)}F(s,m,\pi(a|s,m)),$
$F(s,m,\pi(a|s,m))=\mathbb{E}_{\pi(a|s,m)}\bigg{[}\frac{1}{\alpha}\log\frac{\pi(a|s,m)}{\pi_{B}(a|s,m)}+\\\
\frac{1}{\beta}\log{\frac{\pi_{TS}(a|s,m)}{\pi_{TS}(a|s,m_{Main})}}-\log{\pi_{TS}(a|s,m)}\bigg{]},$
(21)

where parameters $\beta$ and $\alpha$ are the Lagrange multipliers for the
constraints (19) and (20), and they have a direct relationship with $K_{1}$
and $K_{2}$, respectively. Parameters $\beta$ and $\alpha$ control the force
of making the agent behavior in the state to be similar to that of the main
space and given behavioral policy, respectively. The optimization problem of
(21) is identical to the free energy framework in (14) and the corresponding
utility function is

$\tilde{U}(a,s,m)=-\frac{1}{\beta}\log{\frac{\pi_{TS}(a|s,m)}{\pi_{TS}(a|s,m_{Main})}}+U(a,s,m),$
(22)

so the optimal solution for this problem is [27]

$\pi^{*}(a|s,m)=\frac{1}{Z(s,m)}\pi_{B}(a|s,m)e^{\alpha\tilde{U}(a,s,m)},$

$Z(s,m)=\sum_{a}\pi_{B}(a|s,m)e^{\alpha\tilde{U}(a,s,m)}.$ (23)

Finally, the best space is given by

$m^{*}=\operatorname*{arg\,min}_{m}F(s,m,\pi^{*}(a|s,m)).$ (24)

Then, the agent samples an action according to the policy of
$\pi^{*}(a|s,m^{*})$ to ineract with its environment. After that, it updates
all models in parallel due to the selected action and the feedback of the
environment. Algorithm 2 illustrates our framework for discrete and continuous
domains. Next, in Theorem 1, we investigate the conditions for convergence of
algorithm in discrete domain.

######  Theorem 1.

Let $\mathbb{M}$ be an MDP with finite state space $\mathbb{S}$, and finite
action space $\mathbb{A}$. In the proposed scheme, if an agent uses finite
$\alpha>0$ and $\beta>1$ and uses $\epsilon$-greedy as its behavioral policy,
then the agent finally uses the main space policy. Therefore, it guarantees
convergence to the optimal policy222In practice, the utility function in (18)
might get numerally not defined values as Thompson sampling policy goes to
zero. Therefore, we add a small constant to the probabilities to avoid these
cases. .

The detailed proof for Theorem 1 is given in Appendix A.

Algorithm 2 Concurrent RL using subspaces with FETS

Function FETS($s,r,I,D,W,\pi_{B},p,\alpha,\beta$)

1:$s$ is the state observed from the environment, $r$ is the reward from
environment, $I$ consists of values, Q-networks and confidence intervals, $D$
is the domain type (Discrete or Continuous), W is a set consisting of
subspaces and the main space models. Model can be Q-table, MDP, neural network
and etc, $\pi_{B}$ is an arbitrary behavioral policy, $p$ is dropout
probability, $\alpha$ is the agent parameter to remain restricted to the
behavioral policy, $\beta$ is the agent generalization characteristic

2:Initialize $F(s,m)$

3:Update $I$

4:for all $m\in W$ do

5: if $D$ is discrete (Model-free or Model-based) then

6: for all $a_{i}\in A$ do

7: Use $I.CI$($s$) to form approximated distribution $P_{i}$

8: Use (2) to compute $\pi_{TS}$

9: end for

10: end if

11: if $D$ is continuous then

12: $n_{s}(.)=0$

13: for $i=1$ to $N$ do

14: $Q=I.NN.forward(dropout=p)$ $//$ A forward pass in the Q-network with
dropout rate of $p$

15: $a_{b}=\operatorname*{arg\,max}{Q}$

16: $n_{s}(a_{b})=n_{s}(a_{b})+1$

17: end for

18: Compute $\pi_{TS}$ using (13)

19: end if

20:
$F(s,m),\pi^{*}(a|s,m)=$FreeEnergy$(\pi_{TS}(a|s,m),\pi_{TS}(a|s,m_{Main}),\newline
\pi_{B}(a|s,m),\alpha,\beta)$ $//$ Use Algorithm 1. $m_{Main}$ is the main
space.

21:end for

22:$m^{*}=\operatorname*{arg\,min}{F(s,m)}$

23:Sample according to $\pi^{*}(a|s,m^{*})$ to get action $a$

24:return $a$

##  V Experimental Results

We test our framework in both discrete and continuous domains and for model-
free and model-based reinforcement learning333The codes for reproducing the
results of this section can be downloaded from
https://www.dropbox.com/sh/kz8q1685lmaxl6m/AAAMHGwaOmHiWOuKn-grd-rma?dl=0..

###  V-A Discrete Domain

Figure 2: 2-D maze environments.

In the discrete case, we compare our framework (FETS) with other discrete off-
policy approaches using $\epsilon$-greedy policy as the behavioral policy. We
select the following methods based on some key feaures: subspaces usage, space
selection criteria, and the kind of policy.

  1. 1.

MB: Our model-based approach ignoring subspaces. The policy of the agent is
the behavioral policy.

  2. 2.

MB-FE: Our model-based approach ignoring subspaces. The policy of the agent is
given in (23) instead of using the behavioral policy.

  3. 3.

MB-CDM: Model-based approach with generalization in subspaces termed MoBLeS
that integrates policies of subspaces using a confidence degree model
(CDM)[18].

  4. 4.

MB-FETS-B: Model-based FETS method where the policy is the behavior policy in
the selected space.

  5. 5.

MB-FETS-FE: Model-based FETS method where the policy is given in (23) for the
selected space.

  6. 6.

MF: Famous $Q(\lambda)$ learning method [44] by selecting the best decay rate
of the eligibility trace ($\lambda$).

  7. 7.

MF-FE: $Q(\lambda)$ method where the agent uses the policy that is given in
(23).

  8. 8.

MF-LUS: $Q(\lambda)$ with generalization in subspaces that integrates policies
of subspaces with the least uncertain source (LUS) method[17].

  9. 9.

MF-FETS-B: Model-free FETS method where the policy is the behavior policy in
the selected space.

  10. 10.

MF-FETS-FE: Model-free FETS method where the policy is given in (23) for the
selected space.

We test our framework on 2-D maze environments and a real-time strategy game
called StarCraft:Broodwar (SC:BW)[45]. In these experiments, the parameters of
the agent integration and generalization are $\alpha=4$ and $\beta=7$,
respectively. However, the algorithm is not very sensitive to the exact values
of these parameters, and the results are similar in a wide interval around
these parameters.

####  V-A1 2-D Maze Environment

We simulate 2-D maze environments introduced in[18] and 4 other new
environments (Fig. 2). In these environments, the agent can move in four
directions (up, right, down and left). The task is not deterministic, and each
action has its real effect with a probability of 0.9; otherwise, the agent
moves in a random direction. The agent is given reward reaching the goal (the
green cell of the environments) and is punished by hitting the barriers. There
is a constant cost of performing each action. The state is represented by
location X and Y (the vertical and horizontal axis). More information on the
setting of 2-D maze environment can be found in Appendix B.

In 2-D maze environments, two primitive subspaces are created by keeping
either X or Y features. Some environments are generalizable in these subspaces
(for example environment 1,5,7 and 8) and some environments are designed to be
nongeneralizable (for example environment 4 and 6).

Figure 3: (a)-(h) Average accumulative reward simulating model-based
approaches for environments 1-8 in 15 runs.

In our simulations at the beginning of each episode, the starting state is
randomized between possible starting states (empty non-goal cells). We record
average accumulated reward for each method and average free energy over all
states for subspaces and the main space. The average accumulated reward for
model-based and model-free approaches are depicted in Fig. 3 and Fig. 4,
respectively. Our framework has a significantly better average accumulated
reward in both model-based and model-free RL compared to the other methods.

Figure 4: (a)-(h) Average accumulative reward simulating model-free approaches
for environments 1-8 in 15 runs.

Our method also has better performance in detecting which subspace is more
generalizable. Environment 7 is more generalizable in subspace X (subspace
that has only the X feature, and states with different Y values and the same X
value are assumed to be one state.). This environment is designed such that
only subspace X is informative for decision making. As it can be seen in Fig.
5(c) and (d), our method does not stop generalization in subspace X, whereas
other methods [17, 18] stop generalization by switching to the main space in
the early stages of learning. Environment 8 is opposite to environment 7 and
is only generalizable in subspace Y and our algorithm successfully detects
this fact (see Fig. 5(e) and (f)).

Figure 5:  Average free energies and selection percentage of each model
(subspaces and the main space) for model-based version of our approach in
environments 7 (top plots) and 8 (bottom plots). Plots (a) and (b) are average
free energy of each space as a function of the number of episodes. Plots
(c)-(f) are selection percentage of each space in each episode for our and CDM
approaches.

Generalizability also results in decreasing free energy. In environment 7,
free energy of subspace X decreases more than subspace Y and the main space.
In environment 8, it happens for subspace Y in the same way (see Fig. 5(a) and
(b)).

####  V-A2 Real-Time Strategy Game StarCraft:Broodwar

In this subsection, we evaluate the performance of our approach in a more
complex task of abstract combat maneuvering model of SC:BW between RL agent
unit and enemy units[45, 18]. The RL agent can move toward each enemy, retreat
(get away from all enemies) and shoot each enemy and cause its hitpoint
decreases. If the agent gets too close to an enemy, the enemy shoots and the
agent hitpoint decreases. The agent gets the following rewards:

  * •

The agent is punished by hitting the wall.

  * •

It is punished by firing when no enemy is nearby444The proximity to each enemy
is defined by the Manhattan distance[46] and if the distance is less than
$\theta_{E}$, it means that the enemy is nearby..

  * •

It is given a reward when it kills all of the enemies.

  * •

It gets a reward if it shoots an enemy and gets punishment when is shot by an
enemy.

In this environment, the agent observes location X, location Y, its hitpoint
and the location and the hitpoint of each enemy. More information on the
setting of SC:BW environment can be found in Appendix C. We consider the
following subspaces: the subspace of the agent XY location, the subspace of
the agent’s hitpoint and the subspace of the agent distance to each enemy. The
subspace of the agent distance to the enemy is not primitive and is a
nonlinear subspace created via a nonlinear combination of features X and Y.

We simulated this environment for one enemy and three enemies scenarios
depicted in Fig. 6. In these scenarios, the agent starts each episode in a
fixed starting state and can move, but the enemy location is fixed all over
each episode. This feature of this environment makes the XY location an
informative subspace.

Figure 6: StarCraft:BroodWar environment scenarios.

Fig. 7 and Fig. 8 give some information about the scenarios of SC:BW
environment; the average accumulated reward for different methods, average
free energy and selection percentage for subspaces and main space. It can be
noticed that our approach has a significantly better average accumulated
reward in comparison to other methods.

As agent gets experienced in the SC:BW environments, the subspace of distance
to enemies becomes more important for the RL agent to fight with the enemies.
In one enemy scenario, the agent successfully kills the enemy. As shown in
Fig. 7(c) and (d) free energy of the subspace of distance to enemy decreases
more than other subspaces for both model-free and model-based versions of our
framework in this scenario. In this environment, the confidence intervals are
inacurate, and the constraint (20) helps the agent to tackle this issue.

Figure 7: SC:BW with one enemy results. (a) and (b) Average accumulated reward
for various model-based and model-free approaches. (c) and (d) average free
energy of different subspaces and main space for model-based and model-free
version of our framework. (e)-(h) Selection percentage for different subspace-
based methods.

###  V-B Continuous Domain

In this subsection, we also test our idea in continuous maze environments[32].
The barrier configurations of these mazes are depicted in Fig. 9. We compare
the following methods using Thompson sampling policy as the behavioral policy.

  1. 1.

TS: Using Q-networks with dropout to get a random sample of Q-values and
perform Thompson sampling policy as explained in section III-A3.

  2. 2.

TS-FE: The policy of the agent is given in (23) instead of using the
behavioral policy.

  3. 3.

TS-FETS-B: In this method, the free energy model is just used for selection
between different spaces and the policy is the behavioral policy of the
selected space and the sampling method is like the method of TS.

  4. 4.

TS-FETS-FE: In this method, the free energy model is used both for selection
between different spaces and also for integration of information of the main
space into each space policy given in (23).

In methods that use the free energy model (all except the first), the dropout
method introduced in section III-A3 is used to estimate Thompson sampling. In
this task, Q-networks are used for estimating Q-values. The networks are
fully-connected nets with two hidden layers. The main space Q-network has 50
neurons in each hidden layer, and the subspaces have 15 neurons, and the
dropout rate is $0.1$. This setting makes subspace Q-networks smaller, and
therefore faster to learn in contrast with the main space. The free energy of
subspaces decreases by reducing the number of neurons of Q-networks. The lower
number of neurons also helps to have a better generalization in subspaces and
also avoids over-fitting in the network. In these environments, the parameters
of the agent integration and generalization are $\alpha=\beta=3$555We use
$\alpha=\beta$ case, because in this experience the behavoiral policy is
Thompson sampling and this causes simpler formalisation. The valuse are
selected based on conditions $\beta\geq 1$ and $\alpha>0$ of Theorem 1. High
value of $\alpha$ can cause ignoring PA, and low value of $\alpha$ can hinder
us to have good generalization. Therefore, we choose this moderate value for
$\alpha$., respectively. In this case, since the behavioral policy is Thompson
sampling and $\alpha=\beta$, we can rewrite the free energy model in (21) with
a simpler form:

$F(s,m,\pi(a|s,m))=\mathbb{E}_{\pi(a|s,m)}\left[-\log{\pi_{TS}(a|s,m)}\right]+\\\
\frac{1}{\alpha}\mathbb{D}_{KL}(\pi(a|s,m)||\pi_{TS}(a|s,m_{Main})).$ (25)

This means that the agent is maximizing expected utility defined in (18)
having the following constraint that the produced policy by free energy
optimization stays close to the policy of the main space as follows

$\mathbb{D}_{KL}(\pi(a|s,m)||\pi_{TS}(a|s,m_{Main}))<K,$ (26)

In this environment, the agent has nine eyes, pointing to different
directions. Each eye can observe three features that are proximity to wall,
poison or food so that 27 sensors can determine the environment states. The
agent can move toward five directions and gets a reward by colliding to red
circles (food) and gets punished by colliding to yellow circles (poison). The
agent gets further reward for not going toward walls and move straight in a
line[32]. The task which is not stationary, and the red circles and green ones
appear in random locations after the agent eats them, so the location
information is redundant in this task unlike the SC:BW environment.
Information on the setting of this environment can be found in Appendix D.

Figure 8: SC:BW with three enemies results. (a) and (b) Average accumulated
reward for various model-based and model-free approaches. (c) and (d) Average
free energy of different subspaces and main space for the model-based and
model-free version of our framework. (e)-(h) Selection percentage for
different subspace-based methods.

For an accurate comparison of different approaches, we perform a multi-agent
simulation similar to [32] where each agent strategy corresponds to one of
four alternative methods. Fig. 10 depicts average accumulated reward, average
free energies and selection percentage of each subspace. Our approach improves
Thompson sampling in early trials in the learning process.

As the agent gets experienced in the environment, it avoids eating poisons and
moves toward foods. Free energies of the subspaces of food and poison decrease
more than the subspace of wall (Fig. 10(e) and (f)).

Figure 9: Continuous maze environments with different barriers configurations.
Different agents do not see each other and learn individually. However, they
affect on a shared environment. Figure 10: Continuous environments results.
(a)-(d) Average accumulated reward of different methods in different
environments. (e) Average free energy for each subspace in maze 1. (f)
Selection percentage of each subspace in maze 1.

##  VI Conclusion

In this paper, we introduced a framework to improve sample efficiency of
reinforcement learning algorithms using the generalization property of
subspaces but in face of higher computational complexity in both discrete and
continuous domains. The computational complexity is a direct effect of
learning in subspaces alongside the main space. Subspaces help the agent
sample efficiency because they have a fewer number of parameters, so they can
learn the task faster than the main space, but in general, they cannot reach
the optimal policy. Therefore, we proposed the free energy model for space
selection and also policy generation.

The free energy model is suitable to model decision-making under some resource
limitations. In this work, the resource limitations are sub-optimality of the
suggested policies by the subspaces and also inaccurate uncertainty
estimations. Therefore, to tackle them, we used the free energy model, where
we defined utility to be the optimality of actions in a state and considered
information constraints to guarantee the generated policy remains consistent
with information of the main space and also is close enough to a behavioral
policy.

We used the optimal free energy as a criterion to select between different
spaces. Then, we considered two cases for policy: the behavioral policy, and
the policy suggested by the free energy model. We saw that in most problems
the policy that is suggested by the free energy model has a better
performance. This policy in each space helps to avoid over-exploration which
is one of the limitations of using Thompson sampling in large-scale
environments.

Our approach is robust to inaccurate uncertainty estimation (for example in
SC:BW), and this feature makes it also usable in model-free approaches where
the confidence intervals are less accurate than model-based approaches. Also,
we observed that our method can confront the PA problem of the subspaces
better than the standard RL approach and also previous related methods. This
was evident from the high performance of our method in comparison with other
approaches.

We saw that in our framework non-informative subspaces get higher free energy
as the agent gets more experienced (see Fig. 5 and Fig. 10). If the subspaces
are created by selecting a subset of features, removing redundant features
from the main space can reduce the computational complexity of the algorithm.
This scheme related to the feature-based attention control in the literature
[47, 48]. Another usage of detecting non-informative subspaces is to remove
them during the learning process to reduce the computational complexity of the
algorithm. and our method can detect this possibility.

There are multiple directions for future works:

  * •

Finding an optimal set of subspaces which is task-based can be done
automatically using a criterion. If each subspace corresponds a sub-task, then
more complex problems like SC:BW can be solved.

  * •

Although our method has robustness to inaccurate uncertainty estimation, more
reliable approaches to estimate Thompson sampling policy can improve the
sample efficiency.

  * •

In the current method, the temperature of free energy model is not
automatically determined. An adaptive method to set the temperature might
cause improvements.

  * •

In continuous domains, automatically adapting of network settings like number
of neurons, learning rate, and etc. can improve the robustness of the method.
Alternatively, we can have multiple networks with different hyperparameters
and treat them as different subspaces.

## References

  * [1] L. P. Kaelbling, M. L. Littman, and A. W. Moore, “Reinforcement learning: A survey,” _Journal of artificial intelligence research_ , vol. 4, pp. 237–285, 1996.
  * [2] P. Abbeel, V. Ganapathi, and A. Y. Ng, “Learning vehicular dynamics, with application to modeling helicopters,” in _Advances in Neural Information Processing Systems_ , 2006, pp. 1–8.
  * [3] N. Navarro-Guerrero, C. Weber, P. Schroeter, and S. Wermter, “Real-world reinforcement learning for autonomous humanoid robot docking,” _Robotics and Autonomous Systems_ , vol. 60, no. 11, pp. 1400–1407, 2012\.
  * [4] N. Imanberdiyev, C. Fu, E. Kayacan, and I.-M. Chen, “Autonomous navigation of uav by using real-time model-based reinforcement learning,” in _2016 14th International Conference on Control, Automation, Robotics and Vision (ICARCV)_. IEEE, 2016, pp. 1–6.
  * [5] J. Lu, D. Wu, M. Mao, W. Wang, and G. Zhang, “Recommender system application developments: a survey,” _Decision Support Systems_ , vol. 74, pp. 12–32, 2015.
  * [6] E. Q. da Silva, C. G. Camilo-Junior, L. M. L. Pascoal, and T. C. Rosa, “An evolutionary approach for combining results of recommender systems techniques based on collaborative filtering,” _Expert Systems with Applications_ , vol. 53, pp. 204–218, 2016.
  * [7] A. Holzinger, “Interactive machine learning for health informatics: when do we need the human-in-the-loop?” _Brain Informatics_ , vol. 3, no. 2, pp. 119–131, 2016.
  * [8] J. Zhang, P. Fiers, K. A. Witte, R. W. Jackson, K. L. Poggensee, C. G. Atkeson, and S. H. Collins, “Human-in-the-loop optimization of exoskeleton assistance during walking,” _Science_ , vol. 356, no. 6344, pp. 1280–1284, 2017.
  * [9] J. Li, A. H. Miller, S. Chopra, M. Ranzato, and J. Weston, “Dialogue learning with human-in-the-loop,” _arXiv preprint arXiv:1611.09823_ , 2016.
  * [10] R. S. Sutton, “Generalization in reinforcement learning: Successful examples using sparse coarse coding,” in _Advances in neural information processing systems_ , 1996, pp. 1038–1044.
  * [11] W. R. Thompson, “On the likelihood that one unknown probability exceeds another in view of the evidence of two samples,” _Biometrika_ , vol. 25, no. 3/4, pp. 285–294, 1933.
  * [12] A. Gopalan, S. Mannor, and Y. Mansour, “Thompson sampling for complex online problems,” in _International Conference on Machine Learning_ , 2014, pp. 100–108.
  * [13] T. Mandel, Y.-E. Liu, E. Brunskill, and Z. Popovic, “Efficient bayesian clustering for reinforcement learning.” in _IJCAI_ , 2016, pp. 1830–1838.
  * [14] D. Abel, D. E. Hershkowitz, and M. L. Littman, “Near optimal behavior via approximate state abstraction,” _arXiv preprint arXiv:1701.04113_ , 2017\.
  * [15] D. Abel, D. Arumugam, L. Lehnert, and M. Littman, “State abstractions for lifelong reinforcement learning,” in _International Conference on Machine Learning_ , 2018, pp. 10–19.
  * [16] H. Firouzi, M. N. Ahmadabadi, B. N. Araabi, S. Amizadeh, M. S. Mirian, and R. Siegwart, “Interactive learning in continuous multimodal space: A bayesian approach to action-based soft partitioning and learning,” _IEEE Transactions on Autonomous Mental Development_ , vol. 4, no. 2, pp. 124–138, 2011.
  * [17] P. Daee, M. S. Mirian, and M. N. Ahmadabadi, “Reward maximization justifies the transition from sensory selection at childhood to sensory integration at adulthood,” _PloS one_ , vol. 9, no. 7, p. e103143, 2014.
  * [18] M. Hashemzadeh, R. Hosseini, and M. N. Ahmadabadi, “Exploiting generalization in the subspaces for faster model-based reinforcement learning,” _IEEE transactions on neural networks and learning systems_ , vol. 30, no. 6, pp. 1635–1650, 2018.
  * [19] F. L. D. Silva and A. H. R. Costa, “Object-oriented curriculum generation for reinforcement learning,” in _Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems_. International Foundation for Autonomous Agents and Multiagent Systems, 2018, pp. 1026–1034.
  * [20] J. Schmidhuber, “Powerplay: Training an increasingly general problem solver by continually searching for the simplest still unsolvable problem,” _Frontiers in psychology_ , vol. 4, p. 313, 2013.
  * [21] S. Narvekar and P. Stone, “Learning curriculum policies for reinforcement learning,” in _Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems_. International Foundation for Autonomous Agents and Multiagent Systems, 2019, pp. 25–33.
  * [22] S. Narvekar, B. Peng, M. Leonetti, J. Sinapov, M. E. Taylor, and P. Stone, “Curriculum learning for reinforcement learning domains: A framework and survey,” _arXiv preprint arXiv:2003.04960_ , 2020.
  * [23] G. Tesauro, “Temporal difference learning and td-gammon,” _Communications of the ACM_ , vol. 38, no. 3, pp. 58–68, 1995.
  * [24] D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. Van Den Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot _et al._ , “Mastering the game of go with deep neural networks and tree search,” _nature_ , vol. 529, no. 7587, p. 484, 2016.
  * [25] A. Vezhnevets, V. Mnih, S. Osindero, A. Graves, O. Vinyals, J. Agapiou _et al._ , “Strategic attentive writer for learning macro-actions,” in _Advances in neural information processing systems_ , 2016, pp. 3486–3494.
  * [26] D. A. Ortega and P. A. Braun, “Information, utility and bounded rationality,” in _International Conference on Artificial General Intelligence_. Springer, 2011, pp. 269–274.
  * [27] P. A. Ortega and D. A. Braun, “Thermodynamics as a theory of decision-making with information-processing costs,” _Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences_ , vol. 469, no. 2153, p. 20120683, 2013.
  * [28] K. E. Stephan, W. D. Penny, J. Daunizeau, R. J. Moran, and K. J. Friston, “Bayesian model selection for group studies,” _Neuroimage_ , vol. 46, no. 4, pp. 1004–1017, 2009.
  * [29] R. Bellman, “A markovian decision process,” _Journal of mathematics and mechanics_ , pp. 679–684, 1957.
  * [30] R. S. Sutton and A. G. Barto, _Reinforcement learning: An introduction_. MIT press, 2018.
  * [31] P. A. Ortega and D. A. Braun, “Generalized thompson sampling for sequential decision-making and causal inference,” _Complex Adaptive Systems Modeling_ , vol. 2, no. 1, p. 2, 2014.
  * [32] Y. Gal and Z. Ghahramani, “Dropout as a bayesian approximation: Representing model uncertainty in deep learning,” in _international conference on machine learning_ , 2016, pp. 1050–1059.
  * [33] T. Jaksch, R. Ortner, and P. Auer, “Near-optimal regret bounds for reinforcement learning,” _Journal of Machine Learning Research_ , vol. 11, no. Apr, pp. 1563–1600, 2010.
  * [34] P. Daee, “A developmental method for multimodal sensory integration,” Ph.D. dissertation, MS thesis, School Elect. Comput. Eng., Univ. Tehran, Tehran, Iran, 2014.
  * [35] W. Hoeffding, “Probability inequalities for sums of bounded random variables,” _Wiley StatsRef: Statistics Reference Online_ , 2014.
  * [36] T. Weissman, E. Ordentlich, G. Seroussi, S. Verdu, and M. J. Weinberger, “Inequalities for the l1 deviation of the empirical distribution,” _Hewlett-Packard Labs, Tech. Rep_ , 2003.
  * [37] M. White and A. White, “Interval estimation for reinforcement-learning algorithms in continuous-state domains,” in _Advances in Neural Information Processing Systems_ , 2010, pp. 2433–2441.
  * [38] N. Tishby and D. Polani, “Information theory of decisions and actions,” in _Perception-action cycle_. Springer, 2011, pp. 601–636.
  * [39] S. Gottwald and D. A. Braun, “Bounded rational decision-making from elementary computations that reduce uncertainty,” _Entropy_ , vol. 21, no. 4, p. 375, 2019.
  * [40] L. T. Trujillo, “Mental effort and information-processing costs are inversely-related to global brain free energy during visual categorization,” _Frontiers in neuroscience_ , vol. 13, p. 1292, 2019.
  * [41] H. Hihn and D. A. Braun, “Hierarchical expert networks for meta-learning,” _arXiv preprint arXiv:1911.00348_ , 2019.
  * [42] H. Hihn, S. Gottwald, and D. A. Braun, “An information-theoretic on-line learning principle for specialization in hierarchical decision-making systems,” in _2019 IEEE 58th Conference on Decision and Control (CDC)_. IEEE, 2019, pp. 3677–3684.
  * [43] J. Grau-Moya, F. Leibfried, T. Genewein, and D. A. Braun, “Planning with information-processing constraints and model uncertainty in markov decision processes,” in _Joint European Conference on Machine Learning and Knowledge Discovery in Databases_. Springer, 2016, pp. 475–491.
  * [44] C. Watkins, “Learning from delayed rewards (phd dissertation),” _King’s College Cambridge, England_ , 1989.
  * [45] S. Wender and I. Watson, “Applying reinforcement learning to small scale combat in the real-time strategy game starcraft: Broodwar,” in _2012 IEEE Conference on Computational Intelligence and Games (CIG)_. IEEE, 2012, pp. 402–408.
  * [46] V. Perlibakas, “Distance measures for pca-based face recognition,” _Pattern recognition letters_ , vol. 25, no. 6, pp. 711–724, 2004.
  * [47] A. Borji, M. N. Ahmadabadi, and B. N. Araabi, “Learning sequential visual attention control through dynamic state space discretization,” in _2009 IEEE International Conference on Robotics and Automation_. IEEE, 2009, pp. 2258–2263.
  * [48] A. Borji, M. N. Ahmadabadi, B. N. Araabi, and M. Hamidi, “Online learning of task-driven object-based visual attention control,” _Image and Vision Computing_ , vol. 28, no. 7, pp. 1130–1145, 2010.
  * [49] H. B. Callen, “Thermodynamics and an introduction to thermostatistics,” 1998.

##  Appendix A The Proof of Theorem 1

The optimal free energy is related to $Z(s,m)$ as follows [49]

$F^{*}(s,m)=-\frac{1}{\alpha}\log{Z(s,m)},$
$Z(s,m)=\sum_{a}\pi_{B}(a|s,m)e^{\alpha\tilde{U}(a,s,m)}.$

Since all the logarithms are bounded by adding a small constant $\xi>0$ to the
Thompson sampling probabilities, and the behavioral policy is
$\epsilon$-greedy and $\alpha$ is finite, we have

$\pi_{B}(a|s,m_{Main})e^{\alpha\tilde{U}(a,s,m)}\geq\frac{\epsilon}{|A|}e^{\alpha\log{\xi}}=\frac{\epsilon}{|A|}\xi^{\alpha}>0.$

Since $\tilde{U}(a,s,m)\leq 0$, we have

$Z(s,m)=\sum_{a}\pi_{B}(a|s,m)e^{\alpha\tilde{U}(a,s,m)}\leq\sum_{a}\pi_{B}(a|s,m)=1,$

and therefore

$\pi^{*}(a|s,m)=\frac{1}{Z(s,m)}\pi_{B}(a|s,m_{Main})e^{\alpha\tilde{U}(a,s,m)}>0,$

which shows that the agent does not stop exploration. When the sample size
$n(s,a)$ goes to infinity, and the confidence intervals go to zero, the
Thompson sampling policies become one-hot, that is for one action it is equal
to 1 and for the others it is equal to $\xi$. Without losing the generality,
we suppose that the first action is optimal in the main space, and the second
one is optimal in the subspace $m$, so $\tilde{U}(.,s,m)$666$\tilde{U}(.,s,m)$
is a vector with elements $\tilde{U}(a,s,m)$ for different values of $a$.  and
$\tilde{U}(.,s,m_{Main})$ are computed as follows:

$\tilde{U}(.,s,m)=\frac{1}{\beta}\log{\pi_{TS}(.|s,m_{Main})}+\\\
\frac{\beta-1}{\beta}\log{\pi_{TS}(.|s,m)}=\\\
\left[\frac{\beta-1}{\beta}\log(\xi),\frac{1}{\beta}\log(\xi),\log(\xi),\cdots,\log(\xi)\right],$
$\tilde{U}(.,s,m_{Main})=\frac{1}{\beta}\log{\pi_{TS}(.|s,m_{Main})}+\\\
\frac{\beta-1}{\beta}\log{\pi_{TS}(.|s,m_{Main})}=\\\
\left[0,\log(\xi),\cdots,\log(\xi)\right],$

and the behavioral policy for them is $\epsilon$-greedy and is written as
follows

$\pi_{B}(.|s,m)=\left[\frac{\epsilon}{|A|},1-\epsilon+\frac{\epsilon}{|A|},\frac{\epsilon}{|A|},\cdots,\frac{\epsilon}{|A|}\right],$
$\pi_{B}(.|s,m_{Main})=\left[1-\epsilon+\frac{\epsilon}{|A|},\frac{\epsilon}{|A|},\cdots,\frac{\epsilon}{|A|}\right],$

so we have

$Z(s,m)=\frac{\epsilon}{|A|}\xi^{\frac{\alpha(\beta-1)}{\beta}}+(1-\epsilon+\frac{\epsilon}{|A|})\xi^{\frac{\alpha}{\beta}}\\\
+\frac{(|A|-2)\epsilon}{|A|}\xi^{\alpha},$
$Z(s,m_{Main})=(1-\epsilon+\frac{\epsilon}{|A|})e^{0}+\frac{(|A|-1)\epsilon}{|A|}\xi^{\alpha},$

and therefore

$Z(s,m)-Z(s,m_{Main})=\frac{\epsilon}{|A|}\big{(}\xi^{\frac{\beta-1}{\beta}\alpha}+\xi^{\frac{\alpha}{\beta}}-\xi^{\alpha}-1\big{)}\\\
+(1-\epsilon)(-1+\xi^{\frac{\alpha}{\beta}}).$

Since $\alpha>0$ and $\beta>1$, we can find $\xi>0$ such that

$\frac{\epsilon}{|A|}\big{(}\xi^{\frac{\beta-1}{\beta}\alpha}+\xi^{\frac{\alpha}{\beta}}-\xi^{\alpha}\big{)}+(1-\epsilon)(\xi^{\frac{\alpha}{\beta}})<\frac{\epsilon}{|A|}.$

So we have

$Z(s,m)-Z(s,m_{Main})<\epsilon-1<0,$

and therefore

$F^{*}(s,m_{Main})<F^{*}(s,m),$

so if the optimal policy for a subspace differs from the main space, the
algorithm selects the main space. Since the agent finally uses the main space
and it explores all actions in all states infinitely, it finally finds the
true value for all state-actions and converges to the optimal policy.

##  Appendix B Settings of 2-D Maze Environment

In this environment, the state of the agent is its 2D position and it changes
its position using four actions. If there is a barrier in the new position,
the agent remains in the current location and gets reward RW. The agent
obtains reward RS for taking each action. If the agent reaches the goal, it
gets reward RG [18]. The distribution of these immediate rewards are shown in
Table I.

TABLE I: Distribution of the rewards for different scenarios in the 2D maze task [18]. Symbol | Distribution
---|---
RW | $\sim\frac{1}{3}\mathcal{N}(-11.5,0.2)+\frac{2}{3}\mathcal{N}(-10.5,0.3)\;\in[-12,-10]$
RG | $\sim N(+10,0.02)\;\in[9.5,11.5]$
RS | $\sim\frac{1}{3}\mathcal{N}(-1.5,0.2)+\frac{2}{3}\mathcal{N}(-0.5,0.3)\;\in[-2,0]$

##  Appendix C Settings of Real-Time Strategy Game StarCraft:Broodwar

In this environment, state of the agent is its 2D position and its hitpoint
and the enemies hitpoints. It has the folowing abstract actions: moving toward
an enemy, retreating to the starting state, and shooting to each enemy. The
agent’s goal is to eliminate all enemies. The reward for doing action $a$ from
state $s$ and going to state $s^{\prime}$ is computed by the following
relation [18]:

$r=10\times\left(\sum_{i=1}^{\\#\text{enemies}}\left(HP_{i}-HP^{\prime}_{i}\right)-\left(HP-
HP^{\prime}\right)\right)+r_{a}-1,$ (27)

where $HP_{i}$ and $HP^{\prime}_{i}$ are the hitpoints of the ith enemy, where
the agent is in states $s$ and $s^{\prime}$, respectively. $HP$ and
$HP^{\prime}$ denote the agent hitpoints in $s$ and $s^{\prime}$,
respectively. $r_{a}$ is the extra reward that is given to the agent when it
shoots a killed enemy (RA), when it hits to the wall (RW) and when it attains
the goal of killing all enemies (RG). The distribution of $r_{a}$ is shown in
Table II.

TABLE II: Distribution of the rewards for SC:BW task [18]. Symbol | Distribution
---|---
RA | $\sim N(-10,0.1),\;\in[-11,-9]$
RW | $\sim\frac{1}{3}\mathcal{N}(-1.5,0.2)+\frac{2}{3}\mathcal{N}(-0.5,0.3),\;\in[-2,0]$
RG | $\sim\frac{1}{3}\mathcal{N}(97,0.2)+\frac{2}{3}\mathcal{N}(100,0.15),\;\in[95,105]$

##  Appendix D Settings of Countinuous Maze Environment

In this environment, the state of the agent is the proximity of its nine eyes
to walls, foods, and poisons. Its actions are moving toward five different
directions in the continuous maze. If it collides with poisons or foods, it
digests them. The reward of doing action $a$ is computed as follows

$r=R_{P}+R_{SF}+R_{D},$ (28)

where $R_{P}$ is the average of proximity to a wall for different eyes and the
distance is normalized by dividing by the maximum possible proximity. $R_{SF}$
is the straight forward reward to make the agent walk in a straight line. If
the agent takes the forward action and $R_{P}>0.75$, $R_{SF}=0.1R_{P}$,
otherwise $R_{SF}=0$. $R_{D}$ is the digestion reward. If the agent eats a
food, $R_{D}=5$, and if it eats a poison, $R_{D}=-6$.