# Convex Methods for Constrained Linear Bandits

Amirhossein Afsharrad1, Ahmadreza Moradipari2, Sanjay Lall1 1 Department of
Electrical Engineering, Stanford University<EMAIL_ADDRESS>2
Department of Electrical and Computer Engineering, University of California
Santa Barbara<EMAIL_ADDRESS>This work was supported by
NSF under ECCS CPS project number 2125511.

###### Abstract

Recently, bandit optimization has received significant attention in real-world
safety-critical systems that involve repeated interactions with humans. While
there exist various algorithms with performance guarantees in the literature,
practical implementation of the algorithms has not received as much attention.
This work presents a comprehensive study on the computational aspects of safe
bandit algorithms, specifically safe linear bandits, by introducing a
framework that leverages convex programming tools to create computationally
efficient policies. In particular, we first characterize the properties of the
optimal policy for safe linear bandit problem and then propose an end-to-end
pipeline of safe linear bandit algorithms that only involves solving convex
problems. We also numerically evaluate the performance of our proposed
methods.

##  I Introduction

Recently, bandit optimization has received significant attention in real-world
cyber-physical systems that involve repeated interactions with humans. In such
cases, a learner repeatedly interacts with an unknown environment. During each
interaction, it selects an action from a given action set and observes its
corresponding reward. The learner’s goal is to maximize the accumulated
reward. However, these systems are bound by safety constraints that must be
respected during these interactions. Consequently, traditional bandit
algorithms may not be directly applicable in these contexts. Indeed, proper
and nontrivial modifications are necessary to enable the use of bandit
algorithms in safety-critical systems. To achieve this, new research
directions have emerged, focusing on designing constraint bandit algorithms
with provable guarantees. In these settings, the environment is subject to a
set of unknown operational constraints. Depending on the nature of these
constraints, various constrained stochastic bandit settings have been
formulated and analyzed. In our work, we concentrate on the linear stochastic
bandit problem that is constrained by a set of unknown linear constraints.

A linear bandit (LB) is a variant of the multi-armed bandit (MAB) problem in
which each action is associated with a feature vector $x$ and the expected
reward of playing each action is equal to the inner product of its feature
vector and an unknown parameter vector $\theta_{*}$. Two efficient approaches
have been developed for LB: linear UCB (LUCB) [1, 2, 3] and linear Thompson
sampling [4, 5]. A diverse body of related works on linear stochastic bandits
has considered the effect of safety constraints that need to be respected
during all the rounds of the algorithm. An algorithm is called stage-wise safe
if the safety constraint is not violated with high probability over all
rounds. Such algorithms have been proposed for for linear UCB [6] and for
linear Thompson sampling [7, 8]. In the more relaxed setting, where the
algorithm is allowed to violate the safety constraint for some limited rounds,
[9] has proposed safe algorithms with a provable upper bound on the total
number constraint violations. Our setting is inspired by the work of [10],
where the agent’s objective is to produce a series of policies that yield the
highest expected cumulative reward, all the while maintaining that the
expected cost of the policy constructed in each round stays below a specified
threshold.

In this work, we investigate the computational aspects of safe linear bandit
algorithms. Various methods have been developed as shown in [10, 7, 11, 12,
13, 14], which produce policies with precise performance guarantees. In this
paper, we utilize convex programming tools to build a framework using these
algorithms, allowing for explicit computation of policies. We aim to address
two main challenges. First, standard methods require solving a non-convex
optimization problem at each time step of the bandit algorithms. This poses a
computational challenge, as finding a globally efficient solution for this
class of problems can become NP-hard in certain cases, as noted in [15].
Second, standard algorithms necessitate optimization over a set of probability
distributions. While straightforward for convex decision sets, the complexity
is dependent on the form of the decision set and can pose challenges for some
non-convex decision sets. Our primary contribution is an end-to-end pipeline
of algorithms for constrained bandits with performance guarantees, which only
involve solving convex optimization problems. This ensures computational
efficiency as all the algorithms can be efficiently implemented using only a
convex solver. In order to address the second aforementioned challenge, we
focus on decision sets that are a union of convex sets, each described by
convex inequalities.

The rest of the paper is organized as follows: Section II presents some
preliminary material. In Section III we state the formal version of the
problem we are addressing. In Section IV-A, we provide characteristics of an
optimal policy, offering insight into what one might expect from such a
policy, and propose a method to compute such a policy. Section IV-B introduces
a general computationally efficient algorithm with performance guarantees to
address the constrained bandit problem. In Section IV-C we propose a novel
problem-dependent approach that improves the performance bound of the previous
section and can achieve optimal performance for specific classes of problems.
Section V presents experiments that illustrate the performance of our methods.

##  II Preliminaries

Before delving into the main problem formulation and our results, we introduce
a set of definitions and lemmas in this section.

Norms. For a vector $x\in\mathbb{R}^{d}$ and positive definite matrix
$\Sigma\in{\mathbb{R}}^{d\times d}$ we define

$\|x\|_{\Sigma,p}=\|\Sigma^{1/2}x\|_{p},$

In particular, for $p=2$, we have

$\|x\|_{\Sigma,2}=\sqrt{x^{\top}\Sigma x}.$

######  Lemma 1 (Caratheodory’s theorem).

Every point in the convex hull of a set $S\subset{\mathbb{R}}^{d}$ can be
expressed as a convex combination of at most $d+1$ points from $S$.

######  Lemma 2 (Linear program basic feasible solution).

The linear program

$\displaystyle\begin{split}\operatorname*{maximize}\quad&c^{\top}x\\\
\mathrm{subject\>to\>}\quad&Ax=b\\\ &x\geq 0\\\ \end{split}$

has a solution with at most $p$ non-zero entries, where
$A\in{\mathbb{R}}^{p\times q}$ is a fat full-rank matrix. This solution is
called a basic feasible solution.

######  Lemma 3 (Convex hull of the union of convex sets [16]).

Consider the problem

$\displaystyle\begin{split}\mathrm{minimize}\>\quad&f_{0}(z)\\\
\mathrm{subject\>to\>}\quad&\mathop{\bf
conv}\left(\bigcup_{i=1}^{k}{\mathcal{D}}^{i}\right)\\\ \end{split}$ (1)

where

${\mathcal{D}}^{i}=\\{x:f_{ij}(x)\leq 0,\>j=1,\cdots,k_{i}\\}$

and each $f_{ij}:{\mathbb{R}}^{d}\to{\mathbb{R}}$ is convex.

An approach to solving this problem is to solve the convex program

$\displaystyle\begin{split}\mathrm{minimize}\>\quad&f_{0}(z)\\\
\mathrm{subject\>to\>}\quad&\alpha_{i}f_{ij}(x_{i}/\alpha_{i})\leq 0,\quad
i\in[k],j\in[k_{i}]\\\ &\mathbf{1}^{\top}\alpha=1\\\ &\alpha\geq 0\\\
&z=x_{1}+\cdots+x_{k}\end{split}$ (2)

over the variables $z,x_{1},\cdots,x_{k}\in{\mathbb{R}}^{d}$ and
$\alpha_{1},\cdots,\alpha_{k}\in{\mathbb{R}}$. If
$(z^{\star},x_{1}^{\star},\cdots,x_{k}^{\star},\alpha_{1}^{\star},\cdots,\alpha_{k}^{*})$
is an optimal solution of (2), then $z^{*}$ is an optimal solution of (1).

##  III Problem Formulation

Initial setup. We consider the linear bandit with linear constraints
characterized by the reward parameter $\theta_{*}\in{\mathbb{R}}^{d}$ and the
cost parameter $\Gamma_{*}\in{\mathbb{R}}^{m\times d}$. In each round $t$, the
agent is given a decision set ${\mathcal{D}}_{t}\subset{\mathbb{R}}^{d}$ from
which it has to choose an action $x_{t}$. We assume that ${\mathcal{D}}_{t}$
is the union of $n_{t}$ convex sets
${\mathcal{D}}_{t}^{1},\cdots,{\mathcal{D}}_{t}^{n_{t}}$, each of which being
described via convex inequalities, i.e.,

$\displaystyle\begin{split}{\mathcal{D}}_{t}^{i}&=\left\\{x:f_{t}^{ij}(x)\leq
0,\>j=1,\cdots,k_{t}^{i}\right\\}\\\
{\mathcal{D}}_{t}&=\bigcup_{i=1}^{n_{t}}{\mathcal{D}}_{t}^{i}.\end{split}$ (3)

Upon taking action $x_{t}\in{\mathcal{D}}_{t}$, the agent observes a reward
signal $r_{t}=\theta_{*}^{\top}x_{t}+\eta_{t}^{r}$ and a cost signal vector
$c_{t}=\Gamma_{*}x_{t}+\eta_{t}^{c}$, where $\eta_{t}^{r}\in{\mathbb{R}}$ and
$\eta_{t}^{c}\in{\mathbb{R}}^{m}$ are random variables of reward and cost
noise, satisfying conditions that will be specified later. The agent selects
its action $x_{t}\in{\mathcal{D}}_{t}$ in each round $t$ according to its
policy $\pi_{t}\in\Delta_{{\mathcal{D}}_{t}}$ at that round, i.e.,
$x_{t}\sim\pi_{t}$.

Objective. The objective of the agent is to generate a sequence of policies
$\\{\pi_{t}\\}_{t=1}^{T}$ maximizing the expected cumulative reward over $T$
rounds. This should be achieved while satisfying the linear constraints

$\mathbb{E}_{x\sim\pi_{t}}\left(\Gamma_{*}x\right)\leq\tau,\quad\forall
t\in[T],$ (4)

where the $i$th row of $\Gamma_{*}$ is represented by $\mu_{*i}$. The vector
$\tau\in\mathbb{R}^{m}$ is termed the constraint threshold vector and is known
to the agent. Additionally, the vector inequality in (4) is interpreted
element-wise.

Consequently, the policy $\pi_{t}$ that the agent chooses in each round
$t\in[T]$ must reside within the set of feasible policies defined over the
action set ${\mathcal{D}}_{t}$, i.e.,

$\Pi_{t}=\left\\{\pi\in\Delta_{{\mathcal{D}}_{t}}:\mathop{\mathbb{E}}_{x\sim\pi}\left(\Gamma_{*}x\right)\leq\tau\right\\}.$
(5)

Optimizing for the maximum expected cumulative reward over $T$ rounds can be
rephrased as minimizing the constrained pseudo-regret across $T$ rounds

${\mathcal{R}}_{\Pi}(\theta_{*},T)=\sum_{t=1}^{T}\mathop{\mathbb{E}}_{x\sim\pi^{*}_{t}}\left(\theta_{*}^{\top}x\right)-\mathop{\mathbb{E}}_{x\sim\pi_{t}}\left(\theta_{*}^{\top}x\right),$
(6)

where $\pi_{t},\pi^{*}_{t}\in\Pi_{t}$ for all $t\in[T]$. Here, $\pi^{*}_{t}$
signifies the optimal feasible policy during round $t$, defined as

$\pi^{*}_{t}=\max_{\pi\in\Pi_{t}}\mathop{\mathbb{E}}_{x\sim\pi_{t}}\left[\theta_{*}^{\top}x\right].$
(7)

It is worth emphasizing that $\pi^{*}_{t}$ refers to the optimal omniscient
feasible policy, one that is achievable by an agent that is informed of the
hidden parameters $\theta_{*}$ and $\Gamma_{*}$. This should be distinctly
recognized from the best achievable policy by an agent observing only noisy
rewards and costs.

Assumptions. We operate under the following assumptions in our setting, which
are standard in the linear bandit literature.

######  Assumption 1.

The constraint parameter matrix $\Gamma_{*}\in{\mathbb{R}}^{m\times d}$ is fat
and full-rank, i.e., $m<d$ and $\mathop{\bf rank}(\Gamma_{*})=m$.

######  Assumption 2.

For all $t\in T$, the reward and cost noise random variables $\eta_{t}^{r}$,
$\eta_{t}^{c}$ are conditionally $R$-sub-Gaussian, i.e.,

$\displaystyle\mathop{\mathbb{E}}\left[\eta_{t}^{r}|{\mathcal{F}}_{t-1}\right]=0,\quad\mathop{\mathbb{E}}\left[\exp\left(\alpha\eta_{t}^{r}\right)|{\mathcal{F}}_{t-1}\right]\leq\exp\left(\alpha^{2}R^{2}/2\right),$
$\displaystyle\mathop{\mathbb{E}}\left[\eta_{t,i}^{c}|{\mathcal{F}}_{t-1}\right]=0,\quad\mathop{\mathbb{E}}\left[\exp\left(\alpha\eta_{t,i}^{c}\right)|{\mathcal{F}}_{t-1}\right]\leq\exp\left(\alpha^{2}R^{2}/2\right)$

for any $\alpha\in{\mathbb{R}},i\in[m]$, where ${\mathcal{F}}_{t}$ is the
filtration that includes all events
$(x_{1:t+1},\eta^{r}_{1:t},\eta^{c}_{1:t})$ until the end of round $t$.

######  Assumption 3.

There is a known constant $S>0$, such that $\|\theta_{*}\|\leq S$ and
$\|\mu_{i*}\|\leq S^{2}$ for all $i\in[m]$.

######  Assumption 4.

The decision set ${\mathcal{D}}_{t}$ is bounded. Specifically,
$\max_{t\in[T]}\max_{x\in{\mathcal{D}}_{t}}\|x\|\leq L$.

######  Assumption 5.

For all $t\in[T]$ and $x\in{\mathcal{D}}_{t}$, the mean rewards and costs are
bounded, i.e., $\theta_{*}^{\top}x\in[0,1]$ and $\mu_{i*}^{\top}x\in[0,1]$ for
$i\in[m]$.

######  Assumption 6.

There exists a universally safe action $x_{0}\in{\mathcal{D}}_{t}$ for all
$t\in[T]$ associated with the cost vector $c_{0}\in{\mathbb{R}}^{m}$. This
means that $\Gamma_{*}x_{0}=c_{0}<\tau$. For the sake of clarity, we assume
that $c_{0}=0$ and that its value is known. Extending this to the cases where
$c_{0}\neq 0$ is known, or $c_{0}$ is unknown, is straightforward. For further
details on these scenarios, one can refer to [17].

Summary. To summarize, the problem data includes the reward vector
$\theta_{*}$, the constraint matrix $\Gamma_{*}$, the constraint threshold
vector $\tau$, the problem horizon $T$, the observation noise sub-Gaussian
parameter $R$, the reward and cost upper bound parameter $S$, the known safe
action $x_{0}$, and the decision sets
$\mathcal{D}_{1},\ldots,\mathcal{D}_{T}$, where each $\mathcal{D}_{t}$ is
characterized by a set of integers $n_{t},k_{t}^{1},\ldots,k_{t}^{n_{t}}$ and
a set of convex functions $f_{t}^{i,j}$ with $i\in[n_{t}],j\in[k_{t}^{i}]$.

Note that we are working within the specified class of decision sets, i.e.,
sets in the form of a union of convex sets each described by convex
inequalities, exclusively for computational purposes. Nevertheless, it is
important to highlight that our theoretical results and theorems remain valid
for any arbitrary choice of decision sets.

##  IV Main Results

###  IV-A The optimal feasible policy

At each time step $t$, the optimal feasible policy $\pi^{*}_{t}$ is obtained
by solving the following optimization problem:

$\displaystyle\begin{split}\operatorname*{maximize}_{\pi\in\Delta_{{\mathcal{D}}_{t}}}\quad&\mathop{\mathbb{E}}_{x\sim\pi}\left(\theta_{*}^{\top}x\right)\\\
\mathrm{subject\>to\>}\quad&\mathop{\mathbb{E}}_{x\sim\pi}\left(\Gamma_{*}x\right)\leq\tau\end{split}$
(8)

While the reward and cost parameters $\theta_{*}$ and $\Gamma_{*}$ are unknown
in the bandit setting, it is valuable to understand the structure of the
optimal feasible policy $\pi^{*}_{t}$ even when these parameters are known.
Specifically, the optimization in (8) considers probability distributions over
the decision set ${\mathcal{D}}_{t}$, and since ${\mathcal{D}}_{t}$ can be any
arbitrary set, characterizing the optimal feasible policy can be a complex
task. The subsequent theorem, an extension of Lemma 5 in [17], provides a
characterization of the optimal feasible policy $\pi^{*}_{t}$.

######  Theorem 1.

There exists an optimal feasible policy $\pi^{*}_{t}$ that solves (8) with
finite support of at most $m+1$ elements.

###### Proof.

First, observe that while (8) is an optimization over all choices of
distributions $\pi\in{\mathcal{D}}_{t}$, the only component of $\pi$ that
plays a role in the optimization is $\mathop{\mathbb{E}}_{x\sim\pi}(x)$. Thus,
letting $z=\mathop{\mathbb{E}}_{x\sim\pi}(x)$, solving (8) is equivalent to
first solving

$\displaystyle\begin{split}\operatorname*{maximize}_{z}\quad&\theta^{\top}z\\\
\mathrm{subject\>to\>}\quad&\Gamma z\leq\tau\\\ &z\in\mathop{\bf
conv}({\mathcal{D}}_{t})\end{split}$ (9)

to find a solution $z^{*}$, and then find a distribution
$\pi^{*}_{t}\in\Delta_{{\mathcal{D}}_{t}}$ such that
$\mathop{\mathbb{E}}_{x\sim\pi^{*}_{t}}(x)=z^{*}$. Note that the constraint
$z\in\mathop{\bf conv}({\mathcal{D}}_{t})$ has to be included in the new
optimization problem since if $z^{*}\notin\mathop{\bf
conv}({\mathcal{D}}_{t})$, then there is no distribution
$\pi\in\Delta_{{\mathcal{D}}_{t}}$ whose expected value is $z^{*}$.

Now, let $z^{*}$ be the solution of (9). Since $z\in\mathop{\bf
conv}({\mathcal{D}}_{t})$, we know that $z$ is given by a convex combination
of a finite number of elements in ${\mathcal{D}}_{t}$. Moreover, according to
Caratheodory’s theorem presented in Lemma 1, one such convex combination
exists with at most $d+1$ points. Thus, a set of points
$z_{1},\cdots,z_{d+1}\in{\mathcal{D}}_{t}$ and a set of non-negative scalars
$\alpha_{1},\cdots,\alpha_{d+1}$ exist such that
$z^{*}=\sum_{i=1}^{d+1}\alpha_{i}z_{i}=Z\alpha$ and
$\sum_{i=1}^{d+1}\alpha_{i}=1$, where $Z\in{\mathbb{R}}^{d\times(d+1)}$ is a
matrix whose $i$th column is $z_{i}$ and $\alpha\in{\mathbb{R}}^{d+1}$ is a
vector whose $i$ entry is $\alpha_{i}$. Next, we form the following
optimization problem:

$\displaystyle\begin{split}\operatorname*{maximize}_{\beta\in{\mathbb{R}}^{d+1}}\quad&\theta^{\top}Z\beta\\\
\mathrm{subject\>to\>}\quad&\Gamma Z\beta\leq\tau\\\
&\mathbf{1}^{\top}\beta=1\\\ &\beta\geq 0\end{split}$ (10)

Note that if $\beta$ is a solution of (10), then $z_{\beta}=Z\beta$ is a
solution of (9). The final step would be to show that a specific solution
$\beta^{*}$ for (10) exists with at most $m+1$ non-zero entries. This step is
taken via Lemma 2, according to which (10) has a basic feasible solution that
has no more than $m+1$ non-zero elements. Note that (10) can be converted to
the form given by Lemma 2 by adding slack variables. Now, letting $\beta^{*}$
be a basic feasible solution of (10), the optimal feasible policy
$\pi^{*}_{t}$ with a support of at most $m+1$ elements is given by

$\mathop{\mathbb{P}}_{x\sim\pi^{*}_{t}}(x=z)=\begin{cases}\beta^{*}_{i}&z=z_{i}\\\
0&\text{otherwise}\end{cases}$ (11)

where $z_{i}$ is the $i$th column of $Z$. This completes the proof. ∎

The proof of Theorem 1 provides a straightforward algorithm to compute the
optimal feasible policy $\pi^{*}_{t}$ given $\theta_{*}$ and $\Gamma_{*}$.
Algorithm 1 provides the steps to achieve this goal.

Algorithm 1 Computation of the optimal feasible policy

1:Input: $\theta_{*}\in{\mathbb{R}}^{d},\Gamma_{*}\in{\mathbb{R}}^{m\times
d},\tau\in{\mathbb{R}}^{d}_{+}$

2: Solve (9) and find $z^{*}\in\mathop{\bf
conv}\left({\mathcal{D}}_{t}\right)$

3: Find $Z=\begin{bmatrix}z_{1}\cdots
z_{d+1}\end{bmatrix}\in{\mathbb{R}}^{d\times(d+1)}$ and
$\alpha\in{\mathbb{R}}^{d}_{+}$ such that $z^{*}=Z\alpha$ and
$\mathbf{1}^{\top}\alpha=1$

4: Find $\beta^{*}$, a basic feasible solution of (10)

5: return $\pi^{*}_{t}$ according to (11)

With the decision set described in (3), lines 2 and 3 of the algorithm can be
implemented simultaneously using the result of Lemma 3. According to Lemma 3,
this can be done by solving the convex optimization problem

$\displaystyle\begin{split}\mathrm{minimize}\>\quad&\theta^{\top}z\\\
\mathrm{subject\>to\>}\quad&\Gamma z\leq\tau\\\
&\alpha_{i}f_{ij}(x_{i}/\alpha_{i})\leq 0,\quad i\in[k],j\in[k_{i}]\\\
&\mathbf{1}^{\top}\alpha=1\\\ &\alpha\geq 0\\\
&z=x_{1}+\cdots+x_{k}\end{split}$ (12)

and finding the optimal $z^{*}=\sum_{i=1}^{k}\alpha_{i}z_{i}$, where
$z_{i}=x_{i}/\alpha_{i}$ and $x_{i},\alpha_{i}$ are solutions of (12). Note
that in this case, instead of expressing $z^{*}$ in terms of at most $d+1$
points, it is expressed in terms of $k$ points. Based on how $d$ and $k$
compare, this can be a computational advantage or disadvantage. However, it
does not affect the overall flow of Algorithm 1 as all the steps can be
implemented and the only difference is that $d+1$ gets substituted by $k$.

While we have addressed the implementation issue in line 3 of Algorithm 1 for
a special case, we do not have a general computationally efficient method to
implement it without further knowledge of the set ${\mathcal{D}}_{t}$ and the
way it is being expressed.

Finally, line 4 of Algorithm 1 can be implemented using the Simplex method,
and line 5 is constructed based on the output of line 4, which concludes our
full algorithmic pipeline to calculate the optimal feasible policy
$\pi^{*}_{t}$.

###  IV-B Computationally-tractable algorithms with performance guarantees for
linear bandits with linear constraints

In the literature, there are numerous formulations of linearly-constrained
linear bandits [6, 7, 10, 18, 19, 12]. Many associated algorithms [19, 18, 7,
10] follow similar strategies. Specifically, they establish confidence regions
for both reward and cost parameters. These algorithms strive to optimistically
maximize the reward, while taking a pessimistic stance in controlling the
cost. This means they account for the worst-case scenario that the cost
parameter corresponds to the least favorable value within the confidence
region.

In this section, we delve into the Optimistic-Pessimistic Linear Bandit (OPLB)
Algorithm introduced by [17], which serves as our foundational algorithm. We
elucidate its workings, identify computational barriers, and tackle these
challenges by introducing computationally-tractable algorithms backed by
performance guarantees. It is worth noting that, although our solutions are
tailored to a specific formulation of the linearly constrained linear bandit
problem, they can be readily extended to other formulations, given that they
all encounter the same computational challenge.

Consider a linear bandit with linear constraints as described in III. For
simplicity we assume $m=1$. Consequently, the constraint matrix
$\Gamma_{*}\in\mathbb{R}^{m\times d}$ simplifies to a row vector, which we
denote by $\mu_{*}^{\top}\in\mathbb{R}^{d}$. This implies that only one linear
constraint, $\mu_{*}^{\top}x\leq\tau$, is present. Extending this to the
general case with $m$ constraints is straightforward.

At each round $t\in[T]$, given the past actions $\\{x_{i}\\}_{i=1}^{t-1}$,
observed rewards $\\{r_{i}\\}_{i=1}^{t-1}$, and cost signals
$\\{c_{i}\\}_{i=1}^{t-1}$, we construct the Gram matrix

$\Sigma_{t}=\lambda I+\sum_{i=1}^{t-1}x_{i}x_{i}^{\top}.$ (13)

Then we compute the $\ell_{2}$-regularized least squares estimates of
$\theta_{*}$ and $\mu_{*}$ using the regularization parameter $\lambda$. These
are given by

${\widehat{\theta}}_{t}=\Sigma_{t}^{-1}\sum_{i=1}^{t-1}r_{i}x_{i},\quad\quad{\widehat{\mu}}_{t}=\Sigma_{t}^{-1}\sum_{i=1}^{t-1}c_{i}x_{i}.$
(14)

As suggested by OPLB, we construct the confidence sets

$\displaystyle\begin{split}{\mathcal{C}}_{t,\ell_{2}}^{\theta}&=\left\\{\theta\in{\mathbb{R}}^{d}:\left\|\theta-{\widehat{\theta}}_{t}\right\|_{\Sigma_{t},2}\leq\rho\beta_{t}\right\\},\\\
{\mathcal{C}}_{t,\ell_{2}}^{\mu}&=\left\\{\mu\in{\mathbb{R}}^{d}:\left\|\mu-{\widehat{\mu}}_{t}\right\|_{\Sigma_{t},2}\leq\beta_{t}\right\\},\end{split}$
(15)

where $\rho=1+\frac{2}{\tau-c_{0}}$,
$\beta_{t}=R\sqrt{d\log\frac{1+(t-1)L^{2}/\lambda}{\delta}}+\sqrt{\lambda}S$,
and $\|.\|_{\Sigma_{t},2}$ is defined in Sectin II.

According to the principal theorem presented in [20], there is a probability
of at least $1-\delta$ that the unidentified parameters $\theta_{*}$ and
$\mu_{*}$ are contained within the sets ${\mathcal{C}}_{t,\ell_{2}}^{\theta}$
and ${\mathcal{C}}_{t,\ell_{2}}^{\mu}$, respectively.

The final step of OPLB is to solve the problem

$\displaystyle\begin{split}\operatorname*{maximize}_{\pi\in\Delta_{{\mathcal{D}}_{t}},\theta\in{\mathbb{R}}^{d}}\quad&\mathop{\mathbb{E}}_{x\sim\pi}\left(\theta^{\top}x\right)\\\
\mathrm{subject\>to\>}\quad&\theta\in{\mathcal{C}}_{t,\ell_{2}}^{\theta}\\\
&\pi\in\Pi_{t},\end{split}$ (16)

where

$\Pi_{t}=\\{\pi\in\Delta_{{\mathcal{D}}_{t}}:\mathop{\mathbb{E}}_{x\sim\pi}\left(\mu^{\top}x\right)\leq\tau,\>\forall\mu\in{\mathcal{C}}^{\mu}_{t,\ell_{2}}\\}$
(17)

is the pessimistic set of safe policies.

######  Proposition 1.

The optimization problem (16) is equivalent to

$\displaystyle\begin{split}\operatorname*{maximize}_{z\in{\mathbb{R}}^{d}}\quad&\rho\beta_{t}\sqrt{z^{\top}\Sigma_{t}z}+{\widehat{\theta}}_{t}^{\top}z\\\
\mathrm{subject\>to\>}\quad&\beta_{t}\sqrt{z^{\top}\Sigma_{t}z}+{\widehat{\mu}}_{t}^{\top}z\leq\tau\\\
&z\in\mathop{\bf conv}({\mathcal{D}}_{t}).\end{split}$ (18)

###### Proof.

First, we define $z=\mathbb{E}_{x\sim\pi}(x)$. Instead of tackling an
optimization problem over a set of probability distributions, we aim to find
the expected value. This step needs the condition $z\in\mathop{\bf
conv}(\mathcal{D}_{t})$. This reasoning follows the same lines as the proof of
Theorem 1. The remainder of the proof, which explains the specific forms of
the objective function and the constraint, directly stems from Proposition 1
in [17]. ∎

Once equation (18) is solved and the optimal solution
$z^{*}=\sum_{i=1}^{d+1}\alpha_{i}z_{i}$ is identified as a convex combination
of elements from $\mathcal{D}_{t}$, the optimal feasible policy $\pi^{*}_{t}$
is expressed by

$\mathop{\mathbb{P}}_{x\sim\pi^{*}_{t}}(x=z)=\begin{cases}\alpha_{i}&\text{if
}z=z_{i}\\\ 0&\text{otherwise}.\end{cases}$ (19)

The following theorem, a central result from [17], offers a regret bound on
the algorithm’s performance.

######  Theorem 2 (Theorem 2 of [17]).

Assuming the conditions presented in the problem formulation of Section III
are satisfied, the regret of OPLB, with a probability greater than
$1-2\delta$, is bounded by

$\displaystyle\begin{split}\mathcal{R}_{\Pi}\left(\theta,T\right)&\leq\frac{2L(\rho+1)\beta_{T}}{\sqrt{\lambda}}\sqrt{2T\log\left(1/\delta\right)}\\\
&+(\rho+1)\beta_{T}\sqrt{2Td\log\left(1+\frac{TL^{2}}{\lambda}\right)}.\end{split}$
(20)

While the outlined approach offers a comprehensive pipeline to tackle the
constrained bandit problem, a primary obstacle arises from the computational
complexity of solving the main optimization problem (16) or its equivalent
(18). As noted in [15], the unconstrained variant of this problem, with a
decision set that is represented as a polytope defined by the intersection of
halfspaces, is NP-hard. This implies that searching for a universally
applicable computational technique, irrespective of the decision set’s nature,
may be futile. Furthermore, as elaborated in Section IV-A, optimizing over
probability distributions (or equivalently, with the constraint
$z\in\mathop{\bf conv}\left({\mathcal{D}}_{t}\right)$) introduces its own set
of challenges.

To navigate the first challenge, we propose a modified OPLB that, while
computationally feasible, yields a more relaxed regret bound. This
modification ensures a universally efficient algorithm. Later in Section IV-C,
we present an alternative technique for addressing the original problem (18),
which is suitable for specific cases but not universally. To tackle the second
challenge, analogous to Section IV-A, we utilize the technique introduced in
Lemma 3.

To make the OPLB more computationally efficient, we modify the confidence
sets. Instead of using the confidence set $C^{\theta}_{t,\ell_{2}}$ presented
in (15), we switch to a confidence set using the $\ell_{1}$ norm and an
adjusted radius. Specifically, we define the confidence set as

${\mathcal{C}}_{t,\ell_{1}}^{\theta}=\left\\{\theta\in{\mathbb{R}}^{d}:\left\|\theta-{\widehat{\theta}}_{t}\right\|_{\Sigma_{t},1}\leq\rho\sqrt{d}\beta_{t}\right\\},$
(21)

where $\rho$ and $\beta_{t}$ retain their previous definitions and
$\|.\|_{\Sigma,1}$ is detailed in Section II. Note that, as will be shown in a
subsequent lemma, an $\ell_{1}$ confidence set for $\mu_{*}$ is unnecessary.
Instead, we can continue using the ${\mathcal{C}}_{t,\ell_{2}}^{\mu}$ as
previously defined.

######  Lemma 4.

For any $t\in[T]$ and any $\delta>0$, the following holds:

$\displaystyle\mathop{\mathbb{P}}\left(\theta_{*}\in{\mathcal{C}}_{t,\ell_{1}}^{\theta}\right)$
$\displaystyle\geq 1-\delta.$ (22)

###### Proof.

For any vector $x\in{\mathbb{R}}^{d}$, we have that
$\|x\|_{1}\leq\sqrt{d}\|x\|_{2}$. This yields

$\left\|\Sigma^{1/2}\left(\theta-{\widehat{\theta}}\right)\right\|_{1}\leq\sqrt{d}\left\|\Sigma^{1/2}\left(\theta-{\widehat{\theta}}\right)\right\|_{2}.$

Given that the right-hand side is bounded by $\sqrt{d}\rho\beta_{t}$ for any
$\theta\in{\mathcal{C}}^{\theta}_{t,\ell_{2}}$, it follows that
${\mathcal{C}}^{\theta}_{t,\ell_{2}}\subseteq{\mathcal{C}}^{\theta}_{t,\ell_{1}}$.
By the main theorem of [20], we know that
$\theta_{*}\in{\mathcal{C}}^{\theta}_{t,\ell_{2}}$ with a probability of at
least $1-\delta$, which concludes the proof. ∎

In the modified version of OPLB that incorporates the $\ell_{1}$ confidence
region, we address a new optimization problem given by

$\displaystyle\begin{split}\operatorname*{maximize}_{z\in{\mathbb{R}}^{d},\theta\in{\mathbb{R}}^{d}}\quad&\theta^{\top}z\\\
\mathrm{subject\>to\>}\quad&\theta\in{\mathcal{C}}_{t,\ell_{1}}^{\theta}\\\
&z\in S_{t}\\\ &z\in\mathop{\bf
conv}\left({\mathcal{D}}_{t}\right),\end{split}$ (23)

where
$S_{t}=\\{z\in{\mathbb{R}}^{d}:\mu^{\top}z\leq\tau,\>\forall\mu\in{\mathcal{C}}^{\mu}_{t,\ell_{2}}\\}.$
Once this problem is solved and the optimal solution
$z^{*}=\sum_{i=1}^{d+1}\alpha_{i}z_{i}$ is identified as a convex combination
of elements from $\mathcal{D}_{t}$, the optimal feasible policy $\pi^{*}_{t}$
is given by (19).

######  Proposition 2.

The optimization problem (23) can be decomposed and solved by addressing $2d$
individual convex optimization problems.

###### Proof.

We can express (23) in the following format:

$\displaystyle\begin{split}\operatorname*{maximize}_{\theta\in{\mathbb{R}}^{d}}\quad&f(\theta)\\\
\mathrm{subject\>to\>}\quad&\theta\in{\mathcal{C}}_{t,\ell_{1}}^{\theta},\\\
\end{split}$ (24)

where the function $f$ is defined as:

$\displaystyle\begin{split}f(\theta)=\quad\max_{z\in{\mathbb{R}}^{d}}\quad&\theta^{\top}z\\\
\mathrm{s.t.}\quad&z\in S_{t}\\\ &z\in\mathop{\bf
conv}\left({\mathcal{D}}_{t}\right).\end{split}$ (25)

Given that $f$ is convex and the region ${\mathcal{C}}_{t,\ell_{1}}^{\theta}$
forms a polytope in ${\mathbb{R}}^{d}$, our task in (24) is to maximize this
convex function over the polytope. Recognizing that solutions to such problems
occur at the vertices of the polytope, we realize that to solve (24), it
suffices to evaluate $f$ at the $2d$ vertices. Each evaluation corresponds to
solving a convex optimization problem as shown in (25), which completes the
proof. ∎

Proposition 2 demonstrates that the modified OPLB can be efficiently solved.
The subsequent step is to ascertain a guarantee for the regret bound. The
theorem below provides this guarantee.

######  Theorem 3 (Modified OPLB regret bound).

Given that the conditions outlined in Section III are met, the regret of the
modified OPLB employing the $\ell_{1}$ confidence region for the reward
parameter $\theta_{*}$, with a probability exceeding $1-2\delta$, can be
upper-bounded as

$\displaystyle\begin{split}\mathcal{R}_{\Pi}\left(\theta,T\right)&\leq\frac{2L(\rho+1)\beta_{T}}{\sqrt{\lambda}}\sqrt{2Td\log\left(1/\delta\right)}\\\
&+(\rho+1)\beta_{T}d\sqrt{2T\log\left(1+\frac{TL^{2}}{\lambda}\right)}.\end{split}$
(26)

###### Proof.

By examining the proof of Theorem 2, it becomes apparent that the regret bound
depends on the confidence region radius of the reward parameter $\theta_{*}$,
namely $\rho\beta_{T}$, without specifically relying on the value of
$\rho\beta_{T}$. Further inspection reveals that the confidence region radius
of the cost parameter $\mu_{*}$ has no bearing on the bound. In the modified
OPLB approach, the initial radius is scaled by a factor of $\sqrt{d}$, while
the latter remains unchanged. Hence, in the expression (20), substituting
$\beta_{t}$ with $\sqrt{d}\beta_{t}$ results in the updated bound presented in
(26), which completes the proof. ∎

With Theorem 3, we now possess a comprehensive framework for tackling the
constrained bandit problem using algorithms that are computationally
efficient. It’s important to highlight that a key step in this process is the
evaluation of the function $f$ as defined in (25). Although this is a convex
optimization problem, one cannot overlook that its two constraints, in their
most general form, may introduce complications unless they are further
simplified.

The primary constraint, $z\in S_{t}$, can be replaced by the more direct
constraint
$\beta_{t}\sqrt{z^{\top}\Sigma_{t}z}+{\widehat{\mu}}^{\top}z\leq\tau$,
following the guidelines of Proposition 1. The latter constraint,
$z\in\mathop{\bf conv}\left({\mathcal{D}}_{t}\right)$, while complicated in
general, is navigated for the class of decision sets studied in this work
using the technique introduced in Lemma 3. Consequently, the task of
evaluating the function $f$ from (25) simplifies to solving

$\begin{split}f(\theta)=\max_{z\in{\mathbb{R}}^{d}}&\quad\theta^{\top}z\\\
\mathrm{s.t.}\quad&\beta_{t}\sqrt{z^{\top}\Sigma_{t}z}+{\widehat{\mu}}_{t}^{\top}z\leq\tau\\\
&\alpha_{i}f_{ij}(x_{i}/\alpha_{i})\leq 0,\quad i\in[k],j\in[k_{i}]\\\
&\mathbf{1}^{\top}\alpha=1,\quad\alpha\geq 0,\\\
&z=x_{1}+\cdots+x_{k}.\end{split}$ (27)

The procedure is concisely summarized in Algorithm 2.

Algorithm 2 Modified OPLB

1:Input: $T\in{\mathbb{N}}$, $\delta\in{\mathbb{R}}_{+}$,
$\gamma\in{\mathbb{R}}_{+}$, $\tau\in{\mathbb{R}}$

2:for $t=1$ to $T$ do

3: Observe $r_{t},c_{t}$ and compute ${\widehat{\theta}}_{t}$ and
${\widehat{\mu}}_{t}$ using (14)

4: $z^{*}\leftarrow$ Solve (23) using Proposition 2 and (27)

5: Construct $\pi_{t}$ using $z^{*}$ according to (19)

6: Play the action $x_{t}\sim\pi_{t}$

7:end for

###  IV-C The upper bound maximization method

Recall (18) which presents the original problem with $\ell_{2}$ confidence
sets that we initially sought to solve. Since solving this problem is
challenging, our first approach was to present an $\ell_{1}$ relaxation to
this problem, as discussed in Section IV-B. In this section we introduce a
problem-dependent method that has the potential to exactly solve (18). The
following theorem provides the tools that we need for this method.

######  Theorem 4.

Let $g_{1},g_{2}:{\mathbb{R}}^{d}\to{\mathbb{R}}$ be arbitrary functions and
let $C\subseteq{\mathbb{R}}^{d}$ be an arbitrary set. Consider the
optimization problems

$\displaystyle\begin{split}\operatorname*{maximize}_{z\in{\mathbb{R}}^{d}}\quad&g_{1}(z)\\\
\mathrm{subject\>to\>}\quad&g_{1}(z)\leq g_{2}(z)\\\ &z\in C\end{split}$ (28)

and

$\displaystyle\begin{split}\operatorname*{maximize}_{z\in{\mathbb{R}}^{d}}\quad&g_{2}(z)\\\
\mathrm{subject\>to\>}\quad&g_{1}(z)\leq g_{2}(z)\\\ &z\in C.\end{split}$ (29)

If $z^{*}$ is an optimal solution for (29) and $g_{1}(z^{*})=g_{2}(z^{*})$,
then $z^{*}$ is also an optimal solution for (28).

###### Proof.

Suppose $\tilde{z}$ is an optimal solution for (28) and $z^{*}$ is not. Then,
$g_{1}(\tilde{z})>g_{1}(z^{*})=g_{2}(z^{*})\geq g_{2}(\tilde{z})$. The first
inequality stems from the optimality of $\tilde{z}$ and the non-optimality of
$z^{*}$ for (28), the equality follows directly from the assumption of the
theorem, and the last inequality arises because $z^{*}$ maximizes $g_{2}$.
This leads to $g_{1}(\tilde{z})>g_{2}(\tilde{z})$, a violation of the
constraint $g_{1}(z)\leq g_{2}(z)$, thus a contradiction. This concludes that
$z^{*}$ is an optimal solution for (28). ∎

This theorem allows us to solve (29) instead of (28). If the condition
$g_{1}(z^{*})=g_{2}(z^{*})$ holds, then we have an optimal solution for (28)
as well. This may be quite useful if (29) is more tractable than (28).

We now apply the result of Theorem 4 to (18). For clarity, we restate this
problem as follows:

$\displaystyle\begin{split}\operatorname*{maximize}_{z\in{\mathbb{R}}^{d}}\quad&\rho\beta_{t}\sqrt{z^{\top}\Sigma_{t}z}+\hat{\theta}_{t}^{\top}z\\\
\mathrm{subject\>to\>}\quad&\beta_{t}\sqrt{z^{\top}\Sigma_{t}z}+\hat{\mu}_{t}^{\top}z\leq\tau\\\
&z\in\mathop{\bf conv}(\mathcal{D}_{t}).\end{split}$ (30)

Setting
$g_{1}(z)=\rho\beta_{t}\sqrt{z^{\top}\Sigma_{t}z}+\hat{\theta}_{t}^{\top}z$,
$g_{2}(z)=\rho\tau+(\hat{\theta}_{t}-\rho\hat{\mu}_{t})^{\top}z$, and
$C=\mathop{\bf conv}(\mathcal{D}_{t})$, (30) becomes a particular instance of
(28). Consequently, the counterpart of (29) in our setting is

$\displaystyle\begin{split}\operatorname*{maximize}_{z\in{\mathbb{R}}^{d}}\quad&\rho\tau+\left(\hat{\theta}_{t}-\rho\hat{\mu}_{t}\right)^{\top}z\\\
\mathrm{subject\>to\>}\quad&\beta_{t}\sqrt{z^{\top}\Sigma_{t}z}+\hat{\mu}_{t}^{\top}z\leq\tau\\\
&z\in\mathop{\bf conv}(\mathcal{D}_{t}),\end{split}$ (31)

which is a convex optimization problem. This provides a potentially more
efficient approach to solve the original OPLB problem with $\ell_{2}$
confidence sets and yield exact solutions. It involves solving (31), a convex
optimization problem amenable to efficient computation. Upon solving this
problem, one must check whether the first constraint is active. If it is, then
the obtained solution also solves (30). If not, the process shifts back to
addressing the $\ell_{1}$ version of the problem, as outlined in (23) or (27).
To handle the second constraint in (31), we utilize the technique proposed in
Lemma 3. Algorithm 3 summarizes the entire methodology. We refer to this
technique as the Upper Bound Maximization (UBM) method, as it entails
maximizing an upper bound on the objective function rather than the objective
function itself.

Algorithm 3 Enhanced OPLB with UBM

1:Input: $T\in\mathbb{N}$, $\delta\in\mathbb{R}_{+}$,
$\gamma\in\mathbb{R}_{+}$, $\tau\in\mathbb{R}$

2:for $t=1$ to $T$ do

3: Observe $r_{t},c_{t}$, and compute $\hat{\theta}_{t}$, $\hat{\mu}_{t}$
using (14)

4: $z^{*}\leftarrow$ Solve (31)

5: if
$\beta_{t}\sqrt{{z^{*}}^{\top}\Sigma_{t}{z^{*}}}+\hat{\mu}_{t}^{\top}{z^{*}}<\tau$
then

6: $z^{*}\leftarrow$ Solve (23) using Proposition 2 and (27)

7: end if

8: Construct $\pi_{t}$ using $z^{*}$ according to (19)

9: Play the action $x_{t}\sim\pi_{t}$

10:end for

Each iteration of Algorithm 3 involves solving either the $\ell_{2}$ or the
$\ell_{1}$ confidence set problem. Thus, the ultimate regret bound will be no
worse than that provided by Theorem 3 but may approach the bound of Theorem 2,
depending on the frequency at which the first constraint becomes active in
(31).

Example. Figure 1 illustrates a one-dimensional example of our setup. The
decision set ${\mathcal{D}}_{t}$ is defined such that $\mathop{\bf
conv}\left({\mathcal{D}}_{t}\right)=\\{z:|z|\leq 3\\}$. Two distinct upper
bound functions, $g^{(1)}_{2}(z)$ and $g^{(2)}_{2}(z)$, are introduced, each
corresponding to a different value of ${\widehat{\mu}}_{t}$. The set $S$
represents the points where the safety constraint $g_{1}(z)\leq g_{2}(z)$, as
described in (30) and (31), is satisfied.

The implications of Theorem 4 are observable in Figure 1, where the conditions
under which UBM is effective become apparent. Specifically, when the upper
bound is described by $g^{(1)}_{2}(z)$, maximizing this function also
optimizes the original objective $g_{1}(z)$, with the constraint $g_{1}(z)\leq
g_{2}(z)$ becoming active at the optimum. Conversely, when the upper bound is
$g^{(2)}_{2}(z)$, UBM does not lead to an optimal solution, as maximizing
$g^{(2)}_{2}(z)$ does not make the constraint active, rendering the approach
ineffective in this case.

$g_{1}(z)$$g^{(2)}_{2}(z)$$g^{(1)}_{2}(z)$$-4$$-3$$-2$$-1$$1$$2$$3$$4$$-2$$-1$$1$$2$$3$$4$$z$$z\in\mathop{\bf
conv}\left({\mathcal{D}}_{t}\right)$$z\in S$Feasible actions Figure 1: Example
of the upper bound maximization test

##  V Experiments

In this section, we present empirical evaluations of the proposed algorithms
through two distinct experiments.

###  V-A Enhanced OPLB policy evaluation with non-convex decision sets

Figure 2: Mean policy trajectory with ${\mathcal{D}}_{t}$ as a union of convex
sets

The first experiment considers a two-dimensional scenario with a non-convex
decision set represented by a union of five disks in $\mathbb{R}^{2}$, all
subject to a single linear constraint. Figure 2 illustrates the policies
chosen by the algorithm at each time step over a total of $T=300$ rounds. The
trajectory depicting the mean value of the policy is shown in Figure 2, which
transitions from yellow to red as time progresses. Notably, at three specific
time steps—$t=0$, $t=40$, and $t=100$— the mean policy values are highlighted
in cyan, magenta, and purple respectively, each delineated with a black
border. Corresponding to each of these mean values, five points are plotted,
representing the five potential actions, one of which is to be randomly
selected according to a specific probability for the policy to be effective.
The radius of each point is proportional to its probability weight in the
policy’s construction, with all weights summing up to one. Furthermore, the
constraint boundary, defined by $x^{\top}\mu=\tau$, is represented as a line
within the figure, and the mean value of the optimal policy is denoted as
$x^{*}$.

Observations from the figure reveal that initially, the trajectory of the
points moves along the boundary of the convex hull of the decision set and
away from the optimal policy. However, as time progresses, the trajectory
redirects towards the optimal policy and ultimately converges to the optimal
solution. Furthermore, the mean value of the policy always remains within the
safe region, indicating that the pessimism in action selection has been
effective, ensuring that the algorithm does not violate the safety constraint
at any point.

###  V-B Cumulative regret comparison

Figure 3: Left: Cumulative regret of $\ell_{1}$ OPLB vs. OPLB with UBM.
Middle: Histogram of cumulative regret at $T=2000$. Right: Mean policy
trajectory of $\ell_{1}$ OPLB vs. UBM OPLB

In the second experiment, we compare the cumulative regrets of Algorithms 2
and 3, namely the $\ell_{1}$ OPLB and UBM OPLB. Figure 3 (left) presents the
cumulative regret of both algorithms given the parameters
$\theta_{*}=[3,2.5]^{\top}$, $\mu_{*}=[0.5,0.5]^{\top}$, and $\tau=0.5$, with
the decision set being the unit disk. The results indicate a marginally better
cumulative regret for UBM OPLB. This plot reveals an interesting phenomenon:
asymmetric confidence bands around the UBM OPLB’s regret, with a lower
confidence band that is notably further below the mean compared to the upper
band. Further investigation into this observation is conducted by examining
Figure 3 (middle), which displays a histogram of the cumulative regrets for
both algorithms at time $t=2000$ over $N=1000$ simulations. The histogram
suggests that, although UBM OPLB’s performance is largely in line with that of
$\ell_{1}$ OPLB, it exhibits a secondary mode where the cumulative regret is
substantially lower. This accounts for the observed lower confidence band in
the first plot. In certain cases, UBM OPLB significantly outperforms
$\ell_{1}$ OPLB. For a closer look at this behavior, we examine the mean
policy trajectories of $\ell_{1}$ OPLB and UBM OPLB under the aforementioned
superior performance. Figure 3 (right) delineates these trajectories with the
evolution from yellow to red and cyan to magenta, respectively, for a span of
$T=300$ steps. Clearly, $\ell_{1}$ OPLB does not approach the optimal policy
as closely as UBM OPLB, resulting in greater regret, whereas UBM OPLB tends
toward the optimal policy, exhibiting minimal regret. Although this phenomenon
is problem-specific and not universally observed, it presents an intriguing
aspect for further research.

## References

  * [1] V. Dani, T. P. Hayes, and S. M. Kakade, “Stochastic linear optimization under bandit feedback,” 2008.
  * [2] P. Rusmevichientong and J. N. Tsitsiklis, “Linearly parameterized bandits,” _Mathematics of Operations Research_ , vol. 35, no. 2, pp. 395–411, 2010\.
  * [3] Y. Abbasi-Yadkori, D. Pál, and C. Szepesvári, “Improved algorithms for linear stochastic bandits,” in _Advances in Neural Information Processing Systems_ , 2011, pp. 2312–2320.
  * [4] S. Agrawal and N. Goyal, “Thompson sampling for contextual bandits with linear payoffs,” in _International Conference on Machine Learning_ , 2013, pp. 127–135.
  * [5] M. Abeille, A. Lazaric _et al._ , “Linear thompson sampling revisited,” _Electronic Journal of Statistics_ , vol. 11, no. 2, pp. 5165–5197, 2017\.
  * [6] S. Amani, M. Alizadeh, and C. Thrampoulidis, “Linear stochastic bandits under safety constraints,” in _Advances in Neural Information Processing Systems_ , 2019, pp. 9252–9262.
  * [7] A. Moradipari, S. Amani, M. Alizadeh, and C. Thrampoulidis, “Safe linear thompson sampling with side information,” _IEEE Transactions on Signal Processing_ , vol. 69, pp. 3755–3767, 2021.
  * [8] A. Moradipari, M. Alizadeh, and C. Thrampoulidis, “Linear thompson sampling under unknown linear constraints,” in _ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2020, pp. 3392–3396.
  * [9] T. Chen, A. Gangrade, and V. Saligrama, “Strategies for safe multi-armed bandits with logarithmic regret and risk,” in _International Conference on Machine Learning_. PMLR, 2022, pp. 3123–3148.
  * [10] A. Pacchiano, M. Ghavamzadeh, P. Bartlett, and H. Jiang, “Stochastic bandits with linear constraints,” in _International conference on artificial intelligence and statistics_. PMLR, 2021, pp. 2827–2835.
  * [11] K. N. Varma, S. Lale, and A. Anandkumar, “Stochastic linear bandits with unknown safety constraints and local feedback,” in _ICML Workshop on New Frontiers in Learning, Control, and Dynamical Systems_ , 2023.
  * [12] K. Khezeli and E. Bitar, “Safe linear stochastic bandits,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 34, no. 06, 2020, pp. 10 202–10 209.
  * [13] S. Hutchinson, B. Turan, and M. Alizadeh, “The impact of the geometric properties of the constraint set in safe optimization with bandit feedback,” in _Learning for Dynamics and Control Conference_. PMLR, 2023, pp. 497–508.
  * [14] T. Chen, A. Gangrade, and V. Saligrama, “A doubly optimistic strategy for safe linear bandits,” _arXiv preprint arXiv:2209.13694_ , 2022.
  * [15] V. Dani, T. P. Hayes, and S. M. Kakade, “Stochastic linear optimization under bandit feedback,” in _Annual Conference Computational Learning Theory_ , 2008\. [Online]. Available: https://api.semanticscholar.org/CorpusID:9134969
  * [16] S. Boyd and L. Vandenberghe, _Convex Optimization_. Cambridge University Press, 2004.
  * [17] A. Pacchiano, M. Ghavamzadeh, P. Bartlett, and H. Jiang, “Stochastic bandits with linear constraints,” in _Proceedings of The 24th International Conference on Artificial Intelligence and Statistics_ , ser. Proceedings of Machine Learning Research, A. Banerjee and K. Fukumizu, Eds., vol. 130. PMLR, 13–15 Apr 2021, pp. 2827–2835. [Online]. Available: https://proceedings.mlr.press/v130/pacchiano21a.html
  * [18] A. Moradipari, C. Thrampoulidis, and M. Alizadeh, “Stage-wise conservative linear bandits,” _Advances in neural information processing systems_ , vol. 33, pp. 11 191–11 201, 2020.
  * [19] A. Kazerouni, M. Ghavamzadeh, Y. Abbasi Yadkori, and B. Van Roy, “Conservative contextual linear bandits,” _Advances in Neural Information Processing Systems_ , vol. 30, 2017.
  * [20] Y. Abbasi-yadkori, D. Pál, and C. Szepesvári, “Improved algorithms for linear stochastic bandits,” in _Advances in Neural Information Processing Systems_ , J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K. Weinberger, Eds., vol. 24. Curran Associates, Inc., 2011.


#  Erdős-Rényi laws for exponentially and polynomially mixing dynamical
systems.

Nicolai Haydn and Matthew Nicol Department of Mathematics, University of
Southern California; Department of Mathematics, University of Houston. E-mail:
$<$nhaydn<EMAIL_ADDRESS>MN would like to thank the NSF
for support on NSF-DMS Grant 2009923.

###### Abstract

Erdős-Rényi limit laws give the length scale of a time-window over which time-
averages in Birkhoff sums have a non-trivial almost-sure limit. We establish
Erdős-Rényi type limit laws for Hölder observables on dynamical systems
modeled by Young Towers with exponential and polynomial tails. This extends
earlier results on Erdős-Rényi limit laws to a broad class of dynamical
systems with some degree of hyperbolicity.

##  1 Introduction

The Erdős-Rényi fluctuation law gives the length scale of a time-window over
which time-averages in Birkhoff sums have a non-trivial almost-sure limit. It
was first proved in the independent and identically distributed (i.i.d.) case
[9] in the following form:

######  Proposition 1.1.

Let $(X_{n})_{n\geq 1}$ be an i.i.d. sequence of non-degenerate random
variables, $\mathbb{E}[X_{1}]=0$, and let $S_{n}=X_{1}+\cdots+X_{n}$. Assume
that the moment generating function $\phi(t)=\mathbb{E}(e^{tX_{1}})$ exists in
some open interval $U\subset\mathbb{R}$ containing $t=0$. For each $\alpha>0$,
define $\psi_{\alpha}(t)=\phi(t)e^{-\alpha t}$. For those $\alpha$ for which
$\psi_{\alpha}$ attains its minimum at a point $t_{\alpha}\in U$, let
$c_{\alpha}=\alpha t_{\alpha}-\ln\phi(t_{\alpha})$. Then

$\lim_{n\to\infty}\max\\{(S_{j+[\ln n/c_{\alpha}}-S_{j})/[\ln
n/c_{\alpha}]:1\leq j\leq n-[\ln n/c_{\alpha}]\\}=\alpha$

The existence of $\psi_{\alpha}(t)$ for all $t\in U$ implies exponential large
deviations with a rate function (in fact $c_{\alpha}=I(\alpha)$ where $I$ is
the rate function, defined later) and this implies that sampling over a window
length $k(n)$ of larger than logarithmic length scale (in the sense that
$k(n)/\ln n\to\infty$), allows the ergodic theorem to kick in and

$\lim_{n\to\infty}\max\\{(S_{j+k(n)}-S_{j})/k(n):1\leq j\leq n-k(n)\\}=0$

while sampling over too small a window, for example $k(n)=1$, gives similarly
a trivial limit

$\lim_{n\to\infty}\max\\{(S_{j+k(n)}-S_{j})/k(n):1\leq j\leq
n-k(n)\\}=\|X_{1}\|_{\infty}$

Define the function

$\theta(n,k(n)):=\max_{0\leq j\leq n-k(n)}\frac{S_{j+k(n)}-S_{j}}{k(n)},$

which may be interpreted as the maximal average gain over a time window of
length $k(n)$ up to time $n$. In the setting of coin tosses the Erdős-Rényi
law gives precise information on the maximal average gain of a player in a
fair game in the case where the length of the time window ensures
$\lim_{n\to\infty}\theta(n,k(n))$ has a non-degenerate almost sure limit.

In 1986 Deheuvels, Devroye and Lynch [6] in the i.i.d. setting of Proposition
1.1 gave a precise rate of convergence and showed that if $k(n)=[\ln
n/c_{\alpha}]$ then $P$ a.s:

$\limsup\frac{[\theta(n,k(n))-\alpha k(n)]}{\ln k(n)}=\frac{1}{2t_{\alpha}}$

and

$\liminf\frac{[\theta(n,k(n))-\alpha k(n)]}{\ln k(n)}=-\frac{1}{2t_{\alpha}}$

In this paper we establish Erdős-Rényi limit laws for Hölder observables on
dynamical systems modeled by Young Towers [21, 22] with exponential and
polynomial tails. Tails refer to the measure $\mu(R>n)$ of the return time $R$
function to the base of the tower. Our exposition is based upon [13, Section
2.3] and [15] who present a framework more general than that of the original
Tower construction of Young [21] in that uniform contraction of local stable
manifolds is not assumed for polynomially mixing systems in dimensions greater
than $1$. We will give more details on Young Towers below but here note that
Hölder observables on Young Towers with exponential (polynomial) tails have
exponential (polynomial) decay of correlations, the precise rate is encoded in
the return time function.

Our results extends the work of [16] from the class of non-uniformly expanding
maps with exponential decay of correlations to all systems modeled by a Young
Tower, including Sinai dispersing billiard maps; diffeomorphisms of Henón
type; polynomially mixing billards as in [4] (as long as the correlation decay
rate is greater than $n^{-\beta}$, $\beta>1$); smooth unimodal and multimodal
maps satisfying the Collet-Eckmann conditions [13, Example 4.10]; certain
Viana maps [13, Example 4.11]; and Lorenz-like maps. Other examples to which
our results apply are listed in [15].

In the setting of hyperbolic dynamical systems there are many earlier results.
Grigull [10] established the Erdős-Renyi law for hyperbolic rational maps,
Chazottes and Collet [5] proved Erdős-Renyi theorems with rates for uniformly
expanding maps of the interval, while Denker and Kabluchko [7] proved Erdős-
Renyi results for Gibbs-Markov dynamics. In [8] Erdős-Rényi limit laws for
Lipschitz observations on a class of non-uniformly expanding dynamical
systems, including logistic-like maps, were given as well as related results
on maximal averages of a time series arising from Hölder observations on
intermittent-type maps over a time window of polynomial length. Kifer [11, 12]
has established Erdős-Rényi laws for non-conventional ergodic sums and in the
setting of averaging or homogenization of chaotic dynamical systems. We
mention also recent related work of [2, 3] on applications of Erdő-Renyí limit
laws to multifractal analysis.

The main novelty of out technique is the use of the symbolic metric on the
axiomatic Young Tower construction of [15, 13] to control the norm of the
indicator function of sets of the form $(S_{n}>n\alpha)$ on the quotiented
tower. This eliminates many difficulties involved with considering the
Lipschitz norm of such sets with respect to the Riemannian metric on the phase
space of the system. The structure allows us to consider, with small error,
averaged Birkhoff sums as being constant on stable manifolds, and thence use
the decay of correlations for observables on the quotiented tower in terms of
their Lipschitz and $L^{\infty}$ norms.

Our results in the case of Young Towers with exponential decay of
correlations, Theorem 5.1, are optimal and replicate the i.i.d case, while in
the case of Young Towers with polynomial tails we investigate windows of
polynomial length and give close to optimal upper and lower bounds, Theorem
7.1 and Theorem 7.2.

##  2 Young Towers.

We now describe more precisely what we mean by a non-uniformly hyperbolic
dynamical system modeled by a Young Tower. Our exposition is based upon [13,
Section 2.3] and [15] who present a framework more general than that of the
original Tower of Young [21] in that uniform contraction of local stable
manifolds is not assumed for polynomially mixing systems in dimensions greater
than $1$. This set-up is very useful for the study of almost sure fluctuations
of Birkhoff sums of bounded variables.

We suppose $T$ is a diffeomorphism of a Riemannian manifold $(M,d)$, possibly
with singularities. Fix a subset $\Lambda\subset M$ with a ‘product
structure’. Product structure means there exists a family of disjoint stable
disks (sometimes called local stable manifolds) $\\{W^{s}\\}$ that cover
$\Lambda$ as well as a family of disjoint unstable disks (sometimes called
local unstable manifolds) $\\{W^{u}\\}$ that cover $\Lambda$. The stable and
unstable disks containing $x\in\Lambda$ are denoted $W^{s}(x)$ and $W^{u}(x)$.
Each stable disk intersects each unstable disk in precisely one point.

Suppose there is a partition $\\{\Lambda_{j}\\}$ of $\Lambda$ such that each
stable disk $W^{s}(x)$ lies in $\Lambda_{j}$ if $x\in\Lambda_{j}$. Suppose
there exists a ‘return time’ integer-valued function $R:\Lambda\to\mathbb{N}$,
constant with value $R(j)$ on each partition element $\Lambda_{j}$, such that
$T^{R(j)}(W^{s}(x))\subset W^{s}(T^{R(j)}x)$ for all $x\in\Lambda_{j}$. We
assume that the greatest common denominator of the integers $\\{R(j)\\}$ is
$1$, which ensures that the Tower is mixing. We define the induced return map
$f:\Lambda\to\Lambda$ by $f(x)=T^{R(x)}(x)$.

For $x,y\in\Lambda$ let $s(x,y)$ be the least integer $n\geq 0$ such that
$f^{n}(x)$ and $f^{n}(y)$ lie in different partition elements of $\Lambda$. We
call $s$ the separation time with respect to the map $f:\Lambda\to\Lambda$.

Assumptions: there exist constants $K\geq 1$ and $0<\beta_{1}<1$ such that

(a) if $z\in W^{s}(x)$ then $d(f^{n}z,f^{n}x)\leq K\beta_{1}^{n}$;

(b) if $z\in W^{u}(x)$ then $d(f^{n}z,f^{n}x)\leq K\beta_{1}^{s(x,z)-n}$;

(c) if $z,x\in\Lambda$ then $d(T^{j}z,T^{j}x)\leq K(d(z,x)+d(fz,fx))$ for all
$0\leq j\leq\min\\{R(z),R(x)\\}$.

Define an equivalence relation on $\Lambda$ by $z\sim x$ if $z\in W^{s}(x)$
and form the quotient space $\overline{\Lambda}=\Lambda/\sim$ with
corresponding partition $\\{\overline{\Lambda_{j}}\\}$. The return time
function $R:\overline{\Lambda}\to\mathbb{N}$ is well-defined as each stable
disk $W^{s}(x)$ lies in $\Lambda_{j}$ if $x\in\Lambda_{j}$ and
$T^{R(j)}(W^{s}(x))\subset W^{s}(T^{R(j)}x)$ for all $x\in\Lambda_{j}$. So we
have a well-defined induced map
$\bar{f}:\overline{\Lambda}\to\overline{\Lambda}$. Suppose that $\bar{f}$ and
the partition $\\{\overline{\Lambda_{j}}\\}$ separates points in
$\overline{\Lambda}$. Define $d_{\beta_{1}}(z,x)=\beta_{1}^{s(z,x)}$, then
$d_{\beta_{1}}$ is a metric on $\overline{\Lambda}$.

Let $m$ be a reference probability measure on $\overline{\Lambda}$ (in most
applications this will be normalized Lebesgue measure). Assume that
$\bar{f}:\overline{\Lambda}\to\overline{\Lambda}$ is a Gibbs-Markov uniformly
expanding on $(\overline{\Lambda},d_{\beta_{1}})$. By this we mean that
$\bar{f}$ is a measure-theoretic bijection from each $\overline{\Lambda_{j}}$
onto $\overline{\Lambda}$.

We assume that $\bar{f}:\overline{\Lambda}\to\overline{\Lambda}$ has an
invariant probability measure $\overline{\nu}$ and
$0<a<\frac{d\bar{\nu}}{dm}<b$ for some constants $a,b$. We assume that $R$ is
$\overline{\nu}$-integrable and there is an $f$ invariant probability $\nu$
measure on $\Lambda$ such that $\overline{\pi}^{*}\nu=\overline{\nu}$ where
$\overline{\pi}$ is the quotient map taking $\Lambda$ onto $\Lambda/\sim$. Now
we define the Young Tower

$\Delta=\\{x,j)\in\Lambda\times\mathbb{N}:0\leq j\leq R(x)-1\\}$

and the tower map $F$ by

$F(x,j)=\left\\{\begin{array}[]{ll}(x,j+1)&\mbox{if $j<R(x)-1$};\\\
(fx,0)&\mbox{if $j=R(x)-1$}.\end{array}\right.$

and lift $\nu$ in a standard way to an invariant probability measure
$\nu_{\Delta}$ for $F:\Delta\to\Delta$. In fact
$\nu_{\Delta}=\nu\times\mbox{counting measure}$.

Define the semi-conjugacy $\pi:\Delta\to M$, $\pi(x,j)=T^{j}(x)$. The measure
$\mu=\pi^{*}\nu_{\Delta}$ is a $T$-invariant mixing probability measure on
$M$. Given an observable $\varphi:M\to\mathbb{R}$ we may lift to an observable
$\varphi:\Delta\to\mathbb{R}$ by defining $\varphi(x,j)=\varphi(T^{j}x)$ (we
keep the same notation for the observable). The semi-conjugacy $\pi^{*}$
allows us to transfer statistical properties from lifted observables $\varphi$
on $(\Delta,F,\nu_{\Delta})$ to the original observables $\varphi$ on
$(T,M,\mu)$.

##  3 Large deviations and rate functions.

Before stating precisely our main result we recall the definition of rate
function and some other notions of large deviations theory. Suppose
$(T,M,\mu)$ is a probability preserving transformation and
$\varphi:M\to\mathbb{R}$ is a mean-zero integrable function i.e.
$\int_{M}\varphi~{}d\mu=0$. Throughout this paper we will write
$S_{n}(\varphi):=\varphi+\varphi\circ T+\ldots+\varphi\circ T^{n-1}$ for the
$n$th ergodic sum of $\varphi$. Sometimes we will write $S_{n}$ instead of
$S_{n}(\varphi)$ for simplicity of notation or when $\varphi$ is clear from
context.

######  Definition 3.1.

A mean-zero integrable function $\varphi:M\to\mathbb{R}$ is said to satisfy a
large deviation principle with rate function $I(\alpha)$, if there exists a
non-empty neighborhood $U$ of $0$ and a strictly convex function
$I:U\to\mathbb{R}$, non-negative and vanishing only at $\alpha=0$, such that

$\displaystyle\lim_{n\to\infty}\frac{1}{n}\log\mu(S_{n}(\varphi)\geq n\alpha)$
$\displaystyle=$ $\displaystyle-I(\alpha)$ (1)

for all $\alpha>0$ in $U$ and

$\displaystyle\lim_{n\to\infty}\frac{1}{n}\log\mu(S_{n}(\varphi)\leq n\alpha)$
$\displaystyle=$ $\displaystyle-I(\alpha)$ (2)

for all $\alpha<0$ in $U$.

In the literature this is referred to as a first level or local (near the
average) large deviations principle.

For Hölder observables on Young Towers with exponential tails (which are not
$L^{1}$ coboundaries in the sense that $\varphi\not=\psi\circ T-\psi$ for any
$\psi\in L^{1}(\mu)$) such an exponential large deviations result holds with
rate function $I_{\varphi}(\alpha)$ [16, 19, 14, 18]. A formula for the width
of $U$ is given in [19] following a standard approach but it is not useful in
concrete estimates.

##  4 Erdős-Rényi laws: background.

Proposition 4.1 given below is found in a proof from Erdős and Rényi [9] (see
[Csorgo_Revesz, Theorem 2.4.3], Grigull [10] Denker and Kabluchko [7] or [8]
where this method has been used). The Gauss bracket $[.]$ denotes the integer
part of a number. Throughout the proofs of this paper we will concentrate on
the case $\alpha>0$ as the case $\alpha<0$ is identical with the obvious
modifications of statements.

######  Proposition 4.1.

Let $(T,M,\mu)$ be an ergodic dynamical system and $\varphi:M\to\mathbb{R}$ is
an observable.

(a) Suppose that $\varphi$ satisfies a large deviation principle with rate
function $I$ defined on the open set $U$ and assume $\mu(\varphi)=0$ Let
$\alpha>0$, $\alpha\in U$ and set

$L_{n}=L_{n}(\alpha)=\left[\frac{\ln n}{I(\alpha)}\right]\qquad
n\in\mathbb{N}.$

Then the upper Erdős-Rényi law holds, that is, for $\mu$ a.e. $x\in X$

$\limsup_{n\to\infty}\max_{0\leq j\leq
n-L_{n}}\frac{1}{L_{n}}S_{L_{n}}(\varphi)\circ T^{j}(x)\leq\alpha.$

(b) If for some constant $C>0$ and integer $\kappa\geq 0$ for each interval
$A$

$\displaystyle\mu\\!\left(\bigcap_{m=0}^{n-L_{n}}\\{S_{L_{n}}(\varphi)\circ
T^{m}\in A\\}\right)$ $\displaystyle\leq$ $\displaystyle C[\mu(S_{L_{n}}\in
A)]^{n/(L_{n})^{\kappa}}$ (3)

then the lower Erdős-Rényi law holds as well, that is, for $\mu$ a.e. $x\in X$

$\liminf_{n\to\infty}\max_{0\leq j\leq
n-L_{n}}\frac{1}{L_{n}}S_{L_{n}}(\varphi)\circ T^{j}\geq\alpha.$

######  Remark 4.2.

If both Assumptions (a) and (b) of Proposition 4.1 hold then

$\lim_{n\to\infty}\max_{0\leq m\leq n-L_{n}}\frac{S_{L_{n}}\circ
T^{m}}{L_{n}}=\alpha.$

######  Remark 4.3.

The proof of the lemma shows that the upper Erdős-Rényi law follows from the
existence of exponential large deviations given by a rate function, while for
the lower Erdős-Rényi law it suffices to show that for every $\epsilon>0$ the
series $\sum_{n>0}\mu(B_{n}(\epsilon))$, where $B_{n}(\epsilon)=\\{\max_{0\leq
m\leq n-L_{n}}S_{L_{n}}\circ T^{m}\leq L_{n}(\alpha-\epsilon)\\}$ is summable.
This is usually the harder part to prove in the deterministic case.

##  5 Erdős-Rényi limit laws for Young Towers with exponential tails.

We now state our main theorem in the case of exponential tails.

######  Theorem 5.1.

Suppose $(T,M,\mu)$ is a dynamical system modeled by a Young Tower with
$\nu_{\Delta}(R>j)\leq C\beta_{2}^{j}$ for some $\beta_{2}\in(0,1)$ and some
constant $C_{2}$. Let $\varphi:M\to\mathbb{R}$ be Hölder with
$\int\varphi~{}d\mu=0$. Assume $\varphi\not=\psi\circ T-\psi$ for any $\psi\in
L^{1}(\mu)$. Let $I(\alpha)$ denote the non-degenerate rate function defined
on an open set $U\subset\mathbb{R}$ containing $0$. Define
$S_{n}(x)=\sum_{j=0}^{n-1}\varphi(T^{j}x)$.

Let $\alpha>0$, $\alpha\in U$ and define

$L_{n}=L_{n}(\alpha)=\left[\frac{\ln n}{I(\alpha)}\right]\qquad
n\in\mathbb{N}.$

Then

$\lim_{n\to\infty}\max_{0\leq j\leq n-L_{n}}\frac{S_{L_{n}}\circ
T^{j}(x)}{L_{n}}=\alpha,$

for $\mu$ a.e. $x\in\Omega$.

##  6 Proof of Theorem 5.1.

We now give the proof of Theorem 5.1, beginning with some preliminary lemmas.
Throughout this proof we will assume that $\varphi$ is Lipschitz, as the
modification for Hölder $\varphi$ is straightforward.

The next lemma is not optimal but is useful in allowing us to go from uniform
contraction along stable manifolds upon returns to the base of the Young Tower
(Property (P3) of [21]) to estimates of the contraction along stable leaves in
the whole manifold.

######  Lemma 6.1.

Let $\beta_{1}$ be defined as in Section (2.1) Assumption (a) and $\beta_{2}$
be as in Theorem 2.2. Let
$D(m)=\\{(x,j)\in\Delta:|T^{k}W^{s}(x,j)|<{(\sqrt{\beta_{1}})}^{k}\mbox{ for
all }k\geq m\\}$. Then for any $\delta>0$ there exists $K(\delta)>0$ such that
for all $m\geq K$, $\nu_{\Delta}(D(m)^{c})\leq C{(\beta_{2}+\delta)}^{m/2}$
for some constant $C>0$.

###### Proof.

Let $\tau_{r}(x,j):=\\#\\{k:1<k\leq r:F^{k}(x,j)\in\Lambda\\}$, so that
$\tau_{r}(x,j)$ denotes the number of times $k\in[1,r]$ that $F^{k}(x,j)$ lies
in the base of the Young Tower. Let
$B_{r}=\\{(x,j)\in\Delta:\tau_{r}(x,j)\leq\sqrt{r}\\}$. If
$\tau_{r}(x,j)\leq\sqrt{r}$ then there is at least one $k\in[0,r]$, such that
$R(F^{k}(x,j))>\sqrt{r}$ and hence
$B_{r}\subset\bigcup_{k=1}^{r}F^{-k}(R>\sqrt{r})$. Thus
$\nu_{\Delta}(B_{r})\leq r\nu(R>\sqrt{r})<C_{2}r{\beta_{2}}^{\sqrt{r}}$.

Suppose now that $(x,j)\in B_{r}^{c}$. Then $|T^{r}W_{s}((x,j))|\leq
2K\beta_{1}^{\sqrt{r}}$ by (a) and (c) and moreover
$\nu_{\Delta}(\bigcup_{r\geq m}(B_{r}))\leq\sum_{r\geq
m}C_{2}r{\beta_{2}}^{\sqrt{r}}$. Now the lemma follows from a straightforward
calculation.

∎

######  Corollary 6.2.

Lift $\varphi:M\to\mathbb{R}$ to $\varphi:\Delta\to\mathbb{R}$ by defining
$\varphi(x,j)=\varphi(T^{j}x)$. Let $\beta_{1}$ be defined as in Section (2.1)
(a). Suppose $p\in
D(m)=\\{(x,j)\in\Delta:|T^{k}W^{s}(x,j)|<{(\sqrt{\beta_{1}})}^{k}\mbox{ for
all }k\geq m\\}$ and let $L_{n}=[\frac{\ln n}{I(\alpha)}]$. Then if $q\in
W^{s}(p)$, $|S_{L_{n}}\varphi\circ F^{m}(p)-S_{L_{n}}\varphi\circ
F^{m}(q)|\leq C\|\varphi\|_{\infty}L_{n}{\beta_{1}}^{m/2}$.

###### Proof of Theorem 5.1.

The main idea of the proof of Theorem 5.1 is to approximate functions on
$\Delta$ by functions constant on stable manifolds, so that correlation decay
estimates on the quotiented tower from [13, Corollary 2.9] can be used.

We define an equivalence relation on $\Lambda$ by $z\sim x$ if $z\in W^{s}(x)$
and form the quotient space $\overline{\Lambda}=\Lambda/\sim$ with
corresponding partition $\\{\overline{\Lambda_{j}}\\}$. The return time
function $R:\overline{\Lambda}\to\mathbb{N}$ is well-defined (and the same in
the quotiented and unquotiented tower) as each stable disk $W^{s}(x)$ lies in
$\Lambda_{j}$ if $x\in\Lambda_{j}$ and $T^{R(j)}(W^{s}(x))\subset
W^{s}(T^{R(j)}x)$ for all $x\in\Lambda_{j}$. So we have a well-defined induced
map $\bar{f}:\overline{\Lambda}\to\overline{\Lambda}$. We similarly define the
quotient space of $\Delta$, denoted $\overline{\Delta}$. The separation time
for $f:\overline{\Lambda}\to\overline{\Lambda}$ extends to a separation time
on $\overline{\Delta}$ by defining

$s((x,l),(y,l^{{}^{\prime}}))=\left\\{\begin{array}[]{ll}s(x,y)&\mbox{if
$l=l^{{}^{\prime}}$};\\\ 1&\mbox{if $l\neq
l^{{}^{\prime}}$}.\end{array}\right.$

We fix $\beta_{1}$ from Section 2.1 Assumption (a) and define the metric
$d_{\beta_{1}}$ on $\overline{\Delta}$ by
$d_{\beta_{1}}(p,q)=\beta_{1}^{s(p,q)}$. Here we write
$p=(x,l)\in\overline{\Delta}$, $q=(y,l^{{}^{\prime}})$. We define the
$\|\cdot\|_{\beta_{1}}$-norm by
$\|\phi\|_{\beta_{1}}:=\|\phi\|_{\infty}+\sup_{p,q\in\Delta}\frac{|\phi(p)-\phi(q)|}{d_{\beta_{1}}(p,q)}$.
Functions $\phi$ and $\psi$ which are constant on stable manifolds in $\Delta$
naturally project to functions $\phi$ and $\psi$ (we use the same notation) on
$\overline{\Delta}$ with the same $d_{\beta_{1}}$ Lipschitz constant and
$L^{\infty}$ norm. If $\phi:\Delta\to\mathbb{R}$ is constant on stable
manifolds we define the $\|\cdot\|_{\beta_{1}}$-norm by
$\|\phi\|_{\beta_{1}}:=\|\phi\|_{\infty}+\sup_{p,q\in\Delta}\frac{|\phi(p)-\phi(q)|}{d_{\beta_{1}}(p,q)}$.

With this set-up the correlation estimate of [13, Corollary 2.9] can be
stated:

######  Proposition 6.3.

[13, Corollary 2.9]

Suppose that $\phi,~{}\psi:\Delta\to\mathbb{R}$ are constant on stable
manifolds then for some constants $C$, $\beta_{3}\in(0,1)$,

$|\int_{\Delta}\phi(\psi\circ
F^{j})\,d\nu_{\Delta}-\int_{\Delta}\phi\,d\nu_{\Delta}\int_{\Delta}\psi\,d\nu_{\Delta}|\leq
C\|\phi\|_{\beta_{1}}\|\psi\|_{\infty}\beta_{3}^{j}$

for all $j\geq 0$ .

In the case that $\varphi$ is not an $L^{1}$ coboundary i.e. there exists no
$\psi$ such that $\varphi=\psi\circ T-\psi$, $\psi\in L^{1}(m)$ it has been
shown [16, 19] under the assumptions of Theorem 5.1 that $\varphi$ has
exponential large deviations with a rate function $I(\alpha)$. Thus assumption
(a) of Proposition 4.1 holds and we therefore only need to prove
$\mu(\\{\max_{0\leq m\leq n-L_{n}}S_{L_{n}}\circ T^{m}\leq
L_{n}(\alpha-\epsilon)\\})$ is summable in order to get the lower bound by an
application of the Borel-Cantelli lemma. This direction is more difficult and
uses differential and dynamical information on the system.

For the reader’s convenience we recall our assumptions:

Assumptions: there exist constants $K\geq 1$ and $0<\beta_{1}<1$ such that

(a) if $z\in W^{s}(x)$ then $d(f^{n}z,f^{n}x)\leq K\beta_{1}^{n}$;

(b) if $z\in W^{u}(x)$ then $d(f^{n}z,f^{n}x)\leq K\beta_{1}^{s(x,z)-n}$;

(c) if $z,x\in\Lambda$ then $d(T^{j}z,T^{j}x)\leq K(d(z,x)+d(fz,fx))$ for all
$0\leq j\leq\min\\{R(z),R(x)\\}$.

We lift $\varphi$ from $M$ to $\Delta$ by defining
$\varphi(x,j)=\varphi(T^{j}x)$. We will use the same notation for $\varphi$ on
$\Delta$ as we use for $\varphi$ on $M$.

To simplify notation we will sometimes write $p=(x,j)$ for a point
$p\in\Delta$.

For $0<\epsilon\ll\alpha$ put

$A_{n}(\epsilon):=\\{(x,j)\in\Delta:S_{L_{n}}\leq L_{n}(\alpha-\epsilon)\\},$

where

$S_{n}(x,j)=\sum_{k=0}^{n-1}\varphi\circ F^{k}(x,j)$

is the $n$th ergodic sum of $\varphi$. Define

$B_{n}(\epsilon)=\bigcap_{m=0}^{n-L_{n}}F^{-m}A_{n}(\epsilon)=\left\\{(x,j)\in\Delta:\max_{0\leq
m\leq n-L_{n}}S_{l_{n}}\circ F^{m}\leq L_{n}(\alpha-\epsilon)\right\\}.$

The theorem follows by the Borel-Cantelli lemma once we show that
$\sum_{n=1}^{\infty}\nu_{\Delta}(B_{n}(\epsilon))<\infty$.

To do this we will use a blocking argument to take advantage of decay of
correlations and intercalate by blocks of length
$\kappa_{n}:=\ln^{\kappa}(n)$, where $\kappa$ will be specified later.

For $1\leq j<r_{n}:=[\frac{n}{\kappa_{n}}]$ put

$E_{n}^{j}(\epsilon):=\bigcap_{m=1}^{j}F^{-m[\kappa_{n}]}A_{n}(\epsilon)$

which is a nested sequence of sets. Note that
$\nu_{\Delta}(B_{n}(\epsilon))\leq\nu_{\Delta}(E_{n}^{r_{n}}(\epsilon))$.

We also have the recursion

$E_{n}^{j}(\epsilon)=A_{n}(\epsilon)\cap F^{-\kappa_{n}}E_{n}^{j-1}(\epsilon)$

$j=1,\dots,r_{n}$, which implies

$\nu_{\Delta}(E_{n}^{j}(\epsilon))=\nu_{\Delta}(A_{n}(\epsilon)\cap
F^{-\kappa_{n}}E_{n}^{j-1}(\epsilon))$

Recall $D(m)=\\{(x,j)\in\Delta:|T^{k}W^{s}(x)|<(\sqrt{\beta_{1}})^{k}\mbox{
for all }k\geq m\\}$. Hence given $\delta>0$ such that
$\beta_{2}^{{}^{\prime}}:=\beta_{2}+\delta<1$ by Lemma 6.1 we may estimate
$\nu_{\Delta}(D(\kappa_{n})^{c})\leq(\beta_{2}^{{}^{\prime}})^{\kappa_{n}/2}$
for sufficiently large $n$.

Furthermore if $m\geq\kappa_{n}$, $p\in D(m)$ and $q\in W^{s}(p)$ then
$|S_{L_{n}}\circ F^{m}(p)-S_{L_{n}}\circ F^{m}(q)|\leq
C\|\varphi\|_{\infty}L_{n}\beta_{1}^{\kappa_{n}/2}$ by the corollary to Lemma
6.1. We will take $\kappa$ and $n$ large enough that
$C\|\varphi\|_{\infty}L_{n}\beta_{1}^{\kappa_{n}/2}<\frac{\epsilon}{2}$.

Accordingly for large $n$ if $m\geq\kappa_{n}$, $p\in D(m)\cap
F^{-m}A_{n}(\epsilon)$ and $q\in W^{s}(p)$ then $F^{m}q\in
A_{n}(\frac{\epsilon}{2})$.

First Approximation.

We now approximate $1_{A_{n}(\epsilon)\cap D(\kappa_{n})}$ by a function
$g_{n}^{\epsilon}$ which is constant on stable manifolds by requiring that if
$p\in A_{n}(\epsilon)\cap D(\kappa_{n})$ then $g_{n}^{\epsilon}(p)=1$ on
$W^{s}(p)$ and $g_{n}^{\epsilon}=0$ otherwise. Thus
$\\{g_{n}^{\epsilon}=1\\}\subset A_{n}(\frac{\epsilon}{2})$ and

$\nu_{\Delta}(g_{n}=1)\leq\nu_{\Delta}(A_{n}(\frac{\epsilon}{2}))$

Furthermore

$A_{n}(\epsilon)\subset\\{g_{n}^{\epsilon}=1\\}\cup D(\kappa_{n})^{c}$

hence

$\nu_{\Delta}(A_{n}(\epsilon))\leq\nu_{\Delta}(g_{n}^{\epsilon}=1)+\nu_{\Delta}(D(\kappa_{n})^{c}).$

For $j=1,\ldots,r_{n}$ let

$G_{n}^{j}(\epsilon)=:\prod_{i=1}^{j}g_{n}^{\epsilon}\circ F^{i[\kappa_{n}]}$

and note
$\nu_{\Delta}(E_{n}^{j}(\epsilon))\leq\nu_{\Delta}(G_{n}^{j}(\epsilon))+j\nu_{\Delta}(D(\kappa_{n})^{c})$.

Second Approximation

We will approximate $g_{n}^{\epsilon}$ (considered as a function on
$\overline{\Delta}$) by a $d_{\beta_{1}}$ Lipschitz function
$h_{n}^{\epsilon}$ which extends to a function on $\Delta$ by requiring
$h_{n}^{\epsilon}$ to be constant on stable manifolds.

First define

$h_{n}^{\epsilon}(\bar{p}):=\max\\{0,1-d_{\beta_{1}}(\bar{p},\mbox{supp}(g_{n}^{\epsilon}))\beta_{1}^{-\sqrt{\kappa_{n}}}\\}$

on $\overline{\Delta}$ and then extend so that it is constant on local stable
manifolds and hence is a function on $\Delta$. In particular
$h_{n}^{\epsilon}$ has support in points such that
$d_{\beta_{1}}(p,\mbox{supp}(g_{n}^{\epsilon}))\leq\beta_{1}^{\sqrt{\kappa_{n}}}$
and $\|h_{n}^{\epsilon}\|_{\beta_{1}}\leq\beta_{1}^{\sqrt{\kappa_{n}}}$ by
[20, Section 2.1].

By $(b)$ and $(c)$ if $z\in W^{u}(p)$ and
$d_{\beta_{1}}(p,z)<\beta_{1}^{\sqrt{\kappa_{n}}}$ then $d(F^{j}p,F^{j}z)\leq
2K\ \beta_{1}^{\sqrt{\kappa_{n}}-L_{n}}$ for all $j\leq L_{n}$.

Hence if
$d_{\beta_{1}}(z,\mbox{supp}(g_{n}^{\epsilon}))\leq\beta_{1}^{\sqrt{\kappa_{n}}}$
then there exists $p\in\mbox{supp}(g_{n}^{\epsilon})$ such that
$d(F^{j}p,F^{j}z)\leq 2K\beta_{1}^{\sqrt{\kappa_{n}}-L_{n}}$ for all $j\leq
L_{n}$ and hence

$|\sum_{j=0}^{L_{n}}[\varphi\circ F^{j}(z)-\varphi\circ F^{j}(p)]|\leq
CL_{n}\beta_{1}^{\sqrt{\kappa_{n}}-L_{n}}\leq\frac{\epsilon}{2}$

for sufficiently large $n$. This implies that
$\nu_{\Delta}(g_{n}^{\epsilon})\leq\nu_{\Delta}(h_{n}^{\epsilon})\leq\nu_{\Delta}(A_{n}(\frac{\epsilon}{2}))$.

As $h_{n}^{\epsilon}$ Lipschitz in the $d_{\beta_{1}}$ metric we obtain by
Proposition 6.3

$\displaystyle\nu_{\Delta}(E_{n}^{j}(\epsilon))$ $\displaystyle\leq$
$\displaystyle\int_{\Delta}(G_{n}^{j}(\epsilon))\,d\nu_{\Delta}+j\nu_{\Delta}(D(\ln^{k}(n)^{c})$
$\displaystyle\leq$ $\displaystyle\int_{\Delta}(g_{n}^{\epsilon}\cdot
G_{n}^{j-1}\circ
F^{\kappa_{n}})\,d\nu_{\Delta}+Cn{(\beta_{1}^{{}^{\prime}})}^{\kappa_{n}/2}$
$\displaystyle\leq$ $\displaystyle\int h_{n}^{\epsilon}\,d\nu_{\Delta}\int
G_{n}^{j-1}(\epsilon)\,d\nu_{\Delta}+c_{3}\beta_{3}^{\kappa_{n}}\|h_{n}^{\epsilon}\|_{\beta_{1}}\|G_{n}^{j-1}(\epsilon)\|_{\infty}+Cj{(\beta_{1}^{{}^{\prime}})}^{\kappa_{n}/2}$
$\displaystyle\leq$
$\displaystyle\nu_{\Delta}(A_{n}(\frac{\epsilon}{2}))\nu_{\Delta}(G_{n}^{j-1}(\epsilon))+c_{3}\beta_{3}^{\kappa_{n}}\beta_{1}^{-\sqrt{\kappa_{n}}}+Cj{(\beta_{1}^{{}^{\prime}})}^{\kappa_{n}/2}.$

Iterating this estimate yields

$\nu_{\Delta}(E_{n}^{0}(\epsilon))\leq\nu_{\Delta}(A_{n}(\frac{\epsilon}{2}))^{[n/\kappa_{n}]}+nc_{3}\beta_{3}^{\kappa_{n}}\beta_{1}^{-\sqrt{\kappa_{n}}}+n^{2}C\beta_{1}^{\kappa_{n}/2}.$

The terms $nc_{3}\beta_{3}^{\kappa_{n}}\beta_{1}^{-\sqrt{\kappa_{n}}}$ and
$n^{2}C\beta_{1}^{\kappa_{n}}$ are summable if we take $\kappa>3$ in the
definition of $\kappa_{n}$.

In order to verify summability of the
$\nu_{\Delta}(A_{n}(\frac{\epsilon}{2}))^{[n/\kappa_{n}]}$ term we proceed as
in the proof of Proposition 4.1 using large deviations. By the existence of a
rate function we obtain $\nu_{\Delta}((A_{n}(\frac{\epsilon}{2}))^{c})\geq
e^{-L_{n}(I(\alpha-\frac{\epsilon}{2})+\delta_{1})}$ for some $0<\delta_{1}$
and hence $1-\nu_{\Delta}(A_{n}(\frac{\epsilon}{2}))\geq
e^{-L_{n}(I(\alpha-\frac{\epsilon}{2})+\delta_{1})}$ for some $0<\delta_{1}$.
Hence $\nu_{\Delta}(A_{n}(\frac{\epsilon}{2}))\leq 1-n^{-\rho}$ where
$\rho=\frac{I(\alpha-\frac{\epsilon}{2})}{I(\alpha)}+\delta_{1}$ is less than
$1$ for $\delta_{1}>0$ small enough. The principal term can be bounded by

$\nu_{\Delta}(A_{n}(\frac{\epsilon}{2}))^{[n/\kappa_{n}]}\leq(1-n^{-\rho})^{[n/\kappa_{n}]}$

which is also summable over $n$. Hence by Borel-Cantelli we conclude that the
set $\\{B_{n}(\epsilon)\mbox{ i.o.}\\}$ has measure zero. This concludes the
proof.

∎

##  7 Erdös-Rényi laws for Young Towers with polynomial tails.

We now consider Young Towers with polynomial tails in the sense that
$\nu_{\Delta}(R>n)\leq Cn^{-\beta}$.

###  7.1 Upper bounds.

We first prove a general result. We suppose that $(T,M,\mu)$ is an ergodic
dynamical system and $\varphi:M\to\mathbb{R}$ is a bounded observable. We
assume also

$\mu\\!\left(\left|\frac{1}{n}S_{n}(\varphi)-\bar{\varphi}\right|>\epsilon\right)\leq
C(\epsilon)n^{-\beta}.$

######  Theorem 7.1.

Assume that $\bar{\varphi}=\mu(\varphi)=0$, $\varphi$ is bounded and for every
$\epsilon>0$ there exists a constant $C(\epsilon)>0$ and $\beta>1$ so that

$\mu\\!\left(\left|\frac{1}{n}S_{n}(\varphi)\right|>\epsilon\right)\leq
C(\epsilon)n^{-\beta}.$

Then if $\tau>\frac{1}{\beta}$ for $\mu$ a.e. $x\in M$,

$\lim_{n\to\infty}\max_{0\leq m\leq n-n^{\tau}}n^{-\tau}S_{n^{\tau}}\circ
T^{m}(x)=0.$

###### Proof.

Choose $\tau>\frac{1}{\beta}$ and put $L_{n}=n^{\tau}$. Let $\epsilon>0$ and
define

$A_{n}:=\\{x\in X:\max_{0\leq m\leq n-L_{n}}|S_{L_{n}}\circ T^{m}|\geq
L_{n}\epsilon\\}.$

Then $\mu(A_{n})\leq n\mu(S_{L_{n}}\geq\epsilon L_{n})\leq
c_{1}(\delta)n^{1-\tau\beta}=c_{1}n^{-\delta}$, for some $c_{1}>0$, where
$\delta=\tau\beta-1$.

Let $p>\frac{1}{\delta}$ (i.e. $\delta p>1$) and consider the subsequence
$n=k^{p}$. Since $\sum_{k}\mu(A_{k^{p}})\leq
c_{1}\sum_{k}k^{-p\delta}<\infty$, we obtain via the Borel-Cantelli lemma that
for $\mu$ a.e. $x\in X$

$\limsup_{k\to\infty}\max_{0\leq m\leq
k^{p}-L_{k^{p}}}L_{k^{p}}^{-1}|S_{L_{k^{p}}}\circ T^{m}|\leq\epsilon.$

To fill the gaps use that $k^{p}-(k-1)^{p}=O(k^{p-1})$ and we obtain (as
$\varphi$ is bounded) that

$\frac{S_{L_{k^{p}}}\circ T^{m}}{L_{k^{p}}}=\frac{S_{L_{(k-1)^{p}}}\circ
T^{m}}{L_{k^{p}}}+\mathcal{O}\\!\left(\frac{1}{k}\right)$

where the implied constant is uniform in $x\in X$as $\varphi$ is bounded. As
$\lim_{k\to\infty}\frac{k^{p}}{(k-1)^{p}}=1$ we conclude

$\lim_{k\to\infty}\frac{|S_{L_{k^{p}}}|}{L_{k^{p}}}=\lim_{k\to\infty}\frac{|S_{L_{(k-1)^{p}}}|}{L_{k^{p}}}.$

Since any $n\in\mathbb{N}$ satisfies $(k-1)^{p}\leq n\leq k^{p}$ for some $k$
and $\varphi$ is bounded, it follows that

$\limsup_{n\to\infty}\max_{0\leq m\leq n-L_{n}}|S_{L_{n}}\circ
T^{m}|/L_{n}\leq\epsilon.$

As $\epsilon$ was arbitrary this gives the upper bound. ∎

###  7.2 Lower bounds.

Now we suppose there exists $\gamma\geq\beta$, an observable $\varphi$ and an
$\alpha>0$ such that for all $n$,
$\mu\\!\left(\left|\frac{1}{n}S_{n}(\varphi)-\bar{\varphi}\right|>\alpha\right)\geq
C(\alpha)n^{-\gamma}$. We show if we take a window of length $n^{\tau}$,
$\tau<\frac{1}{1+\frac{\beta+1}{\beta}\gamma}$ then the time-averaged
fluctuation persists almost surely. In the case that $\gamma$ limits to
$\beta$ then we require $\tau<\frac{1}{2+\beta}$. Comparing Theorem 7.1 and
Theorem 7.2 there is a gap
$\frac{1}{1+\frac{\beta+1}{\beta}\gamma}<\tau<\frac{1}{\beta}$ for which we
don’t know the almost sure limit of windows of length $n^{\tau}$. In Example
7.3 we show that $\tau<\frac{1}{\beta+1}$ is required to ensure that a time-
averaged fluctuation persists almost surely.

######  Theorem 7.2.

Suppose that $(T,M,\mu)$ is modeled by a Young Tower and
$\bar{\nu}_{\Delta}(R>n)\leq Cn^{-\beta}$. Suppose that $\gamma\geq\beta$ and
there exists a function $C$ which is continuous on a neighborhood of
$\alpha>0$ such that

$\mu\\!\left(\left|\frac{1}{n}S_{n}(\varphi)-\bar{\varphi}\right|>\alpha\right)\geq
C(\alpha)n^{-\gamma}$

Then if $0<\tau<\frac{1}{1+\gamma\frac{\beta+1}{\beta}}$ for $\mu$ a.e. $x\in
M$

$\lim_{n\to\infty}\max_{0\leq m\leq n-n^{\tau}}n^{-\tau}S_{n^{\tau}}\circ
T^{m}(x)\geq\alpha$

###### Proof.

Let $0<\epsilon\ll\alpha$ and put

$A_{n^{\tau}}(\epsilon)=\\{(x,j):\sum_{r=1}^{n^{\tau}}\varphi\circ
F^{r}(x,j)\leq\alpha-\epsilon\\}.$

Since $\varphi$ is Lipschitz continuous with Lipschitz constant $L$, then if
$y\in A_{n^{\tau}}(\epsilon)$ and
$d(y,y^{\prime})<\frac{\epsilon}{2Ln^{\tau}}$, then $y^{\prime}\in
A_{n^{\tau}}(\epsilon/2)$. Hence let us choose $n_{1}$ so that
$K\beta_{1}^{n_{1}}<\frac{\epsilon}{2Ln^{\tau}}$ and define

$B_{n^{\tau}}(\epsilon)=\\{(x,0)\in\Lambda:\exists\>0\leq
j<R(f^{n_{1}}x)~{}\mbox{ with }(f^{n_{1}}x,j)\in
A_{n^{\tau}}(\epsilon)\\}=f^{-n_{1}}(\pi A_{n^{\tau}}(\epsilon)),$

where $\pi:\Delta\to\Lambda$ is the projection given by $\pi((x,j))=(x,0)$
($j<R(x)$). The choice of the integer achieves that if $(x,0)\in
B_{n^{\tau}}(\epsilon)$ and $(x^{\prime},0)\in W^{s}(x,0)$ then
$(f^{n_{1}}x^{\prime},0)\in\pi(A_{n^{\tau}}(\frac{\epsilon}{2}))$. This is a
consequence of Assumption (a). By assumption

$\nu_{\Delta}(A_{n^{\tau}}(\epsilon))\geq C(\alpha-\epsilon)n^{-\gamma\tau}.$

For $\delta>\frac{\tau\gamma}{\beta}$ we have

$\nu_{\Delta}(R>n^{\delta})=o(n^{-\delta})$

as by assumption $\nu_{\Delta}(R>\ell)\leq C\ell^{-\beta}$.

Since $\nu_{\Delta}=\bar{\nu}\times\mbox{ (counting measure) }$ we get for
$D\subset\Delta$

$\bar{\nu}(\pi(D))\geq\frac{\nu_{\Delta}(D)-\nu_{\Delta}(R>n^{\delta})}{n^{\delta}}.$

Consequently

$\bar{\nu}(\pi(A_{n^{\tau}}(\epsilon)))\geq\left(C(\alpha-\epsilon)n^{-\tau\gamma}-o(n^{-\delta\beta})\\!\right)n^{-\delta}$

and since $\delta\beta>\tau\gamma$ the first term dominates and we obtain

$\bar{\nu}(\pi(A_{n^{\tau}}(\epsilon)))\geq c_{1}n^{-\tau\gamma-\delta}$

for some $c_{1}>0$ and since $f^{n_{1}}$ preserves $\bar{\nu}$,

$\bar{\nu}(B_{n^{\tau}}(\epsilon))\geq c_{1}n^{-\tau\gamma-\delta}.$

We can now define

$\tilde{B}_{n^{\tau}}(\epsilon)=\bigcup_{x\in B_{n^{\tau}}(\epsilon)}W^{s}(x)$

which by choice of $n_{1}$ implies that

$\tilde{B}_{n^{\tau}}(\epsilon)\subset B_{n^{\tau}}(\epsilon/2).$

We now approximate $1_{B_{n^{\tau}}}(\epsilon)$ by a function
$h_{n^{\tau}}(\epsilon)$ which has Lipschitz constant $\beta_{1}^{-n^{\tau}}$
in the $d_{\beta_{1}}$-norm, that is we define

$h_{n^{\tau}}(\epsilon)(p)=\max(0,1-d(p,B_{n^{\tau}}(\epsilon)\beta_{1}^{-n^{\tau}})$

where we write $p$ for $(p,0)$. We can choose $n_{1}$ to be much smaller than
$n^{\tau}$ and therefore, since by Assumption (b) and (c) if
$d(p,B_{n^{\tau}}(\epsilon))<\beta_{1}^{\tau_{n}}$ then
$d(f^{n_{1}}p,B_{n^{\tau}}(\epsilon))<K\beta_{1}^{n^{\tau}-n_{1}}<\frac{\epsilon}{2Ln^{\tau}}$
which implies that the support of $h_{n^{\tau}}(\epsilon)$ is contained in
$B_{n^{\tau}}(\epsilon/2)$.

Now we let $\tau_{1}>\tau$ but
$\tau_{1}-\tau<1-(\tau\gamma\frac{\beta+1}{\beta}+\tau)$ and consider

$G_{n}(\epsilon)=\bigcap_{m=0}^{[n/n^{\tau_{1}}]}f^{-mn^{\tau_{1}}}B_{n^{\tau}}(\epsilon)$

We will show that

$\sum_{n}\bar{\nu}(G_{n}(\epsilon))<\infty$

Now

$\displaystyle\bar{\nu}(G_{n}(\epsilon))$ $\displaystyle\leq$
$\displaystyle\bar{\nu}\\!\left(\prod_{m=0}^{n^{1-\tau_{1}}}h_{n^{\tau}}(\epsilon)\circ
f^{mn^{\tau_{1}}}\\!\right)$ $\displaystyle\leq$
$\displaystyle\bar{\nu}(h_{n^{\tau}}(\epsilon))\bar{\nu}(G_{n-1}(\epsilon))+c_{3}\|h_{n^{\tau}}(\epsilon)\|_{\beta_{1}}\||G_{n-1}(\epsilon)|_{\infty}\beta_{3}^{n^{\tau_{1}}}$
$\displaystyle\leq$
$\displaystyle[\bar{\nu}(h_{n^{\tau}}(\epsilon))]^{n^{1-\tau_{1}}}+nC_{3}\beta_{3}^{n^{\tau_{1}}}\beta_{1}^{-n^{\tau}}$

The term $nC_{3}\beta_{3}^{n^{\tau_{1}}}\beta_{1}^{-n^{\tau}}$ is summable in
$n$ as $\tau_{1}>\tau$. The principal term is estimated by

$[\bar{\nu}(h_{n^{\tau}}(\epsilon))]^{n^{1-\tau_{1}}}\leq\left(1-C(\alpha-\frac{\epsilon}{2})n^{-\gamma\tau-\delta}\\!\right)^{n^{1-\tau_{1}}}\leq\exp\\!\left(-C(\alpha-\epsilon/2)n^{1-\tau_{1}-\gamma\tau-\delta}\\!\right)$

Since $\tau_{1}>\tau$ can be chosen arbitrarily close to $\tau$ and
$\delta>\frac{\tau\gamma}{\beta}$ can be chosen to achieve the power
$1-\tau-\tau\gamma-\delta$ is positive for any chosen
$\tau<(1+\gamma\frac{\beta+1}{\beta})^{-1}$ we obtain that the principal terms
are summable which implies summability of $\bar{\nu}(G_{n}(\epsilon)$.

Now define

$E_{n}:=\\{(x,0):\mbox{for all
}j<n:\sum_{r=0}^{n^{\tau}}\varphi(F^{R_{n_{1}}(x)+j+r}x,0)\leq(\alpha-\frac{\epsilon}{2})n^{\tau}\\},$

where $R_{\ell}=\sum_{i=0}^{\ell-1}R\circ f^{i}$ is the $\ell$-th ergodic sum
of $R$. As $E_{n}(\epsilon)\subset G_{n}(\epsilon)$,
$\bar{\nu}(G_{n}(\epsilon))$ summable implies that
$\sum_{n=1}^{\infty}\bar{\nu}(E_{n}(\epsilon))<\infty$.

By Birkhoff’s ergodic theorem

$\lim_{n\to\infty}\frac{R_{n}(x,j)}{n}=\bar{R}=\frac{1}{\nu_{\Delta}(\Lambda)}$

for $\nu_{\Delta}$ a.e. $(x,j)\in\Delta$, and so the theorem follows.

∎

######  Example 7.3.

The condition $\tau<\frac{1}{1+\gamma\frac{\beta+1}{\beta}}$ is close to
optimal in that, taking $\gamma=\beta$, we require $\tau<\frac{1}{2+\beta}$.
We may construct a Young Tower and observable $\varphi$,
$\int_{\Delta}\varphi\,d\nu_{\Delta}=0$ and $\alpha>0$ such that
$\nu_{\Delta}(S_{n_{\tau}}\varphi(x,j)\geq n^{\tau}\alpha)\leq
Cn^{-\tau\beta}$, yet for all $\tau>\frac{1}{\beta+1}$,

$\lim_{n\to\infty}\max_{0\leq m\leq n-n^{\tau}}n^{-\tau}S_{n^{\tau}}\circ
T^{m}=0$

We sketch the main idea of the tower and observable and make a couple of
technical adjustments to ensure the tower is mixing and that the observable is
not a coboundary. The construction is based on that of [1]. The base partition
consists of disjoint intervals $\Lambda_{i}$ of length $i^{-\beta-2}$ and
height $2i$. Above the base element $\Lambda_{i}$ the levels of the tower
consist of $\\{(x,j):0\leq j\leq 2i-1\\}$. We define $\varphi$ on the Tower
by, if $x\in\Lambda_{i}$,

$\varphi(x,j)=\left\\{\begin{array}[]{ll}-1&\mbox{if $0\leq j<i$};\\\
1&\mbox{if $i\leq j<2i$}.\end{array}\right.$

Clearly $\nu_{\Delta}(\varphi)=0$.

Let $0<\alpha<1$. Note that $S_{n_{\tau}}\varphi(x,j)\geq n^{\tau}\alpha$ only
if $(x,j)\in(R>n^{\tau})$ and in fact
$\nu_{\Delta}(S_{n_{\tau}}\varphi(x,j)\geq n^{\tau}\alpha)\geq
C\nu_{\Delta}(R>2n^{\tau})=\sum_{r=2n^{\tau}}^{\infty}(2j)j^{-2-\beta}\leq
Cn^{-\tau\beta}$.

However if $\tau>\frac{1}{\beta+1}$ then $\sum_{j\geq
n^{\tau}}\bar{\nu}(\Lambda_{j})\leq\sum_{n=1}^{\infty}n^{-\tau(\beta+1)}<\infty$.
Hence by the Borel-Cantelli lemma
$f^{n}(x,0)\in\bigcup_{j>n^{\tau}}\Lambda_{j}$ only finitely many times for
$\bar{\nu}$ a.e. $(x,0)$. This implies that for $\bar{\nu}$ a.e. $(x,0)$ there
exists an $N(x)$ such that for all $n\geq N(x)$

$\mbox{for all }j<n:\sum_{r=0}^{n^{\tau}}\varphi(f^{j+r}x,0)<\alpha n^{\tau}.$

Hence for $\mu$ a.e. $x\in M$

$\lim_{n\to\infty}\max_{0\leq m\leq n-n^{\tau}}n^{-\tau}S_{n^{\tau}}\circ
T^{m}<\alpha$

for every $\alpha>0$.

The same argument shows for $\nu_{\Delta}$ a.e. $(x,j)$

$\lim_{n\to\infty}\max_{0\leq m\leq n-n^{\tau}}n^{-\tau}S_{n^{\tau}}\circ
T^{m}=0$

and

$\lim_{n\to\infty}\min_{0\leq m\leq n-n^{\tau}}n^{-\tau}S_{n^{\tau}}\circ
T^{m}=0$

The heights of the levels in the tower above are all multiples of $2$.
Furthermore the observable $\varphi$ is a coboundary. If we define

$\psi(x,j)=\begin{cases}j&\mbox{ if }x\in\Lambda_{k},0\leq j\leq k\\\
2k-j&\mbox{ if }x\in\Lambda_{k},k<j\leq 2k-1\end{cases}.$

It is easy to check that

$\varphi=\psi\circ F-\psi$

We will modify the tower and the observable so that the greatest common
denominator of the return time function $R$ is $1$ (to ensure the tower is
mixing) and that the new observable is not a coboundary. We change
$\Lambda_{3}$ to have height $3$. This entails that the tower is mixing. On
the levels above $\Lambda_{3}$ we modify $\varphi$ to $\varphi_{1}$ so that
$\varphi_{1}(x,j)=\kappa>0$, $j=0,1,2$, $x\in\Lambda_{3}$ where $\kappa>0$ is
small but $\varphi_{1}=\varphi$ elsewhere . This entails
$r_{1}:=\nu_{\Delta}(\varphi_{1})=\kappa\nu_{\Delta}(\Lambda_{3})>0$. We
subtract $r_{1}/(\nu_{\Delta}(\Lambda_{2}))$ from the value of $\varphi_{1}$
on $\Lambda_{2}$ to form a new observable $\varphi_{2}$ such that
$\nu_{\Delta}(\varphi_{2})=0$. Since $F^{3}$ has a fixed point $p$ on
$\Lambda_{3}$ and since $\sum_{j=0}^{2}\varphi_{2}(x,j)\not=0$ we conclude
$\varphi_{2}$ is not a coboundary (by the Liv̌sic theorem [17]). The new tower
with observable $\varphi_{2}$ we defined has the properties of the former
pertinent to our example.

## References

  * [1] Bryc, W and Smolenski, W. On the Convergence of Averages of Mixing Sequences. Journal of Theoretical Probability, Vol 6, (1993), No. 3.
  * [2] Chen, H and Yu, M. A generalization of the Erdős-Rényi limit theorem and the corresponding multifractal analysis. J. Number Theory 192 (2018), 307-327.
  * [3] Chen, H, Ding, D and Long, X. The Hausdorff dimension of level sets described by Erdős-Rényi average. J. Math. Anal. Appl. 458 (2018), no. 1, 464-480.
  * [4] Chernov, N and Zhang, H. K. A family of chaotic billiards with variable mixing rates. Stoch. Dyn. 5 (2005) 535-553.
  * [5] Chazottes, J.-R.; Collet, P.: Almost-sure central limit theorems and the Erdős-Rényi law for expanding maps of the interval. Ergodic Theory Dynam. Systems 25, (2005), 419–441.
  * [6] Deheuvels, P.; Devroye, L.; Lynch, J.: Exact convergence rate in the limit theorems of Erdős-Rényi and Shepp. Ann. Probab. 14 (1986), 209–223.
  * [7] Denker, M.; Kabluchko, Z.: An Erdős-Rényi law for mixing processes. Probab. Math. Statist. 27 (2007), 139–149.
  * [8] Denker, M and Nicol, M. Erdős-Rényi limit laws for hyperbolic dynamical systems. Journal LMS 87(2) (2013), 497–508.
  * [9] Erdős, P.; Rényi, A.: On a new law of large numbers. J. Analyse Math. 23 (1970), 103–111.
  * [10] Grigull, J.: Große Abweichungen und Fluktuationen für Gleichgewichtsmaße rationaler Abbildungen. Dissertation Georg-August-Universität zu Göttingen 1993.
  * [11] Kifer, Y. Functional Erdős-Rényi law of large numbers for nonconventional sums under weak dependence., Elect. J. Probab. 22 (2017), no.23, 1-17.
  * [12] Kifer,Y. Erdős-Rényi law of large numbers in the averaging setup., Stoch. Dyn. 18 (2018), no. 3, 1850018, 26 pp.
  * [13] A. Korepanov, Z. Kosloff and I. Melbourne. Explicit coupling argument for nonuniformly hyperbolic transformations. Proc. Roy. Soc. Edinburgh Sect. A 149 (2019), no. 1, 101-130.
  * [14] Melbourne, I.: Large and moderate deviations for slowly mixing dynamical systems. Proc. Amer. Math. Soc. 137 (2009), 1735–1741.
  * [15] Melbourne, I and Varandas, P. A note on statistical properties for non-uniformly hyperbolic systems with slow contraction and expansion. Stoch. Dyn. 16 (2016), no. 3, 1660012, 13 pp.
  * [16] Melbourne, I.; Nicol, M.: Large deviations for nonuniformly hyperbolic systems. Trans. Amer. Math. Soc. 360 (2008), 6661–6676.
  * [17] Nicol, M; Scott,A. Livšic theorems and stable ergodicity for group extensions of hyperbolic systems with discontinuities. Ergodic Theory Dynam. Systems 23 (2003), no. 6, 1867-1889.
  * [18] Pollicott, M; Sharp, R.: Large deviations for intermittent maps. Nonlinearity 22(9) (2009), 2079–2090.
  * [19] Rey-Bellet, L.; Young, L.-S.: Large deviations in nonuniformly hyperbolic dynamical systems. Ergodic Theory Dynam. Systems 28 (2008) 587–612.
  * [20] Stein, E: Singular integrals and differentiability properties of functions, Princeton University Press, 1986.
  * [21] L.-S. Young. Statistical properties of dynamical systems with some hyperbolicity. _Ann. of Math._ 147 (1998), 585–650.
  * [22] L.-S. Young. Recurrence times and rates of mixing. _Israel J. Math._ 110 (1999), 153–188.