# Blind Decision Making: Reinforcement Learning with Delayed Observations

Mridul Agarwal, Vaneet Aggarwal The authors are with Purdue University, West
Lafayette IN 47907, USA<EMAIL_ADDRESS>
###### Abstract

Reinforcement learning typically assumes that the state update from the
previous actions happens instantaneously, and thus can be used for making
future decisions. However, this may not always be true. When the state update
is not available, the decision taken is partly in the blind since it cannot
rely on the current state information. This paper proposes an approach, where
the delay in the knowledge of the state can be used, and the decisions are
made based on the available information which may not include the current
state information. One approach could be to include the actions after the
last-known state as a part of the state information, however, that leads to an
increased state-space making the problem complex and slower in convergence.
The proposed algorithm gives an alternate approach where the state space is
not enlarged, as compared to the case when there is no delay in the state
update. Evaluations on the basic RL environments further illustrate the
improved performance of the proposed algorithm.

##  I Introduction and Related Work

A reinforcement learning (RL) agent models the world into states, which come
from the set $\mathcal{S}$. The agent, at time $t$ and in state $s_{t}$,
chooses an action $a_{t}\in\mathcal{A}$. After choosing an action, the agent
receives a reward $r_{t}$ and moves to state $s_{t+1}$ at the next time step
$t+1$. The goal of the agent is to find a policy to select an action that
maximizes the total cumulative reward the agent collects over $T$ time steps,
where $T$ may be unbounded [16]. Applications of RL are continuously
increasing in domains that can be formulated using state, action, and rewards.
Many such applications include cloud scheduling [2], robot manipulation [5],
financial trading [6], and microgrid management [11]. However, many of these
works assume that the state update is immediately observed after the action is
played, which may not be true in general applications. This paper proposes an
algorithm and evaluates it when the state updates are not immediately
available.

We note that in many applications, the state update information is not
available instantaneously. As an example, micro-grid control may have
stochastic delays because of the communication link and these delays may have
adverse impact on the system [12]. The authors of [4] studied the impact of
delays in video scheduling for mobile devices. For a mobile device, channel
state information might be delayed since the streaming decisions are made many
seconds before the content is played (to reduce the rebuffering events), which
impacts the video streaming algorithms using RL based control. 360-degree
video streaming further adds a challenge by introducing different qualities in
different tiles in a frame, and thus the head movement prediction can be used
for efficient streaming [7]. However, the head position while viewing a frame
is not available for the streaming algorithm, which makes the decision before
the content is played and is thus making decisions without the current state
information. Similarly, cloud-based scheduling will observe stragglers only
after a certain time threshold, and network delays may cause financial losses
in trading. Delays can also arise from processing delays on input images or
computationally complex data processing. The issue of such delay in the
availability of state information limits the use of RL for practical
applications [13].

As studied by [10], delays may be of three types, 1) observation delays, where
observations for state updates are delayed, 2) action delays, where actions
may take effect after a certain delay, and 3) cost/reward delays, where
rewards are not obtained till certain time after an action is taken in any
state. They show that action delays are equivalent to observation delays. If
observations are delayed then the agent plays action with knowledge of the
last observed state and the actions happened in the meantime. Similarly, if
actions are delayed, the agent schedules actions for the future with the same
information. In case of delays in rewards updates, algorithms train using
mini-batches where a mini-batch consists of state observations, actions taken,
and available rewards received for some duration. We note that even though the
current state information is not known, the decisions still have to be made.
In this paper, we assume only observation or action delays. We further assume
that rewards are provided to the agent along with state updates.

The authors of [1] showed that for Markov Decision Process (MDP) where each
observation is delayed by $d$ steps, an equivalent MDP can be constructed with
an augmented state space where previous $d$ actions are appended to the
currently known state. Thus, the new state space
$\mathcal{S}^{\prime}=\mathcal{S}\times\mathcal{S}^{d}$ with
$s_{t}^{\prime}=(s_{t-d},a_{t-d},a_{t-(d-1)},\cdots,a_{t-1})$. This
formulation restores the problem structure back to an MDP, and any RL
algorithm can now be applied to the new MDP. We point to three limitations of
this approach.

The first limitation is that this approach does not scale to stochastic
delays. In order to resolve this, [10] proposed a new solution by assuming
that the maximum delay is bounded. They assume that if the delays are more
than a threshold $n$, then the algorithm freezes, and would not take any
action. However, many real-time systems might not enjoy this liberty of
freezing the execution of the algorithm.

The second limitation is that the expansion of the state space might not be
efficient for implementation because of the increased storage complexity and
exponentially larger time to converge to the optimal solution. In order to
alleviate this, the authors of [18] proposed an algorithm to play action
$a_{t}$ which is optimal for the state in which the agent is most likely in,
or $a_{t}=\arg\max_{a_{t}}Q(\arg\max{p_{s_{t}}(s_{t}}|s^{\prime}_{t}),a_{t})$.
It was assumed that the probability of not being in the most likely state is
bounded by $\epsilon$, where $\epsilon$ is small enough. Note that for Markov
Decision Process (MDP) where state distributions are not concentrated, this
assumption might not hold.

The third limitation for augmenting the state space is that the regret
analysis of the MDP shows that the regret of this algorithm scales as
$|\mathcal{A}|^{d/2}$, where $d$ is the delay in the availability of the state
information [8]. For large $d$, the gap may be large enough for the approach
to have significantly decreased performance.

Having pointed out the limitations in the prior works, we propose a solution
that aims to alleviate these issues. The proposed algorithm, called
Expectation-Maximization Q-learning (EMQL), takes an action that maximizes the
expected gain of true MDP across all possible states conditioned over the last
known state $s_{t-d}$, and actions taken till time $t$. EMQL for delayed
reinforcement learning has the following properties:

  * •

Space efficient: The proposed algorithm does not use an augmented MDP to
determine the action. It, however, uses the fact the current true state comes
from the probability distribution generated by augmented MDP.

  * •

Robust under deviation from most likely state: The algorithm selects the
action that maximizes the expected value $Q$ function. Thus, even though the
distribution is not concentrated around a single state, the distribution is
efficiently utilized.

  * •

Handles stochastic delays: The algorithm works well with stochastic delays, as
well as missed information.

EMQL is evaluated on Frozen Lake ($8\times 8grid)$, and Cart Pole environments
of OpenAI Gym platform [3]. The results for delayed settings are compared with
Extended MDP formulation of [1], MBS algorithm given by [18], and dQ algorithm
proposed by [15] respectively. The metric of comparison is the total reward,
collected in each episode.

The rest of the paper is organized as follows. Section II defines the problem
under consideration. Section IV presents the proposed algorithm. Evaluation
and comparison results are presented in section V. Section VI concludes the
paper with a brief discussion.

##  II Formulation

We consider a Markov Decision Process $\mathcal{M}$, with set of states
denoted by $\mathcal{S}$, and set of actions denoted by $\mathcal{A}$. At time
$t$, the environment is in state $s_{t}\in\mathcal{S}$. The definitions are
mostly consistent with those in [16, 14]

At any time $t$, the agent chooses action $a_{t}\in\mathcal{A}$ based on its
knowledge about the current state. On playing the action $a_{t}$, environment
rewards the agent with $R_{t}$, which is random variable conditioned on
environment state $s_{t}$, and action chosen by agent at time $t$. The maximum
reward the agent can receive at any time step is $R_{max}$. The goal of the
agent is to maximize the discounted cumulative rewards it receives. The
discount factor $\gamma\in[0,1)$ denotes the importance of future rewards.

$\displaystyle\mathcal{R}$ $\displaystyle=\sum_{t=0}^{\infty}\gamma^{t}R_{t}$
(1)

Expected reward when action $a$ is taken in a state $s$ is defined as $r(s,a)$

$\displaystyle r(s,a)=\mathbb{E}\left[R_{t}|s_{t}=s,a_{t}=a\right]$ (2)

The probability distribution of next state $s_{t+1}$ conditioned on current
state $s_{t}$ and action $a_{t}$ is denoted by $p(s_{t},a_{t},s_{t+1})$.
Shorthand notation by dropping the subscripts is denoted as,

$\displaystyle p(s,a,s^{\prime})$
$\displaystyle=P(s_{t+1}=s^{\prime}|s_{t}=s,a_{t}=a)$ (3)

Agent uses a policy $\pi$ to select an action. $\pi$ is defined as the
probability distribution over actions given the state.

$\displaystyle\pi(a|s)=\mathbb{P}(a_{t}=a|s_{t}=s)$ (4)

The value function $V^{\pi}(s)$ of a state $s$ is defined as the expected
value of sum of discounted rewards which agent can receive over time starting
from state $s$ and choosing actions according to the policy $\pi$.

$\displaystyle V^{\pi}(s)$
$\displaystyle=\mathbb{E}_{\pi}\left[\sum_{t=t_{0}}^{\infty}\gamma^{t-t_{0}}R_{t}\Big{|}s_{t_{0}}=s\right]$
(5)

This makes the maximum possible value of $V^{\pi}(s)$ as
$\frac{R_{max}}{1-\gamma}$. Similarly action-value function $Q^{\pi}(s,a)$ is
defined as the expected cumulative rewards which agent receives in state $s$
on taking action $a$ and then following policy $\pi$,

$\displaystyle Q^{\pi}(s)$
$\displaystyle=\mathbb{E}_{\pi}\left[\sum_{t=t_{0}}^{\infty}\gamma^{t-t_{0}}R_{t}\Big{|}s_{t_{0}}=s,a_{t_{0}}=a\right]$
(6)

For both value function $V^{\pi}(s)$ and action-value function $Q^{\pi}(s,a)$
the expectation is taken over the states which are distributed according to
the transition dynamics of the MDP $\mathcal{M}$ and actions which are
distributed according to the policy $\pi$. We use only $\pi$ in the subscript
for expectation as we can only control the policy. Optimal policy $\pi^{*}$ is
defined as the policy which maximizes the value function for all states.

$\displaystyle V^{*}(s)$ $\displaystyle=V^{\pi^{*}}(s)$ (7)
$\displaystyle=\sup_{\pi}V^{\pi}(s)\ \ \ \forall\ s\in\mathcal{S}$ (8)

The optimal policy $\pi^{*}$ gives an optimal value function $V^{*}$ and an
optimal Q-function $Q^{*}$, which are related as

$\displaystyle Q^{*}(s,a)$
$\displaystyle=\mathbb{E}_{\pi}\left[r(s_{t},a_{t})\right]+\gamma\mathbb{E}\left[V^{*}(s_{t+1})|s_{t}=s,a_{t}=a\right]$
(9) $\displaystyle V^{*}(s)$ $\displaystyle=\max_{a\in\mathcal{A}}Q^{*}(s,a)\
\ \ \forall\ s\in\mathcal{S}$ (10)

In practical RL algorithms, agent deploys some strategy to calculate an
estimate of Q-function $\hat{Q}$. Some common strategies are discussed in
[16]. The agent selects the action greedily based on the estimate of
Q-function $\hat{Q}$ as

$\displaystyle a_{t}=\arg\max_{a_{t}\in\mathcal{A}}\hat{Q}(s_{t},a_{t})$ (11)

The delay $\Delta$ is a random variable denoting the delay of the system. All
realizations of delay $d$ are assumed to be a non-negative integer. At time
$t$, the last known state for the agent is $s_{t-d}$. The actions played in
$d$ time steps are $a_{t-d},a_{t-(d-1)},\cdots,a_{t-1}$.

We assume that at the beginning of any episode, all the delayed observations
of previous episodes are available. This also means that the observations from
any of the previous episodes are not corrupting the observations received in
current episode.

##  III Proposed Policy and Bounds

For a system with $d$ delays, we construct an extended MDP
$\widetilde{\mathcal{M}}$ which has state $\tilde{s}_{t}$ as
$(s_{t-d},a_{t-d},a_{t-(d-1)},\cdots,a_{t-1})$. The two MDPs
$\widetilde{\mathcal{M}}$, and $\mathcal{M}$ share the same action space
$\mathcal{A}$, so we will not change the notation for actions. For everything
else we will put a tilde over the variables for the augmented MDP. The policy
$\tilde{\pi}$ now selects an action based on $\tilde{s}$ or the tuple
$(s_{t-d},a_{t-d},a_{t-(d-1)},\cdots,a_{t-1})$. The corresponding Q-function
for a policy $\tilde{\pi}$ over $\widetilde{\mathcal{M}}$ becomes,

$\displaystyle\widetilde{Q}^{\tilde{\pi}}(\tilde{s},a)$
$\displaystyle=\mathbb{E}_{\tilde{\pi}}\left[R_{t}|\tilde{s}_{t}=\tilde{s},a_{t}=a\right]+$
$\displaystyle\gamma\sum_{\tilde{s}_{t+1}\in\mathcal{\widetilde{S}}}\widetilde{V}^{\tilde{\pi}}(\tilde{s}_{t+1})\mathbb{P}\left[\tilde{s}_{t+1}|\tilde{s}_{t}=\tilde{s},a_{t}=a\right]$
(12)

Using this construction we present the key lemma based on which we construct
our policy.

###### Lemma 1

Expected reward obtained by agent in augmented state $\tilde{s}_{t}$ by taking
an action $a$, is related to the true state $s_{t}$ of environment as

$\displaystyle\tilde{r}(\tilde{s}_{t},a)$
$\displaystyle=\sum_{s\in\mathcal{S}}r(s,a)p(s|\tilde{s}_{t})$ (13)

###### Proof 1

Reward $R_{t}$ generated by the environment is oblivious to the state
maintained by the agent. The expected reward for the agent is
$\tilde{r}(\tilde{s}_{t},a)$

$\displaystyle\tilde{r}(\tilde{s},a)$
$\displaystyle=\mathbb{E}\left[R_{t}|\tilde{s}_{t}=\tilde{s},a_{t}=a\right]$
(14)
$\displaystyle=\sum_{s\in\mathcal{S}}\mathbb{E}\left[R_{t}|s_{t}=s,\tilde{s}_{t}=\tilde{s},a_{t}=a\right]\mathbb{P}(s_{t}=s|\tilde{s}_{t}=\tilde{s})$
$\displaystyle=\sum_{s\in\mathcal{S}}\mathbb{E}\left[R_{t}|s_{t}=s,a_{t}=a\right]\mathbb{P}(s_{t}=s|\tilde{s}_{t}=\tilde{s})$
(15)

Equality (15) follows from the fact that reward does not depend on the state
maintained by agent, but on the environment’s state.

Lemma 1 states that the expected reward received on taking action $a$ in state
$\tilde{s}$ is the expected reward received by taking action $a$ in the
unobserved stated conditioned on $\tilde{s}$. Based on Lemma 1, a myopic
policy, which maximizes immediate expected return for the agent, selects
greedy action $a_{t}(\tilde{s})$ as

$\displaystyle
a_{t}=\arg\max_{a\in\mathcal{A}}\left(\mathbb{E}_{s}\left[R(s,a)|\tilde{s}_{t}\right]\right)$
(16)

Inspired by the myopic policy, we now propose a policy for working with
delayed state updates.

The agent would be able to maximize its expected discounted cumulative rewards
if it has oracle access which could return the optimal action for unobserved
current state $s_{t}$ of the environment. However, since such oracle access is
not available, we settle for a policy that assumes that the state at the next
time step will be available. This policy maximizes the sum of immediate reward
and the expected value of the next state under the optimal policy for
$\mathcal{M}$, or

$\displaystyle\tilde{\pi}(a_{t}|\tilde{s}_{t})=\begin{cases}1,&\text{if
}a_{t}=\arg\max_{a\in\mathcal{A}}\mathbb{E}\left[Q^{*}(s,a)|\tilde{s}_{t}\right],\\\
0,&\text{otherwise }\end{cases}$ (17)

The following theorem provides bounds on minimum value an augmented state
$\tilde{s}\in\widetilde{\mathcal{S}}$ would fetch for the agent. That is,
value function using the policy defined in Equation (17) ensures the minimum
value given in Theorem 1.

###### Theorem 1

If the agent follows policy as given in (17), for an augmented MDP
$\widetilde{\mathcal{M}}$, then the value of each state
$\tilde{s}\in\widetilde{\mathcal{S}}$ satisfies the following lower bound,

$\displaystyle\widetilde{V}^{\tilde{\pi}}(\tilde{s})$
$\displaystyle\geq\mathbb{E}_{s|\tilde{s}}\left[{V}^{\pi^{*}}(s)\right]-\frac{R_{max}}{(1-\gamma)^{2}}\left(1-\frac{1}{|\mathcal{A}|}\right)$
(18)

where $\pi^{*}(a_{t}|s_{t})$ is oracle aided policy which gives the optimal
action for true MDP $\mathcal{M}$.

###### Proof 2

We first mention and prove the lemmas required for the proof, and then
continue to the final proof. Lemma 2 relates the value function for
$\mathcal{M}$ and $\widetilde{\mathcal{M}}$ under same policy $\tilde{\pi}$.
Lemma 3 relates expected value using the oracle aided policy and the state-
action value using oracle aided policy.

###### Lemma 2

Value function of a policy $\tilde{\pi}(a|\tilde{s})$ for augmented MDP
$\tilde{\mathcal{M}}$ is related to value function for same policy under true
MDP $\mathcal{M}$ is related as

$\displaystyle\tilde{V}^{\tilde{\pi}}(\tilde{s})$
$\displaystyle=\mathbb{E}_{s}\left[V^{\tilde{\pi}}(s)|\tilde{s}\right]$ (19)

where $V^{\tilde{\pi}}(s)$ is value function for policy $\tilde{\pi}$ with MDP
$\mathcal{M}$.

###### Proof 3

Note that the value function for the augmented MDP $\tilde{\mathcal{M}}$ is
expected cumulative discounted rewards collected by the agent when it starts
from state $\tilde{s_{t}}$, and follows a policy $\tilde{\pi}$. Thus from the
definition of $\tilde{V}^{\tilde{\pi}}(\tilde{s})$, we have

$\displaystyle\tilde{V}^{\tilde{\pi}}(\tilde{s})$
$\displaystyle=\mathbb{E}_{\tilde{\pi}}\left[\sum_{k=0}^{\infty}\gamma^{t+k}R_{t+k}|\tilde{s}_{t}=\tilde{s}\right]$
(20)
$\displaystyle=\sum_{k=0}^{\infty}\gamma^{k}\mathbb{E}_{\tilde{\pi}}\left[R_{t+k}|\tilde{s}_{t}=\tilde{s}\right]$
(21)
$\displaystyle=\sum_{k=0}^{\infty}\gamma^{k}\mathbb{E}_{\tilde{\pi}}\left[R_{t+k}|s_{t+k},a_{t+k}\right]\mathbb{P}\left[s_{t+k}|\tilde{s}_{t},\tilde{\pi}\right]$
(22)
$\displaystyle=\sum_{k=0}^{\infty}\gamma^{k}\mathbb{E}_{\tilde{\pi}}\left[R_{t+k}|s_{t+k},a_{t+k}\right]\sum_{s_{t}\in\mathcal{S}}\mathbb{P}\left[s_{t+k}|s_{t},\tilde{\pi}\right]\mathbb{P}\left[s_{t}|\tilde{s}_{t}\right]$
(23)
$\displaystyle=\sum_{s_{t}\in\mathcal{S}}\left(\sum_{k=0}^{\infty}\gamma^{k}\mathbb{E}_{\tilde{\pi}}\left[R_{t+k}|s_{t+k},a_{t+k}\right]\mathbb{P}\left[s_{t+k}|s_{t},\tilde{\pi}\right]\right)\mathbb{P}\left[s_{t}|\tilde{s}_{t}\right]$
$\displaystyle=\sum_{s_{t}\in\mathcal{S}}V^{\tilde{\pi}}(s)\mathbb{P}\left[s_{t}|\tilde{s}_{t}\right]$
(24)

Equation (22) follows from Lemma 1. Equation (23) follows the fact that if the
agent knew the true state and followed the policy $\tilde{\pi}$, then the
environment state evolution probabilities would remain the same.

###### Lemma 3

For the optimal policy $\pi^{*}$, and distribution over initial state $s$,
$\mu$,

$\displaystyle\arg\max_{a}\mathbb{E}_{s\sim\mu}\left[Q^{*}(s,a)\right]\geq\frac{1}{\mathcal{A}}\mathbb{E}_{s\sim\mu}\left[V^{*}(s)\right]$
(25)

###### Proof 4

Let initial state follow some distribution $\mu$, or
$\mathbb{P}\left[s_{t}=s\right]\sim\mu$. Then we have,

$\displaystyle\mathbb{E}_{s\sim\mu}\left[V^{*}(s)\right]$
$\displaystyle=\mathbb{E}_{s\sim\mu}\left[\max_{a}Q^{*}(s,a)\right]$ (26)
$\displaystyle\leq\mathbb{E}_{s\sim\mu}\left[\sum_{a\in\mathcal{A}}Q^{*}(s,a)\right]$
(27)
$\displaystyle=\sum_{a\in\mathcal{A}}\mathbb{E}_{s\sim\mu}\left[Q^{*}(s,a)\right]$
(28)
$\displaystyle\leq|\mathcal{A}|\max_{a\in\mathcal{A}}\mathbb{E}_{s\sim\mu}\left[Q^{*}(s,a)\right]$
(29)

We can now use Lemma 2, Lemma 6.1 from [9] and Lemma 3 to find the minimum
value of
$\widetilde{V}^{\tilde{\pi}}(\tilde{s})-\mathbb{E}_{s}\left[V^{\pi^{*}}(s)|\tilde{s}\right]$.
Mathematically we have,

$\displaystyle\tilde{V}^{\tilde{\pi}}(\tilde{s})-\mathbb{E}_{s}\left[V^{\pi^{*}}(s)|\tilde{s}\right]=\mathbb{E}_{s}\left[V^{\tilde{\pi}}(s)|\tilde{s}\right]-\mathbb{E}_{s}\left[V^{\pi^{*}}(s)|\tilde{s}\right]$
(30)
$\displaystyle=\mathbb{E}_{s|\tilde{s},s_{t+1},a_{t}\sim\tilde{\pi}}\left[\sum_{k=0}^{\infty}\gamma^{k}{Q}^{\pi^{*}}(s_{t+k},a_{t+k})-{V}^{\pi^{*}}(s_{t+k})\right]$
(31)
$\displaystyle=\sum_{k=0}^{\infty}\gamma^{k}\mathbb{E}_{s|\tilde{s},s_{t+1},a_{t}\sim\tilde{\pi}}\left[{Q}^{\pi^{*}}(s_{t+k},a_{t+k})\right]$
$\displaystyle\ \ \ \
-\mathbb{E}_{s|\tilde{s},s_{t+1},a_{t}\sim\tilde{\pi}}\left[{V}^{\pi^{*}}(s_{t+k})\right]$
(32)
$\displaystyle\geq\sum_{k=0}^{\infty}\gamma^{k}\frac{1}{|\mathcal{A}|}\mathbb{E}_{s|\tilde{s},s_{t+1},a_{t}\sim\tilde{\pi}}\left[{V}^{\pi^{*}}(s_{t+k})\right]$
$\displaystyle\ \ \ \
-\mathbb{E}_{s|\tilde{s},s_{t+1},a_{t}\sim\tilde{\pi}}\left[{V}^{\pi^{*}}(s_{t+k})\right]$
(33)
$\displaystyle\geq\sum_{k=0}^{\infty}\gamma^{k}\left(\frac{1}{|\mathcal{A}|}-1\right)\mathbb{E}_{s|\tilde{s},s_{t+1},a_{t}\sim\tilde{\pi}}\left[{V}^{\pi^{*}}(s_{t+k})\right]$
(34)
$\displaystyle\geq\sum_{k=0}^{\infty}\gamma^{k}\left(\frac{1}{|\mathcal{A}|}-1\right)\frac{R_{max}}{1-\gamma}=\left(\frac{1}{|\mathcal{A}|}-1\right)\frac{R_{max}}{(1-\gamma)^{2}}$
(35)

Equation (30) follows from Lemma 2, and Equation (31) comes from using Lemma
6.1 from [9]. Equation (33) comes from the fact that $a_{t+k}$ is chosen from
the policy defined in Equation (17) for all $k\geq 0$, and Lemma 3. Equation
(35) follows from maximum possible value of $V^{\pi}(s)$.

Theorem 1 states that the proposed policy can suffer a maximum degradation of
$\left(\frac{1}{|\mathcal{A}|}-1\right)\frac{R_{max}}{(1-\gamma)^{2}}$ only
from the expected optimal value of unobserved state conditioned on the
extended state.

Now, the task that remains is to find $Q^{*}$ for true MDP. We assume that the
delayed state observations can be identified using timestamp or index header.
This is a common engineering principle in communication networks to deal with
asynchronous packets [17], and hence it is a valid assumption. This allows to
find optimal Q-function for true MDP $\mathcal{M}$. We next provide a detailed
algorithm for the policy described in this section.

##  IV Algorithm

We now utilize Equation (17) to construct Expectation Maximization Q Learning
(EMQL) algorithm (described in Algorithm 1) which is space efficient and which
can handle stochastic delays. We note that to calculate the expected Q-value
function, we require an algorithm to calculate and store the Q values for each
state-action pair. Also the algorithm requires to estimate and store the state
transition probabilities to calculate the expected Q value for Equation (17).
For this, we divide our algorithm into two parts. First part (Algorithm 1)
keeps a track of visited state-action pairs, and observed next states and
rewards to calculate the Q-value table and the probability transition matrix.
Second part is an auxiliary algorithm (Algorithm 2) which actually implements
the policy of Equation (17) using the Q-value table and probability transition
matrix of the first part.

###  IV-A Algorithm Construction

The algorithm takes the state space $\mathcal{S}$, action space $\mathcal{A}$,
discount factor $\gamma$, and exploration factor $\epsilon_{t}$ as inputs.
Since, we consider a model based algorithm, we maintain variables
corresponding to number of times a state-action pair was visited
$(N(\cdot,\cdot))$, rewards obtained for the state-action pair
$(R(\cdot,\cdot))$, and the counter for next state from a state-action pair to
calculate the estimates of probability transitions $(P(\cdot,\cdot,\cdot))$.

Before beginning any episode the algorithm calculates the estimated
probability transitions $(\hat{p}(\cdot,\cdot,\cdot))$ and the expected
rewards $(\hat{r}(\cdot,\cdot))$ according the equations (40) and (41)
respectively. It then updates the Q-function $(Q(\cdot,\cdot))$ for the true
MDP as per the equation (42). The Q-function learned is for $\mathcal{M}$,
which converges faster because of the smaller state space.

In each episode, the algorithm follows an $\epsilon$-greedy approach for
exploration. It generates a random number $\mathbb{X}$ from uniform
distribution over $[0,1]$. If the random number generated is less than
$\epsilon_{t}$, it plays action randomly uniformly from the action space
$\mathcal{A}$. Else the algorithm uses the auxiliary algorithm Get_EMQL_Action
to determine the action to be played using the proposed policy of Equation
(17) in Section III. After playing an action, if a new observation is
available to the algorithm, it updates the following parameters - the number
of times state $s$ was visited and action $a$ was taken in $s$ $N(s,a)$,
number of times $s^{\prime}$ was observed as the next state
$P(s,a,s^{\prime})$, and reward observed for the state action pair $R(s,a)$.

Get_EMQL_Action is presented in Algorithm 2, and is described in subsection
IV-B. If the current state is available, the expected Q-function becomes the
true Q function. Thus Algorithm 1 evaluates Q-value table and probability
estimates, and Algorithm 2 computes the expected Q-value for Equation (17).
Last line of Algorithm 2 then returns the action which maximizes the expected
Q-value for the proposed policy. We further note that as the estimates of
transition probabilities and Q-values are improved by the Algorithm 1, the gap
between the value of the proposed policy and the expected optimal value of the
unobserved state can be bounded by Theorem 1.

###  IV-B Complexity

At each time step $t$, Algorithm 2 computes the expected value of the
Q-function whenever an action needs to be taken. This requires
$\mathcal{O}\left(d|\mathcal{S}|^{2}+\log\left(|\mathcal{A}|\right)\right)$
computations. For our algorithm, we calculate the probability vector
${\bf\bar{p}}$ which is the conditional probability distribution of the states
given the last known state $s_{t-d}$, and the sequence of actions
$a_{t-d},\cdots,a_{t-1}$. For time $t-d$, the true state is known and
conditional probability becomes

$\displaystyle{\bf\bar{p}}_{t-d}(s)$
$\displaystyle=\Bigg{\\{}\begin{array}[]{@{}cl}1,&s=s_{t-d},\\\
0,&otherwise\end{array}$ (38)

Then, for each next time step, the probability vector is updated using the
following recursion equation.

$\displaystyle{\bf\bar{p}}_{t-k}$
$\displaystyle=\left(\hat{p}(:,a_{t-(d-k)},:)\right)^{T}{\bf\bar{p}}_{t-k-1}\
\forall\ s\in\mathcal{S},\forall\ 1\leq k<d$ (39)

where $\hat{p}(:,a_{t-k-1},:)$ is the state transition matrix of MDP
$\mathcal{M}$ induced by action $a_{t-k-1}$. $\hat{p}(:,a_{t-k-1},:)$ is
obtained using Equation (40). Since we do this update $d$ times, and each
matrix multiplication costs $\mathcal{O}\left(|\mathcal{S}|^{2}\right)$, the
total complexity to compute the state probability at each time step $t$
becomes $\mathcal{O}\left(d|\mathcal{S}|^{2}\right)$. Fetching the maximum
element cost extra $\mathcal{O}\left(\log\left(|\mathcal{A}|\right)\right)$.
The overall complexity at any time step $t$ thus becomes
$\mathcal{O}\left(d|\mathcal{S}|^{2}+\log\left(|\mathcal{A}|\right)\right)$.

Input: $\mathcal{S}$, $\mathcal{A}$, $\gamma$, $\epsilon_{t}$

for $s\in\mathcal{S}$ do

for $a\in\mathcal{A}$ do

$\hat{p}(s,a,s^{\prime})=0,\hat{r}(s,a)=0$

$P(s,a,s^{\prime})=0,N(s,a)=0$

$R(s,a)=0,Q(s,a)=0$

end for

end for

while 1 do

for $s\in\mathcal{S}$ do

for $a\in\mathcal{A}$ do

Update probability and reward estimates
$\displaystyle\hat{p}(s,a,s^{\prime})$
$\displaystyle=\frac{P(s,a,s^{\prime})}{\max{(1,N(s,a))}}$ (40)
$\displaystyle\hat{r}(s,a)$ $\displaystyle=\frac{R(s,a)}{\max{(1,N(s,a))}}$
(41)

end for

$V(s)=\max_{a}Q(s,a)$

end for

for $s\in\mathcal{S}$ do

for $a\in\mathcal{A}$ do

Update Q function  $\displaystyle
Q(s,a)=\hat{r}(s,a)+\sum_{s^{\prime}\in\mathcal{S}}\gamma
V(s^{\prime})\hat{p}(s,a,s^{\prime})$ (42)

end for

end for

$t=0$

for $t=1,2,\cdots$ do

$t+=1$

Known STATE $s_{t-d}$

if $\mathbb{X}\sim U(0,1)<\epsilon_{t}$ then

play $a_{t}$ randomly uniFORmly from $\mathcal{A}$

else

play $a_{t}$ = Get_EMQL_Action$\left(s_{t-d},a_{t-d},\cdots,a_{t-1}\right)$

end if

if Observation $(s_{t-(d-1)},r_{t-(d-1)})$ available then

$R(s_{t-d},a_{t-d})\ +=r_{t-(d-1)}$

$P(s_{t-d},a_{t-d},s_{t-(d-1)})\ +=1$

$N(s_{t-d},a_{t-d})\ +=1$

end if

end for

end while

Algorithm 1 Expectation Maximization Q-Learning (EMQL)

Input: $\mathcal{S}$, $\mathcal{A}$, $\hat{p}$, $Q$,
$\left(s_{t-d},a_{t-d},\cdots,a_{t-1}\right)$

Output: Estimated greedy action $a_{t}$

${\bf\bar{p}}=[0,\cdots,0]$, vector of length $|\mathcal{S}|$

${\bf\bar{p}}[s_{t-d}]=1$

for $0\leq k<d$ do

${\bf\bar{p}}=\left(\hat{p}(:,a_{t-(d-k)},:)\right)^{T}{\bf\bar{p}}$

end for

${\bf\bar{Q}}={\bf\bar{p}}^{T}Q$

Return $\arg\max_{a}{\bf\bar{Q}}$

Algorithm 2 Get_EMQL_Action

##  V Evaluation

We evaluate our algorithm EMQL on OpenAI Gym platform [3]. We consider the
standard Frozen Lake ($8\times 8$ grid), and Cart Pole problem of OpenAI Gym
which is as per the description in [16]. Frozen Lake environment has a
discrete state space and Cart Pole environment has continuous state space with
discrete action space.

We compare our algorithm with Extended MDP formulation by [1], Model Based
Simulation (MBS) algorithm of [18], and dQ algorithm of [15] for constant
delays. We also compare the proposed EMQL algorithm with MBS algorithm for
stochastic delays. The metric of comparison is total cumulative reward
accumulated at the end of each episode averaged over last 50 episodes.
Exploration factor is time dependent and is chosen as
$\epsilon_{t}=\frac{\log{\left(|\mathcal{S}|\sum_{s,a}N(s,a)+1\right)}}{\sum_{a}N(s,a)+1}\
\ \forall s,a$. This choice of exploration factor is same across all
simulations. For stochastic delays, creating an augmented MDP is not feasible
as delays can be arbitrarily large. We considered $50$ iterations of Frozen
Lake environment, and $20$ iterations of Cart Pole environment. Each iteration
is trained over $1000$ episodes.

For constant delays, we chose delays in the range of $d\in\\{2,4\\}$. For
stochastic delays, each observation was independently delayed by delays
generated using a geometric distribution with parameter $p$. The expected
delay for this distribution is $\frac{1}{1-p}$. We note that, this may create
asynchronous observations as delay $d_{1}$ of observation at $t_{1}$ may be
higher than delay $d_{2}$ of observation at $t_{2}$, where
$t_{1}+d_{1}>t_{2}+d_{2}$. The issue of asynchronous delays can be dealt by
introducing time stamps in observations.

###  V-A Results

Simulations results based for both Frozen Lake and Cart Pole environment are
presented in Figure 1 for constant delays. For stochastic delays the results
are presented in Figure 2. In both figures, median of rewards in each
iteration is plotted along with the top and bottom quantiles.

$0$$200$$400$$600$$800$$1{,}000$$0$$5\cdot
10^{-2}$$0.1$$0.15$$0.2$EpochRewardEMQL delay = 2MBS delay = 2EMDP delay = 2dQ
delay = 2EMQL delay = 4MBS delay = 4EMDP delay = 4dQ delay = 4 (a) Frozen Lake
environment

$0$$200$$400$$600$$800$$1{,}000$$50$$100$$150$EpochRewardEMQL delay = 2MBS
delay = 2EMDP delay = 2dQ delay = 2EMQL delay = 4MBS delay = 4EMDP delay = 4dQ
delay = 4 (b) Cart Pole environment

Figure 1: Reward accumulated by EMQL, MBS, EMDP, and dQ-learning algorithm
with constant delays for Frozen Lake and Cart Pole environments. EMQL achieves
higher average reward per episodes compared to other algorithms.

As observed in Figure 1, total reward per episode is higher for EMQL algorithm
compared to all other algorithms (MBS, dQ, EMDP) in the presence of constant
delays. As delay increases, gap between the rewards also increase between the
two algorithms. For MBS algorithm, this can be reasoned as - with large values
of delays the state with largest likelihood might have lower probability of
occurring.

For dQ algorithm, the reason for increasing difference in accumulated rewards
can be credited to the memoryless algorithm. Also, Extended MDP algorithm is
slow in convergence because of larger state space which grows exponentially.
This reduction in convergence speed is visible in Figure 1b where delay of 4
time steps cause a significant drop in performance of Extended MDP algorithm.

For stochastic delays, the difference between the rewards accumulated by EMQL,
and MBS algorithm increases when the probability of delay increase. For Frozen
Lake environment, the proposed EMQL algorithm doesn’t suffer much degradation
even by increasing the expected delay from $1$ unit to $3$ units. However, MBS
algorithm is not able to achieve similar performance for small expected
delays. In Cart Pole environment, EMQL algorithm beats the MBS algorithm
significantly even when the stochastic delays are geometric distributed with
expected delay of $1$ unit in Figure 2b.

$0$$200$$400$$600$$800$$1{,}000$$0$$0.1$$0.2$$0.3$EpochRewardEMQL delay =
0.5MBS delay = 0.5EMQL delay = 0.75MBS delay = 0.75 (a) Frozen Lake
environment

$0$$200$$400$$600$$800$$1{,}000$$50$$100$$150$EpochRewardEMQL delay = 0.5MBS
delay = 0.5EMQL delay = 0.75MBS delay = 0.75 (b) Cart Pole environment

Figure 2: Reward accumulated by EMQL, MBS algorithms with stochastic delays
for Frozen Lake and Cart Pole environments. EMQL achieves higher average
reward per episodes compared to MBS algorithm when expected delays are high.

##  VI Conclusion

We considered the problem of delays in observation updates for a reinforcement
learning agent. The current state of the environment is not immediately
available to the agent. We proved that the expected immediate rewards
generated for MDP with delays is same as expected immediate rewards generated
for corresponding extended MDP without delays. We proposed a new policy which
can handle stochastic delays by optimizing on optimal Q-function of the true
MDP. We then provided a lower bound on the value function for all states
following the proposed policy. Based on this policy, we proposed a new
algorithm, Expectation Maximization Q-Learning (EMQL), which is robust under
constant, and stochastic delays. Using the knowledge of latest available
state, sequence of actions, estimated transition probabilities, and reward
distributions of the underlying MDP, we determine the best action which
maximizes the expected reward for the unobserved state. Evaluations
demonstrate the improvement over existing algorithms under constant, and
stochastic delays.

## References

  * [1] Eitan Altman and Philippe Nain.  Closed-loop control with delayed information, volume 20.  ACM, 1992.
  * [2] Hamid Arabnejad, Claus Pahl, Pooyan Jamshidi, and Giovani Estrada.  A comparison of reinforcement learning techniques for fuzzy cloud auto-scaling.  In Proceedings of the 17th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, CCGrid ’17, pages 64–73, Piscataway, NJ, USA, 2017. IEEE Press.
  * [3] Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba.  Openai gym.  CoRR, abs/1606.01540, 2016.
  * [4] Nesrine Changuel, Bessem Sayadi, and Michel Kieffer.  Online learning for qoe-based video streaming to mobile receivers.  In 2012 IEEE Globecom Workshops, pages 1319–1324. IEEE, 2012.
  * [5] Ignasi Clavera, Anusha Nagabandi, Simin Liu, Ronald S. Fearing, Pieter Abbeel, Sergey Levine, and Chelsea Finn.  Learning to adapt in dynamic, real-world environments through meta-reinforcement learning.  In International Conference on Learning Representations, 2019.
  * [6] Yue Deng, Feng Bao, Youyong Kong, Zhiquan Ren, and Qionghai Dai.  Deep direct reinforcement learning for financial signal representation and trading.  IEEE transactions on neural networks and learning systems, 28(3):653–664, 2017.
  * [7] Arnob Ghosh, Vaneet Aggarwal, and Feng Qian.  A rate adaptation algorithm for tile-based 360-degree video streaming.  arXiv preprint arXiv:1704.08215, 2017.
  * [8] Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan.  Is q-learning provably efficient?  In Advances in Neural Information Processing Systems, pages 4868–4878, 2018.
  * [9] Sham Kakade and John Langford.  Approximately optimal approximate reinforcement learning.  In ICML, volume 2, pages 267–274, 2002.
  * [10] Konstantinos V Katsikopoulos and Sascha E Engelbrecht.  Markov decision processes with delays and asynchronous cost collection.  IEEE transactions on automatic control, 48(4):568–574, 2003.
  * [11] Elizaveta Kuznetsova, Yan-Fu Li, Carlos Ruiz, Enrico Zio, Graham Ault, and Keith Bell.  Reinforcement learning for microgrid energy management.  Energy, 59:133–146, 2013.
  * [12] Shichao Liu, Xiaoyu Wang, and Peter Xiaoping Liu.  Impact of communication delays on secondary frequency control in an islanded microgrid.  IEEE Transactions on Industrial Electronics, 62(4):2021–2031, 2015\.
  * [13] A Rupam Mahmood, Dmytro Korenkevych, Brent J Komer, and James Bergstra.  Setting up a reinforcement learning task with a real-world robot.  In 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 4635–4640. IEEE, 2018.
  * [14] Martin L Puterman.  Markov decision processes: discrete stochastic dynamic programming.  John Wiley & Sons, 2014.
  * [15] Erik Schuitema, Lucian Buşoniu, Robert Babuška, and Pieter Jonker.  Control delay in reinforcement learning for real-time dynamic systems: a memoryless approach.  In 2010 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 3226–3231. IEEE, 2010.
  * [16] Richard S Sutton and Andrew G Barto.  Reinforcement learning: An introduction.  MIT press, 2018.
  * [17] Jean Walrand and Shyam Parekh.  Communication networks: a concise introduction.  Synthesis Lectures on Communication Networks, 3(1):1–192, 2010\.
  * [18] Thomas J Walsh, Ali Nouri, Lihong Li, and Michael L Littman.  Learning and planning in environments with delayed feedback.  Autonomous Agents and Multi-Agent Systems, 18(1):83, 2009.


1625 LABEL:LastPageMay 01, 2019May 14, 2020

# On the incomputability of computable dimension

Ludwig Staiger  Institut für Informatik
Martin-Luther-Universität Halle-Wittenberg, Germany<EMAIL_ADDRESS>halle.de

###### Abstract.

Using an iterative tree construction we show that for simple computable
subsets of the Cantor space Hausdorff, constructive and computable dimensions
might be incomputable.

Computable dimension along with constructive dimension was introduced by Lutz
[siamcomp/Lutz03, ic/Lutz03] as a means for measuring the complexity of sets
of infinite strings ($\omega$-words). Since then and prior to this
constructive and computable dimension were investigated in connection with
Hausdorff dimension (for a detailed account see [book_DowneyHirsch10, Section
13]). The results of [tocs/Hitch05, ic/St93, tcs/St07] show that the
Hausdorff, constructive and computable dimensions of automaton definable sets
of infinite strings (regular $\omega$-languages) are computable. In contrast
to this Ko [ko98] derived examples of computable $\omega$-languages with an
incomputable Hausdorff dimension.

In this paper we derive examples of computable $\omega$-languages of a simple
structure which have not only incomputable Hausdorff dimension but also
incomputable computable dimension. To this end we use an iteration of finite
trees which resembles the tree construction of Furstenberg [Furstenberg70]
(see also [ciaa/MSS18])

Lutz [siamcomp/Lutz03, ic/Lutz03] defines computable and constructive
dimension via $\sigma$-(super)gales. Terwijn [terwijn04, apal/CST06] observed
that this can also be done using Schnorr’s concept of combining martingales
with (exponential) order functions [book_Schnorr71, Section 17]. For the
computable $\omega$-languages constructed in this paper we can show that
Schnorr’s concept is in some details more precise than Lutz’s approach.

##  1\. Notation

In this section we introduce the notation used throughout the paper. By
$\mathbb{N}=\\{0,1,2,\ldots\\}$ we denote the set of natural numbers, by
$\mathbb{Q}$ the set of rational numbers, and $\mathbb{R}$ are the real
numbers.

Let $X$ be an alphabet of cardinality $|X|\geq 2$. By $X^{*}$ we denote the
set of finite words on $X$, including the empty word $e$, and $X^{\omega}$ is
the set of infinite strings ($\omega$-words) over $X$. Subsets of $X^{*}$ will
be referred to as _languages_ and subsets of $X^{\omega}$ as _$\omega$
-languages_.

For $w\in X^{*}$ and $\eta\in X^{*}\cup X^{\omega}$ let $w\cdot{}\eta$ be
their concatenation. This concatenation product extends in an obvious way to
subsets $W\subseteq X^{*}$ and $B\subseteq X^{*}\cup X^{\omega}$. We denote by
$|w|$ the length of the word $w\in X^{*}$ and $\mathbf{pref}(B)$ is the set of
all finite prefixes of strings in $B\subseteq X^{*}\cup X^{\omega}$.

It is sometimes convenient to regard $X^{\omega}$ as Cantor space, that is, as
the product space of the (discrete space) $X$. Here _open_ sets in
$X^{\omega}$ are those of the form $W\cdot X^{\omega}$ with $W\subseteq
X^{*}$. _Closed_ are sets $F\subseteq X^{\omega}$ which satisfy the condition
$F=\\{\xi:\mathbf{pref}(\xi)\subseteq\mathbf{pref}(F)\\}$.

For a computable domain $\mathcal{D}$, such as $\mathbb{N}$, $\mathbb{Q}$ or
$X^{*}$, we refer to a function $f:\mathcal{D}\rightarrow\mathbb{R}$ as _left-
computable_ (or _approximable from below_) provided the set
$\\{(d,q):d\in\mathcal{D}\wedge q\in\mathbb{Q}\wedge q<f(d)\\}$ is computably
enumerable. Accordingly, a function $f:\mathcal{D}\rightarrow\mathbb{R}$ is
called _right-computable_ (or _approximable from above_) if the set
$\\{(d,q):d\in\mathcal{D}\wedge q\in\mathbb{Q}\wedge q>f(d)\\}$ is computably
enumerable, and $f$ is _computable_ if $f$ is right- and left-computable. If
we refer to a function $f:\mathcal{D}\rightarrow\mathbb{Q}$ as computable we
usually mean that it maps the domain $\mathcal{D}$ to the domain $\mathbb{Q}$,
that is, it returns the exact value $f(d)\in\mathbb{Q}$. If
$\mathcal{D}=\mathbb{N}$ we write $f$ as a sequence
$(q_{i})_{i\in\mathbb{N}}$.

A real number $\alpha\in\mathbb{R}$ is left-computable, right computable or
computable provided the constant function $c_{\alpha}(t)=\alpha$ is left-
computable, right-computable or computable, respectively.
$\alpha\in\mathbb{R}$ is referred to as _computably approximable_ if
$\alpha=\lim_{i\to\infty}q_{i}$ for a computable sequence
$(q_{i})_{i\in\mathbb{N}}$ of rationals. It is well-known (see e.g.
[mlq/ZW01]) that there are left-computable which are not right-computable and
vice versa, and that there are computably approximable reals which are neither
left-computable nor right-computable.

The following approximation property is easily verified. Let
$(q_{i})_{i\in\mathbb{N}}$ be a computable family of rationals converging to
$\alpha$ and let $(q^{\prime}_{i})_{i\in\mathbb{N}},q^{\prime}_{i}>0,$ be a
computable family of rationals converging to $0$. If $\alpha$ is not right-
computable then there are infinitely many $i\in\mathbb{N}$ such that $\alpha-
q_{i}>q_{i}^{\prime}$. ∎ For, otherwise, $\alpha$ as the limit of
$(q_{i}+q^{\prime}_{i})_{i\in\mathbb{N}}$ would be right-computable.

##  2\. Gales and Martingales

Hausdorff [hausdorff18] introduced a notion of dimension of a subset $Y$ of a
metric space which is now known as its _Hausdorff dimension_ , $\dim Y$;
Falconer [book:Falconer03] provides an overview and introduction to this
subject. In the case of the Cantor space $X^{\omega}$, Lutz [ic/Lutz03] (see
also [book_DowneyHirsch10, Section 13.2]) has found an equivalent definition
of Hausdorff dimension via generalisations of martingales.

Following Lutz a mapping $d:X^{*}\to[0,\infty)$ will be called an _$\sigma$
-supergale_ provided

$\forall w(w\in X^{*}\to|X|^{\sigma}\cdot d(w)\geq\sum_{x\in X}d(wx))\,.$ (1)

A $\sigma$-supergale $d$ is called an $\sigma$-gale if, for all $w\in X^{*}$,
Eq. (1) is satisfied with equality. (_Super_)_Martingales_ are
$1$-(super)gales.

From Eq. (1) one easily infers that if $d,\mathcal{V}:X^{*}\to[0,\infty)$
satisfy

$\forall w(w\in X^{*}\to\frac{\mathcal{V}(w)}{|X|^{(1-\sigma)\cdot|w|}}=d(w))$
(2)

then $d$ is a $\sigma$-(super)gale if and only if $\mathcal{V}$ is a
(super)martingale. Thus (super)gales can be viewed as a combination of
(super)martingales with exponential order functions in the sense of Schnorr
[book_Schnorr71, Section 17] (see also [terwijn04, apal/CST06] or
[book_DowneyHirsch10, Section 13.3]).

Following Lutz [ic/Lutz03] we define as follows. Let $F\subseteq X^{\omega}$.
Then $\alpha$ is the _Hausdorff dimension_ $\dim F$ of $F$ provided

  1. (1)

for all $\sigma>\alpha$ there is a $\sigma$-supergale $d$ such that
$\forall\xi(\xi\in F\to\limsup\limits_{w\to\xi}d(w)=\infty)$, and111Here
$\limsup\limits_{w\to\xi}d(w)$ is an abbreviation for
$\lim\limits_{n\to\infty}\sup\\{d(w):w\in\mathbf{pref}(\xi)\wedge|w|\geq
n\\}$.

  2. (2)

for all $\sigma<\alpha$ and all $\sigma$-supergales $d$ it holds
$\exists\xi(\xi\in F\wedge\limsup\limits_{w\to\xi}d(w)<\infty)$.

If the $\omega$-language $F\subseteq X^{\omega}$ is closed in Cantor space and
satisfies a certain balance condition Theorem 4 of [jstplann/St89] shows that
the calculation of its Hausdorff dimension can be simplified. For the purposes
of our investigations the following special case will suffice.

######  Proposition 1.

Let $F\subseteq X^{\omega}$ be non-empty and satisfy the conditions

  1. (1)

$F=\\{\xi:\mathbf{pref}(\xi)\subseteq\mathbf{pref}(F)\\}$ and

  2. (2)

$|\mathbf{pref}(F)\cap w\cdot X^{k}|=|\mathbf{pref}(F)\cap v\cdot X^{k}|$ for
all $k\in\mathbb{N}$ and $w,v\in\mathbf{pref}(F)$ with $|w|=|v|$.

Then $\displaystyle\dim
F=\liminf\limits_{n\to\infty}\frac{\log_{|X|}|\mathbf{pref}(F)\cap X^{n}|}{n}$
.∎

##  3\. Iterative Tree Construction

The aim of this section is, given a sequence of rationals
$(q_{i})_{i\in\mathbb{N}},0<q_{i}<1$, to construct an $\omega$-language
$F\subseteq X^{\omega}$ with Hausdorff dimension $\dim
F=\liminf_{i\to\infty}q_{i}$ satisfying the conditions (1) and (2) of
Proposition 1.

###  3.1. Preliminaries

As a preparation we show how to find sequences of natural numbers
$(k_{i})_{i\in\mathbb{N}}$ and $(\ell_{i})_{i\in\mathbb{N}}$ with appropriate
properties such that $q_{i}=k_{i}/\ell_{i}$.

######  Lemma 2.

Let $(q_{i})_{i\in\mathbb{N}}$, $0<q_{i}<1$, $q_{i}\neq q_{i+1}$, be a family
of positive rationals. Then there are families of natural numbers
$(k_{i})_{i\in\mathbb{N}}$, $(\ell_{i})_{i\in\mathbb{N}}$,
$(\kappa_{i})_{i\in\mathbb{N}}$, $(p_{i})_{i\in\mathbb{N}}$ and
$(r_{i})_{i\in\mathbb{N}}$, such that $q_{i}=k_{i}/\ell_{i}$, $\displaystyle
q_{i+1}=\frac{r_{i}\cdot
k_{i}+\kappa_{i}\cdot\ell_{i}}{r_{i}\cdot\ell_{i}+p_{i}\cdot\ell_{i}}$ where
$\kappa_{i}=\left\\{\begin{array}[]{ll}0,&\mbox{ if }q_{i}>q_{i+1}\mbox{
and}\\\ p_{i},&\mbox{ if }q_{i}<q_{i+1}.\end{array}\right.$

$\displaystyle\mbox{Moreover, for $0\leq t\leq p_{i}\cdot\ell_{i}$ we have\
}q_{i}\geq$ $\displaystyle\displaystyle\frac{r_{i}\cdot
k_{i}}{r_{i}\cdot\ell_{i}+t}$ $\displaystyle\geq q_{i+1},\mbox{ if
}q_{i}>q_{i+1}\mbox{ and}$ (3) $\displaystyle q_{i}\leq$
$\displaystyle\displaystyle\frac{r_{i}\cdot k_{i}+t}{r_{i}\cdot\ell_{i}+t}$
$\displaystyle\leq q_{i+1},\mbox{ if }q_{i}<q_{i+1}.$ (4)

######  Proof 3.1.

Let $q_{i}=k_{i}/\ell_{i}$ and $\displaystyle q_{i+1}=a/b\cdot
q_{i}=\frac{a\cdot k_{i}}{b\cdot\ell_{i}}$, with
$a,b\in\mathbb{N}\setminus\\{0\\},a\neq b$. Since $1>q_{i+1}$ we have
$b\cdot\ell_{i}-a\cdot
k_{i}=a\cdot\frac{q_{i}}{q_{i+1}}\cdot(1-q_{i+1})\cdot\ell_{i}>0$.

Assume $q_{i}>q_{i+1}$. Then $b>a$ and the equation

$\frac{r_{i}\cdot
k_{i}+\kappa_{i}\cdot\ell_{i}}{r_{i}\cdot\ell_{i}+p_{i}\cdot\ell_{i}}=\frac{a\cdot
k_{i}}{b\cdot\ell_{i}}$ (5)

has the solutions $r_{i}=a$, and $p_{i}=(b-a)=a\cdot(\frac{q_{i}}{q_{i+1}}-1)$
and $\kappa_{i}=0$.

If $q_{i}<q_{i+1}$ then $a>b$ and $r_{i}:=b\cdot\ell_{i}-a\cdot
k_{i}=a\cdot(\frac{q_{i}}{q_{i+1}}\cdot\ell_{i}-k_{i})=a\cdot
q_{i}\cdot(\frac{1}{q_{i+1}}-1)\cdot\ell_{i}$ and
$p_{i}=\kappa_{i}:=(a-b)\cdot k_{i}=a\cdot
q_{i}\cdot(1-\frac{q_{i}}{q_{i+1}})\cdot\ell_{i}$ are solutions of Eq. (5).

In view of $\kappa_{i}=0$ Eq. (3) is obvious. Eq. (4) follows inductively from
$\frac{k+1}{\ell+1}\geq\frac{k}{\ell}$ whenever $0\leq k<\ell$. ∎

If the family $(q_{i})_{i\in\mathbb{N}}$ is a computable one then the families
in Lemma 2 can be chosen to be computable. In addition, the values $\ell_{i}$
and $\ell_{i+1}/\ell_{i}$ can be made arbitrarily large.

###  3.2. Tree construction

The $\omega$-language $F$ will be the limit of the following sequence of
finite trees $T_{i}$. These trees have a property similar to the one in
Proposition 1 (2) which is referred to as _spherical symmetry_ in
[Furstenberg70].

We define the following auxiliary languages $T_{i}\subseteq X^{\ell_{i}}$ and
$U_{i}\subseteq X^{p_{i}\cdot\ell_{i}}$.

Let $T_{0}:=X^{k_{0}}\cdot 0^{\ell_{0}-k_{0}}$ or
$T_{0}:=0^{\ell_{0}-k_{0}}\cdot X^{k_{0}}$ and set

$T_{i+1}:=T_{i}^{r_{i}}\cdot U_{i}\mbox{ with
}U_{i}:=\left\\{\begin{array}[]{ll}X^{p_{i}\cdot\ell_{i}},&\mbox{ if
}q_{i+1}\geq q_{i}\mbox{ and}\\\ \\{u_{i}\\},&\mbox{
otherwise}\end{array}\right.$ (6)

where $u_{i}\in X^{p_{i}}$ is a fixed word. Then
$\ell_{i+1}=(r_{i}+p_{i})\cdot\ell_{i}$. Thus $T_{i+1}$ consists of a
concatenation of $r_{i}$ copies of $T_{i}$ plus an appendix $U_{i}$ of length
$p_{i}\cdot\ell_{i}$. The values $r_{i}$ and $p_{i}$ are referred to as
repetition or prolongation factors, respectively.

By induction one proves

$|T_{i}|=|X|^{q_{i}\cdot\ell_{i}}\,.$ (7)

The trees $T_{i}$ have the following properties. Let $\ell\leq\ell_{i}$.

  1. (1)

Prefix property:
$\mathbf{pref}(T_{i+1})=\bigcup_{j=0}^{r_{i}-1}T_{i}^{j}\cdot\mathbf{pref}(T_{i})\cup
T_{i}^{r_{i}}\cdot\mathbf{pref}(U_{i})$,

  2. (2)

Extension property: $\mathbf{pref}(T_{i})\cap
X^{\ell}=\mathbf{pref}(T_{i+1})\cap X^{\ell}$, and

  3. (3)

Spherical symmetry: $\mathbf{pref}(T_{i})\cap
X^{\ell}=(\mathbf{pref}(T_{i})\cap X^{\ell-1})\cdot X$ or

  4. $|\mathbf{pref}(T_{i})\cap X^{\ell}|=|\mathbf{pref}(T_{i})\cap X^{\ell-1}|.$ ∎

###  3.3. The infinite tree

We define our $\omega$-language $F$ having the properties mentioned in
Proposition 1 as $F:=\bigcap_{i\in\mathbb{N}}T_{i}\cdot X^{\omega}$ where the
family $(T_{i})_{i\in\mathbb{N}}$ satisfies Eq. (6).

Before we proceed to further properties of $(T_{i})_{i\in\mathbb{N}}$ and $F$
we mention a general property.

######  Lemma 3.

Let $T_{i}\subseteq X^{*}$, $T_{i+1}\subseteq T_{i}\cdot X\cdot X^{*}$,
$T_{i}\subseteq\mathbf{pref}(T_{i+1})$ and
$F:=\bigcap_{i\in\mathbb{N}}T_{i}\cdot X^{\omega}$. Then
$\mathbf{pref}(F)=\bigcup_{i\in\mathbb{N}}\mathbf{pref}(T_{i})$.

If, moreover, all $T_{i}$ are finite then $F:=\\{\xi:\xi\in
X^{\omega}\wedge\mathbf{pref}(\xi)\subseteq\bigcup_{i\in\mathbb{N}}\mathbf{pref}(T_{i})\\}$.