TITLE: Does the convergence of $f_n$ imply the convergence of $\mathbb P[\inf_{0\le s\le t}(W_s-f_n(s))\le 0]$?
QUESTION [0 upvotes]: Let $(f_n)_{n\ge 1}$ be a sequence of non-decreasing and continuous functions defined on $\mathbb R_+$ and taking values in $[0,1]$. Further, for each $t\ge 0$, $n\mapsto f_n(t)$ is non-decreasing. Denote by $f$ the point-wise limit of $(f_n)_{n\ge 1}$ and by $W$ a standard Brownian motion. For every $x>0$ (saying $x=1$), can we prove that the following convergence
$$\lim_{n\to\infty}\mathbb P[\inf_{0\le s\le t}(x+W_s-f_n(s))\le 0] = \mathbb P[\inf_{0\le s\le t}(x+W_s-f(s))\le 0]$$
holds for every $t\ge 0$?
PS : The direction $$\lim_{n\to\infty}\mathbb P[\inf_{0\le s\le t}(W_s-f_n(s))\le -x] \le \mathbb P[\inf_{0\le s\le t}(W_s-f(s))\le -x]$$
is trivial. For the other direction, my idea is as follows : Denote  by $\tau_n$ (resp. $\tau$) the first hitting time of $W-f_n$ (resp. $W-f$) at $-x$. Then
$$\mathbb P[\inf_{0\le s\le t}(W_s-f(s))\le -x]-\mathbb P[\inf_{0\le s\le t}(W_s-f_n(s))\le -x] = \mathbb P[\tau\le t, \tau_n>t]$$
as $\tau\le \tau_n$. Rewrite
\begin{eqnarray}
\mathbb P[\tau\le t, \tau_n>t] &=& \int_{[0,t]}\mathbb P[\tau_n>t|\tau=s]\mathbb P[\tau\in ds]\\
&=&\int_{[0,t)}\mathbb P[\tau_n>t|\tau=s]\mathbb P[\tau\in ds] + \mathbb P[\tau_n>t|\tau=t]\mathbb P[\tau=t].
\end{eqnarray}
How to estimate $\mathbb P[\tau_n>t|\tau=s]$? Is $\mathbb P[\tau=t]=0$?

REPLY [0 votes]: Denote  by $\tau_n$ (resp. $\tau$) the first hitting time of $W-f_n$ (resp. $W-f$) at $-x$. Then
$$\mathbb P[\inf_{0\le s\le t}(W_s-f_n(s))\le -x]=\mathbb P[\tau_n\le t],\quad \mathbb P[\inf_{0\le s\le t}(W_s-f(s))\le -x]=\mathbb P[\tau\le t].$$
One has by assumption $\tau\le \tau_n$ and thus
$$
0\le \mathbb P[\tau\le t]-\mathbb P[\tau_n\le t] =\mathbb P[\tau\le t, \tau_n>t] = \int_{(0,t]}\mathbb P[\tau_n>t|\tau=s]\mathbb P[\tau\in ds],
$$
where the last equality holds as $\tau>0$. Restricted on the set $\{\tau=s\}$ for $s\in (0, t]$, one has
$$\{\tau_n>t\}\subset \{W_s-f_n(s)> -x\}\cap \{W_s-f(s)\le -x\}.$$
This gives
$$\mathbb P[\tau_n>t|\tau=s] \le \mathbb P[f(s)-x<W_s \le f_n(s)-x] \to 0 \mbox{ as } n\to\infty,$$
and we may conclude by the dominated convergence theorem.


text:
\section{Regenerative Policies}
\label{sec:regenerative}

\subsection{Sample Average Estimator (SAE)}
\begin{definition} Consider sampling policy $A$. The SAE for $\alpha$ is
\begin{align}
   \hat{\alpha}_n= \frac{\sum_{j=0}^{n-1} I(A_{j}=1)R_{j+1}}{\max\{1, \sum_{j=0}^{n-1}I(A_{j}=1)\}}-  \frac{\sum_{j=0}^{n-1}I(A_{j}=2)R_{j+1}}{\max\{1,\sum_{j=0}^{n-1}I(A_{j}=2)\}}
\end{align}
\end{definition}
\mr{not sure we need the definition below as the name is self explanatory.}
\begin{definition}
If SAE for sampling policy $A$ is consistent, we call $A$ a SAE-consistent policy.
\end{definition}

\begin{remark}\label{remark: non-optimality reg} One can find an efficient sampling policy for SAE, i.e. a policy with minimum asymptotic scaled variance, within the space of SAE-consistent sampling policies. However the space of such policies is complicated (With SAE a policy might accumulate so much bias that it  never converge which is not the case with MLE.) and adaptive implementation of such policies is complicated as they require estimating all unknown parameters. To address these complexities, in the rest of this section, we focus on a sub-set of SAE-consistent policies denoted by  \emph{regenerative policies}. \mr{I guess we can characterize such space of policies as follows, but I am not sure if it is worth having that here. If a TAR policy with strictly positive policy limit is SAE-consistent then its policy limit $\gamma$ almost surely satisfies
\begin{align}
   \frac{\sum_{x\in S}\gamma(2, x) r(2,x)}{\sum_{x\in S}\gamma(2, x)}-\frac{\sum_{x\in S} \gamma(1,x)r(1,x)}{\sum_{x\in S} \gamma(1,x)}&=\alpha\label{eq: SAE consistent policy limit}.
\end{align}}\end{remark}

\iffalse
\textbf{Comment: We should check the accuracy of the following definition.  It tries to capture the core idea why we like regenerative policies: Because they are so robustly consistent, even if we do not know the rewards or we only measure rewards with an unknown bias, etc.  Note that although in designing optimal regenerative policy (from oracles perspective) we use the knowledge of reward distributions, but the policy itself is not adaptive to the realization of the rewards. The online algorithm we propose nevertheless is adaptive to realization of the rewards, but even the online algorithm is consistent for any distribution of rewards since it only switches at fixed regenerative states. So it is robust but in a weaker sense than the definition below. Basically it is robust even if the observed rewards are biased. Finally we also like regenerative policies because they are computationally easy to implement in the online algorithm, but I do not see an easy way to define such property!}

\textbf{This definition plus Theorem \ref{thm: reg robust SAE-consistency} try to show some notion of optimality for regenerative policies. If we can not fix them, we can simply delete both and just mention regenerative policies are practically easy to implement with out an exact definition.}
\begin{definition}[Robust SAE-Consistent] A sampling policy is robust consistent if it is not adaptive to the realizations of the rewards i.e. adaptive to $\mathcal{G}'_n=\sigma\big((X_j, U_j): 0\le j\leq n\big)$ for $n\ge 0$, and at the same time is consistent for any distribution or rewards.
\end{definition}\fi

\subsection{Review of the Regenerative Processes}
We provide a quick review theory of regenerative policies required for presenting our results. The reader can find the details in \cite{shedler2012regeneration}.

\begin{definition} [Regenerative Process]
The stochastic process $X(n):n \ge 0$ is a regenerative process provided that:
\begin{itemize}
\item there exists a sequence  $\{N_k:k \ge 0\}$ of stopping times such that $\{N_{k+1} -  N_k:k \ge 0\}$ are independent and identically
distributed; and
\item for every sequence of times $0 < n_1 < n_2 < ... < n_m, (m \ge 1)$ and $k \ge 0$, the random vectors $\{X(n_1), ... ,X(n_m)\}$
and $\{X(N_k + n_1), ... ,X(N_k + n_m )\}$ have the same distribution and the processes $\{X(n):n < N_k\}$ and $\{X(N_k + n): n \ge 0\}$ are independent.
\end{itemize}
\end{definition}

\begin{definition} [Regenerative Cycle] The stochastic process from each $N_k$ to $N_{k+1}$ is called a regenerative cycle with length $\eta_k=N_{k+1}-N_k$.
\end{definition}

\begin{theorem}\label{prop: iid} Denoting $Y_k=\sum_{j=N_{k-1}}^{N_{k}} r(Xj)$, the pairs $\{\eta_k, Y_k\}, k=1,2,...$ are independent and identically distributed random variables.
\end{theorem}

\begin{theorem} \label{prop: steady state} For any regenerative process there exist a vector $\tilde{\pi}$ such that for every state $x\in S$, $\tilde{\pi}(x)\in [0,1]$ and
\begin{align}
    \tilde{\pi}(x)= \lim_{n\rightarrow\infty} P(X_n=x).
\end{align}
$\tilde\pi$ is the stationary distribution for the regenerative process. Moreover
\begin{align}\label{eq: reg rev 2}
\frac{1}{n} \sum_{j=0}^{n-1} r(X_j)\xrightarrow{a.s.} {E}_{\tilde\pi}\{r(X)\}=\frac{{E}\{Y_1\}}{{E}\{\eta_1\}}
\end{align}
as $n\rightarrow \infty$.
\end{theorem}

\begin{proposition}\label{prop: markov chain reg}
The state trajectory, $X_n, n=1,2,...$, of an irreducible Markov chain is a regenerative process with stopping times $N_k=\{n>N_{K-1}, x_n=x^r\}$, where $x^r \in S$. Moreover, the distribution of states between $N_k$ and $N_{k+1}$ are according to the stationary distribution of the Markov chain.
\end{proposition}

\begin{definition} [x-cycle] A sample of a Markov chain is a $x$-cycle if it corresponds to a path starting from state $x$ and ending in state $x$.
\end{definition}

\subsection{Regenerative Policies}
\begin{definition} Policy $A$ is regenerative with regenerative state $x^r\in S$ if $A_{n}=A_{n-1}$ with probability one whenever $X_{n-1}\neq x$.
\end{definition}

\begin{remark}
A regenerative policy is of the following form: fix state $x^r$. At every time $n$, if the Markov chain hits state $x^r$, start running a chain under $P(1)$ with probability $p^r_n$ or $P(2)$ with probability $1-p^r_n$. In general, $p^r_n$ is adaptive to filtering $\mathcal{G}_n$.
\end{remark}

\begin{remark}\label{rem: concatenating}
With a regenerative policy, concatenating all the samples under $P(\ell)$ forms a regenerative process. Furthermore, the statistics of this process is similar to a single run of $P(\ell)$ for the length of the concatenated process. \mr{do we need a reference or proof for this remark?}
\end{remark}
\iffalse
\textbf{Comment: We should check the following theorem and proof for accuracy.}
\begin{theorem}[Robust SAE-Consistency of Regenerative Policies]\label{thm: reg robust SAE-consistency} Every regenerative policy is SAE-consistent and the asymptotic variance of every robust SAE-consistent policy can be achieved with a regenerative policy.
\end{theorem}
\textbf{PROOF}
 A regenerative policy adapts to $\mathcal{G}'$ and considering Remark \ref{rem: concatenating}, it is robust SAE-consistent. On the other hand, for a policy $A$ to be robust SAE-consistent it requires that
\begin{align}\label{eq: sample average 1}
    \frac{\sum_{j=0}^{n-1} I(A_{j}=2)R_{j+1}}{\sum_{j=0}^{n-1}I(A_{j}=2)}-\frac{\sum_{j=0}^{n-1} I(A_{j}=1)R_{j+1}}{\sum_{j=0}^{n-1}I(A_{j}=1)}\xrightarrow{a.s.} TE
\end{align}
for all reward distributions.

Using Poisson equation (\ref{eq: Poisson Equation}), and fundamental functions $\tilde{g}(\ell)$ in (\ref{eq: fundamental matrix solution}) we have
\begin{align}
    & \frac{\sum_{j=0}^{n-1} \big(R_{j+1}-\alpha(\ell)\big)I(A_{j}=\ell)}{n}\\
    = & \frac{\sum_{j=0}^{n-1} \big(R_{j+1}-r(\ell, X_{j+1})\big)I(A_{j}=\ell)}{n}+\frac{\sum_{j=0}^{n-1} \big(r(\ell, X_{j+1})-\alpha(\ell)\big)I(A_{j}=\ell)}{n}\\
    = & \frac{\sum_{j=0}^{n-1} \big(R_{j+1}-r(\ell, X_{j+1})\big)I(A_{j}=\ell)}{n}+ \frac{\sum_{j=0}^{n-1} \big(\tilde{g}(\ell, X_{j+1})-\big(P(\ell)\tilde{g}(\ell)\big)( X_{j+1})\big)I(A_{j}=\ell)}{n}\\
    =& \frac{\sum_{j=1}^{n-1} \big(R_{j+1}-r(\ell, X_{j})\big)I(A_{j}=\ell)}{n}-
    \frac{\sum_{j=0}^{n-1} \big(r(\ell, X_{j+1})- r(\ell, X_{j})\big)I(A_{j}=\ell)}{n}\nonumber\\
    &+ \frac{\sum_{j=1}^{n-1} \big(\tilde{g}(\ell, X_j)-\big(P(\ell)\tilde{g}(\ell)\big)( X_{j-1})\big)I(A_{j-1}=\ell)}{n}\nonumber\\
    &- \frac{\sum_{j=0}^{n-1} \big(P(\ell)\tilde{g}(\ell)\big)(X_{j+1})-\big(P(\ell)\tilde{g}(\ell)\big)( X_{j})\big)I(A_{j}=0)}{n}\nonumber\\
    &+\frac{R(\ell, X_1)I(A_{0}=\ell)}{n}+ \frac{\tilde{g}(\ell, X_1)I(A_{0}=\ell)}{n}\\
    =&\frac{\sum_{j=1}^{n-1} D_j(\ell)}{n}\nonumber\\
    &-\frac{\sum_{j=0}^{n-1} \big(r(\ell, X_{j+1})- r(\ell, X_{j})\big)I(A_{j}=\ell)}{n}- \frac{\sum_{j=0}^{n-1} \big(P(\ell)\tilde{g}(\ell)\big)( X_{j+1})-\big(P(\ell)\tilde{g}(\ell)\big)( X_{j})\big)I(A_{j}=\ell)}{n}\nonumber\\
    &+O(\frac{1}{n})
\end{align}
where
\begin{align}
    D_j(\ell):= I(A_{j}=\ell)\big[\tilde{g}(\ell,X_{j+1})-\big(\big(P(\ell)\tilde{g}(\ell)\big)\big)(X_{j})+R_{j+1}-r(\ell,X_{j})\big].
\end{align}
Note that since $D_j$s are martingale differences, by standard application of martingale law of large numbers we have
\begin{align}
\frac{\sum_{j=1}^{n} D_j(\ell)}{n}\xrightarrow{a.s.} 0
\end{align}
as $n\rightarrow \infty$. Next consider
\begin{align}
    -\frac{\sum_{j=0}^{n-1} \big(r(\ell, X_{j+1})- r(\ell, X_{j})\big)I(A_{j}=\ell)}{n}- \frac{\sum_{j=0}^{n-1} \big(P(\ell)\tilde{g}(\ell)\big)( X_{j+1})-\big(P(\ell)\tilde{g}(\ell)\big)( X_{j})\big)I(A_{j}=\ell)}{n}\label{eq: zero differences reg}
\end{align}
Note that the above sum is collapsing in the intervals in which $A_{j-1}\neq \ell$. Set,
\begin{align}
    T_1&=\inf\{k\ge 0: A_k=1\}\\
    T_2&= \inf\{k> T_1: A_k=2\}\\
    T_{2j+1}&= \inf\{k> T_{2j}: A_k=1\}\\
    T_{2j}&=\inf\{k> T_{2j-1}: A_k=2\}\\
    N_n(1)&=\frac{1}{2}\max\{2j: T_j\leq n\}\\
    N_n(2)&=\frac{1}{2}\bigg(\max\{2j+1: T_j\leq n\}-1\bigg)\\
    N_n&=\max\{j: T_j\leq n\}.
\end{align}
Then, (\ref{eq: zero differences reg}) for $\ell=1$ is equal to
\begin{align}
    W_n(1)=&-\frac{\sum_{j=1}^{N_n(1)} \big(r(1, X_{T_{2j-1}})-r(1, X_{T_{2j}})\big)}{n}\nonumber\\
    &-\frac{\sum_{j=0}^{N_n(1)} \big(P(1)\tilde{g}(1)\big)( X_{T_{2j-1}}\big)-\big(P(1)\tilde{g}(1)\big)( X_{T_{2j}})\big)}{n}\label{eq: zero differences reg 2}
\end{align}
and for $\ell=2$ is
\begin{align}
    W_n(2)=&-\frac{\sum_{j=1}^{N_n(2)} \big(r(2, X_{T_{2j}})-r(2, X_{T_{2j-1}})\big)}{n}\nonumber\\
    &-\frac{\sum_{j=1}^{N_n(2)} \big(P(2)\tilde{g}(2)\big)( X_{T_{2j}}-\big(P(2)\tilde{g}(2)\big)( X_{T_{2j-1}})\big)}{n}\label{eq: zero differences reg 2.5}
\end{align}
Denote
\begin{align}
    \frac{1}{n} I(A_j=\ell)=\overline{\gamma}_n(\ell).
\end{align}
Then (\ref{eq: sample average 1}) holds if and only if
\begin{align}
    \frac{W_n(2)}{\overline{\gamma}_n(2)}-\frac{W_n(1)}{\overline{\gamma}_n(1)}\xrightarrow{a.s.} 0\label{eq: zero differences reg 3}
\end{align}
\iffalse (\ref{eq: zero differences reg 3}) holds for all $P(\ell)$ and $F^{-1}(\cdot,x,y,\ell)$ in the case when,
\begin{align}
    W_n(\ell)\rightarrow 0 \qquad a.s.
\end{align}\fi
\textbf{Comment: the arguments below could still be made more precise mathematically.}
Since the robust SAE-consistent policy does not adapt to the realizations of the rewards, this condition should hold for all possible rewards. Therefore, it can happen under two conditions. The first case is the number of switches from $P(1)$ to $P(2)$ grows sub-linearly almost  surely. In this case, either $\overline{\gamma}(1)\xrightarrow{a.s.} 0$ or $\overline{\gamma}(2)\xrightarrow{a.s.} 0$. This consequently results in asymptotic variance reducing at rate lower $n^{1/2}$ as we will show in  (\ref{eq: SAE Asym Var}). (\ref{eq: zero differences reg 3}) also holds if for every state $x\in S$, asymptotically the number of times the algorithm starts $\ell$-cycle from state $x$ is equal to the number of times it ends $\ell$-cycle with state $x$ with probability $1$. In this case, one can concatenate a permutation of4 all $\ell$-cycles to make a long $\ell$-chain with fraction of $\ell$ chains sample from total samples equal to $\gamma(\ell)=\sum_{x}\gamma(\ell, x)$. The same long chains could be achieved by concatenating a cycles from a regenerative policy that sample from both chains with fractions $\gamma(\ell)$ (see (\ref{eq: p from  p'}) for details of constructing such policy). This regenerative policy has the same asymptotic variance as the original robust SAE-consistent policy under SAE.
\qed
\fi

Denote the number of samples of $P(\ell)$ by time $n$ with $S_n(\ell)$. By Remark \ref{rem: concatenating} concatenating the samples from $P(\ell)$ is statistically equivalent to running a single chain of $P(\ell)$ at stationary state. Denote the sample $j$ of concatenation $\ell$ by $X^{P(\ell)}_j$ and its reward by $R^{P(\ell)}_j$. Also, denote the number of $P(\ell)$ $x^r$-cycles in the first $m$ cycles with $C_m(\ell, x^r)$ and denote by $\eta_j(\ell, x^r)$ the length of the $j$th $x^r$-cycle of $P(\ell)$. Denote the number of $P(\ell)$ samples in the first $m$ cycles with $n( m, \ell)=\sum_{j=1}^{C_m(1, x^r)}\eta_j(1, x^r)$. The number of total samples by the end of first $m$ cycles is $n(m)=n(m, 1)+n(m,2)$. $\eta(\ell, x^r$ denotes the expected length of a $P(\ell)$ $x^r$-cycle.

\begin{proposition}\label{prop: reg policy limit} If a regenerative policy is TAR, then its policy limit $\gamma$ satisfies
\begin{align}
   \gamma(1, x)=q^r\pi(1, x), \gamma(2, x)=(1-q^r)\pi(2, x) \qquad \text{  for all } x\in S \label{eq: reg policy limit}
\end{align}
where $q^r$ is a random variable over $[0,1]$.
\end{proposition}
\begin{proof} If $C_m(\ell, x^r)\not\rightarrow \infty$, eventually there will be only a single run of Markov chain $-\ell$ and the result is obvious. Other wise, from Remark \ref{rem: concatenating} concatenating all samples under $P(\ell)$ is statistically equivalent to infinite samples of a single run of chain $\ell$ with stationary distribution $\pi(\ell)$. Therefore,
\begin{align}
    \gamma(\ell, x)=\frac{\pi(\ell, x)\gamma(\ell, x^r)}{\pi(\ell, x^r)}.
\end{align}
Note that since $\sum_{x, \ell} \gamma(\ell, x)=1$
\begin{align}
    \frac{\gamma(1, x^r)}{\pi(1, x^r)}=1-\frac{\gamma(2, x^r)}{\pi(2, x^r)}.
\end{align}
Therefore, setting
\begin{align}
    q^r=\frac{\gamma(1, x^r)}{\pi(1, x^r)}
\end{align}
gives the result.
\end{proof}

\begin{remark}[Markov Equivalence of a Regenerative Policy]\label{rem: Markov equivalence}
From Proposition \ref{prop: reg policy limit} and policy limits of Markov policies \mr{I think we should we have a separate proposition for limits of Markov policies in previous sections and reference it here?}, for a TAR regenerative policy with policy limits $\gamma$, the following Markov policy achieves the same policy limits
	\begin{align}\label{eq: Markov equiv reg}
	p(x)= \frac{q^r\pi(1,x)}{q^r\pi(1,x)+(1-q^r)\pi(2,x)}.
\end{align}
\end{remark}

\begin{corollary}\label{cor: SAE consistency}
Every regenerative policy with $\lim_{m\rightarrow \infty} C_m(\ell, x^r)$ almost surely for both $\ell=1,2$ is SAE-consistent.
\end{corollary}
\begin{proof}
Consider each chain $X_j^{P(\ell)}$. Then,
\begin{align}
    \frac{\sum_{j=0}^{n(m)-1} I(A_{j}=1)R_{j+1}}{\max\{1, \sum_{j=0}^{n(m, 1)}I(A_{j}=1)\}}=\frac{\sum_{j=0}^{n(m,1)} R^{P(\ell)}_{j+1}}{\max\{1, n(m,1)\}}
\end{align}
The limit of the right hand side from Remark \ref{rem: concatenating} almost surely converges to $\alpha(1)$. In the same way, $\frac{\sum_{j=0}^{n-1}I(A_{j}=2)R_{j+1}}{\max\{1,\sum_{j=0}^{n-1}I(A_{j}=2)\}}$ almost surely converges to $\alpha(2)$. The proposition follows.
\end{proof}

\begin{definition}
We call a regenerative policy stationary if for all $n$, $p^r_n=p^r$  where $p^r\in [0,1]$ is a random variable.
\end{definition}
\begin{proposition}\label{prop: stationary reg policy limits}
The policy limits of a stationary regenerative policy are
\begin{align}\label{eq: stationary reg limit}
   \gamma(1, x)=q^r\pi(1, x), \gamma(2, x)=(1-q^r)\pi(2, x).
\end{align}
where
\begin{align}\label{eq: q from p}
    q^r=\frac{p^r\eta(1, x^r)}{p^r\eta(1, x^r)+(1-p^r)\eta(2, x^r)}
\end{align}
is a random variable in $[0,1]$. Furthermore, for every policy limit $\gamma$ that is in $\mathcal{K}$ characterized in Definition \ref{def: mathcal K} almost surely, and also satisfies (\ref{eq: reg policy limit}), there exists a stationary regenerative policy with policy limits equal to $\gamma$.
\end{proposition}
\begin{proof}
 If $p^r=0$ or $p^r=1$ then we have one run of $P(1)$ or $P(2)$ correspondingly and the results are obvious. If $p^r\in (0,1)$, then  $C_m(\ell, x^r)\rightarrow \infty$ for $\ell\in \{1, 2\}$. Also by law of large numbers
\begin{align}
\frac{C_m(1, x^r)}{m}\xrightarrow{a.s} p^r, \frac{C_m(2, x^r)}{m}\xrightarrow{a.s} (1-p^r)
\end{align}
as $m\rightarrow \infty$. From Theorem \ref{prop: iid}, and law of large numbers
\begin{align}
    \frac{\sum_{j=1}^{C_m(\ell, x^r)} \eta_j(\ell, x^r)}{C_m(\ell, x^r)}\xrightarrow{a.s.} \eta(\ell, x^r)
\end{align}
as $m\rightarrow \infty$. Consequently, conditioning on the event that $p^r=p^r_0$ where $p^r_0\in (0,1)$ is a constant applying Slutsky's lemma gives (note that $\eta_j(\ell, x^r)$ is independent of $p^r$)
\begin{align}
    \frac{1}{m}\sum_{j=1}^{C_m(\ell, x^r)} \eta_j(\ell, x^r)&= \frac{C_m(\ell, x^r)}{m} \times \frac{\sum_{j=1}^{C_m(\ell, x^r)} \eta_j(\ell, x^r)}{C_m(\ell, x^r)}\\
    &\xrightarrow{a.s.} p^r_0\eta(\ell, x^r)
\end{align}
as $m\rightarrow \infty$. Another application of Slutsky's lemma gives the limit fraction of the samples of the $P(1)$ chain by the end of $m$ cycles:
\begin{align}\label{eq: sample fraction reg}
    \frac{\sum_{j=1}^{C_m(1, x^r)} \eta_j(1)}{\sum_{j=1}^{C_m(1, x^r)} \eta_j(1)+\sum_{j=1}^{C_m(2, x^r)} \eta_j(2)}\xrightarrow{a.s.} \frac{p^r_0\eta(1, x^r)}{p^r_0\eta(1, x^r)+(1-p^r_0)\eta(2)}.
\end{align}
Similarly, a limit fraction  $(\frac{(1-p^r_0)\eta(2, x^r)}{p^r_0\eta(1)+(1-p^r_0)\eta(2, x^r)})$ of total samples is allocated to $P(2, x^r)$. Since by Remark \ref{rem: concatenating}, concatenating samples under $P(\ell)$ results in a chain with statistics similar to a $P(\ell)$ chain in stationary distribution (independent of $p^r$),
\begin{align}
\gamma(1, x)&= \frac{p^r_0\eta(1, x^r)}{p^r_0\eta(1, x^r)+(1-p^r_0)\eta(2, x^r)}\pi(1,x^r),\\
\gamma(2,x)&=\frac{(1-p^r_0)\eta(2)}{p^r_0\eta(1, x^r)+(1-p^r_0)\eta(2, x^r)}\pi(2,x^r).
\end{align}
Therefore, setting
\begin{align}
    q^r=\frac{p^r\eta(1, x^r)}{p^r\eta(1, x^r)+(1-p^r)\eta(2, x^r)}
\end{align}
gives (\ref{eq: stationary reg limit}).

Next, assume $\gamma$ is a TAR policy limit that satisfies (\ref{eq: stationary reg limit}). Set
\begin{align}\label{eq: p from q}
    p^r=\frac{q^r\eta(2, x^r)}{(1-q^r)\eta(1,x^r)+q^r\eta(2,x^r)}.
\end{align}
The corresponding stationary regenerative policy has limits $\gamma$.

\end{proof}

\begin{proposition}\label{prop: non-stationary equvalence reg} For every TAR regenerative policy, there exists a stationary regenerative policy which achieves the same policy limits.
\end{proposition}
\begin{proof}
From Proposition \ref{prop: reg policy limit}, $\gamma(1,x)=q^r\pi(1,x), \gamma(2,x)=(1-q^r)\pi(2,x)$. Set $p^r=\frac{q^r\eta(2, x^r)}{(1-q^r)\eta(1,x^r)+q^r\eta(2,x^r)}$. Then from Proposition \ref{prop: stationary reg policy limits}, the policy limits of this stationary regenerative policy are also $\gamma$.
\end{proof}

\begin{remark}
Proposition \ref{prop: reg policy limit} and \eqref{eq: reg policy limit} show that the policy limits corresponding to TAR regenerative policies form a subspace of the entire TAR policy limits characterized in Proposition \ref{prop: policy limits}. Proposition \ref{prop: non-stationary equvalence reg} shows the space of policy limits of stationary regenerative policies and that of all TAR regenerative policies are equivalent.
\end{remark}

\begin{remark} From
Proposition \ref{prop: stationary reg policy limits} and Theorem \ref{thm:CLT}, under MLE one can search the space of stationary regenerative policies for finding an efficient regenerative policy \mr{How can we extend this to SAE? It requires extension of Theorem \ref{thm: clt sae reg} to non-stationary regenerative policies}.
\end{remark}

\begin{theorem}[CLT of SAE with Regenerative Policies]\label{thm: clt sae reg} For stationary regenerative policy $A$ with almost surely $p^r\in (0,1)$ and SAE
\begin{align}\label{eq: SAE clt}
    \sqrt{n}(\alpha_n-\alpha)\Rightarrow \sum_{x\in S} \frac{\sqrt{\pi(1, x)}\sigma(1,x)}{\sqrt{q^r}} G(1, x)- \sum_{x\in S} \frac{\sqrt{\pi(2, x)}\sigma(2,x)}{\sqrt{1-q^r}}G(2,x)
\end{align}
where
\begin{align}
    q^r=\frac{p^r\eta(1, x^r)}{p^r\eta(1, x^r)+(1-p^r)\eta(2, x^r)}.
\end{align}
\end{theorem}
\begin{proof}
Conditioning on $p^r=p^r_0>0$, from (\ref{eq: sample fraction reg}), the asymptotic fraction of samples from chain $1$ is
\begin{align}
 q^r_0=\frac{p^r_0\eta(1, x^r)}{p^r_0\eta(1, x^r)+(1-p^r_0)\eta(2, x^r)}.
\end{align}
Since almost surely $p^r\in (0,1)$, so is $q^r$.
\begin{align}
	\alpha_n=& \frac{\sum_{j=0}^{n-1} I(A_{j}=1)R_{j+1}}{\sum_{j=0}^{n-1}I(A_{j}=1)}-  \frac{\sum_{j=0}^{n-1}I(A_{j}=2)R_{j+1}}{\sum_{j=0}^{n-1}I(A_{j}=2)}\\
	=&\frac{1}{\ceil{q^r_0n-1}}\sum_{j=0}^{\ceil{q^r_0n-1}} R^{P(1)}_j- \frac{1}{\ceil{(1-q^r_0)n-1}}\sum_{j=0}^{\ceil{(1-q^r_0)n-1}} R^{P(2)}_j\nonumber\\
	&+\bigg(\frac{\sum_{j=0}^{n-1} I(A_{j}=1)R_{j+1}}{\sum_{j=0}^{n-1}I(A_{j}=1)}- \frac{1}{\ceil{q^r_0n-1}}\sum_{j=0}^{\ceil{q^r_0n-1}} R^{P(1)}_j\bigg)\nonumber\\ &-\bigg(\frac{\sum_{j=0}^{n-1}I(A_{j}=2)R_{j+1}}{\sum_{j=0}^{n-1}I(A_{j}=2)}-\frac{1}{\ceil{(1-q^r_0)n-1}}\sum_{j=0}^{\ceil{(1-q^r_0)n-1}} R^{P(2)}_j\bigg)\\
	&=\frac{1}{\ceil{q^r_0n-1}}\sum_{j=0}^{\ceil{q^r_0n-1}} R^{P(1)}_j- \frac{1}{\ceil{(1-q^r_0)n-1}}\sum_{j=0}^{\ceil{(1-q^r_0)n-1}} R^{P(2)}_j+O(n^{-1}).
\end{align}
On the other hand, similar to the proof of Theorem \ref{thm:CLT}
\begin{align}
	\frac{1}{\ceil{q^r_0n-1}}\sum_{j=0}^{\ceil{q^r_0n-1}} R^{P(1)}_j-\alpha(1)&= \frac{1}{\ceil{q^r_0n-1}}\sum_{x\in S}\sum_{j=1}^{n}D^{P(\ell)}_j(1,x)+O(n^{-1})\label{eq: Dj(l,x) 2}
\end{align}
and
\begin{align}
     \frac{1}{\ceil{(1-q^r_0)n-1}}\sum_{j=0}^{\ceil{(1-q^r_0)n-1}} R^{P(2)}_j-\alpha(2)= \frac{1}{\ceil{(1-q^r_0)n-1}}\sum_{x\in S}\sum_{j=1}^{n}D^{P(\ell)}_j(2,x)+O(n^{-1})\label{eq: Dj(l,x) 3}
\end{align}
where
\begin{align}
    D^{P(\ell)}_j(\ell,x):= I(X_{j-1}=x, A_{j-1}=\ell)\big[\tilde{g}(\ell,X_j)-\big(P(\ell)\tilde{g}(\ell)\big)(X^{P(\ell)}_{j-1})+R^{P(\ell)}_j-r(\ell,X_{j-1}^{P(\ell)})\big].
\end{align}
Note that $D^{^{P(\ell)}}_j(\ell,x)$s are martingale differences measurable with respect to $\mathcal{G}_j$.  Since they are bounded by $2\max\{|\tilde{g}(\ell,x)|: x\in S, \ell=1,2\}<\infty$ due to $r(\ell,x)$ being finite, the following conditional Lindeberg's condition holds (Eq. (3.7) of \cite{hall1980martingale}):
\begin{align}
    \text{for all } \epsilon>0, \quad \sum_{j=1}^{n}\frac{1}{n}E[D^{P(\ell)}_j(\ell,x)^2I(|D^{P(\ell)}_j|> \epsilon)|\mathcal{G}_{j-1}]\xrightarrow{p} 0.
\end{align}
Furthermore, from the proof of Proposition \ref{prop: stationary reg policy limits},
\begin{align}
    \frac{1}{n} \sum_{j=1}^{n} E\big\{D^{P(\ell)}_j(\ell,x)^2|\mathcal{G}_{j-1}\big\}&= \frac{1}{n} \sum_{j=0}^{n-1} I(X_j=x, A_j=\ell)\sigma^2(\ell,x)\\%Also, is it clear that the conditional variances are RHS?
    &= \sigma^2(\ell,x)\frac{\Gamma_n(\ell,x)}{n}\\
    &\xrightarrow{p} \sigma^2(\ell,x)q^r_0\pi(\ell,x).
\end{align}
Therefore, using the martingale central limit theorem,
\begin{align}	 \frac{1}{\ceil{q^r_0n-1}}\sum_{x\in S}\sum_{j=1}^{n}D_j(1,x)+O(\frac{1}{n})\Rightarrow\sum_{x\in S} \frac{\sqrt{\pi(1, x)}\sigma(1,x)}{\sqrt{q^r_0}} G(1, x)
\end{align}
Similar results can be derived for $ \frac{1}{\ceil{(1-q^r_0)n-1}}\sum_{x\in S}\sum_{j=1}^{n}D_j(2,x)+O(\frac{1}{n})$. Considering the independence of $p^r$ from $R_j^{P(\ell)}$.
\end{proof}

\begin{corollary}
\label{cor:var_lowerbound reg}
Let $A$ be a TAR regenerative policy with almost surely $p^r\in (0,1)$ and associated SAE $\hat{\alpha}_n$.
Then there holds:
\begin{equation}
\label{eq:var_lowerbound reg}
\liminf_{n \to \infty} n \Var(\hat{\alpha}_n - \alpha) \geq \sum_{x\in S} \frac{1}{E\{q^r\}} \pi(1, x)\sigma^2(1,x)+ \sum_{x\in S} \frac{1}{E\{1-q^r\}} \pi(2, x)\sigma^2(2,x).
\end{equation}
\end{corollary}
\begin{proof}
Note that the Skorohod representation theorem together with Fatou's lemma applied to \eqref{eq: SAE clt} yields the following:
\begin{equation}
\label{eq:fatou_var_lowerbound reg}
    \liminf_{n \to \infty} n \Var(\hat{\alpha}_n - \alpha) \geq \sum_{x\in S} E\big\{\frac{1}{q^r}\big\} \pi(1, x)\sigma^2(1,x)+ \sum_{x\in S} E\big\{\frac{1}{1-q^r}\big\} \pi(2, x)\sigma^2(2,x).
\end{equation}
Using Jensen's inequality on the right hand side of \eqref{eq:fatou_var_lowerbound reg}, we obtain the result in \eqref{eq:var_lowerbound reg}, as required.  (Note that $E\{\gamma(\ell,x)\} > 0$ for all $\ell,x$ since we assumed $q^r\in (0,1)$ almost surely.)
\end{proof}

\begin{corollary}\label{thm: asym var sample average} Let $A$ be a stationary regenerative policy with constant $p^r\in (0,1)$ and associated SAE $\hat{\alpha}_n$.
Then there holds:
\begin{align}\label{eq: SAE Asym Var}
    \lim_{n\rightarrow \infty} n Var(\hat{\alpha}_n-\alpha_n)= \sum_{x\in S} \frac{1}{q^r} \pi(1, x)\sigma^2(1,x)+ \sum_{x\in S} \frac{1}{1-q^r} \pi(2, x)\sigma^2(2,x).
\end{align}
\end{corollary}
\begin{proof}
Since $p^r$ is constant in $(0,1)$, so is $q^r$. Considering that $D^{P(\ell)}_j$s are martingale differences,
\begin{align}
	{n} Var(\frac{1}{\ceil{q^rn-1}}\sum_{j=1}^{\ceil{q^rn-1}}{D^{P(1)}_j(1, x)})&= \frac{n}{\ceil{q^rn-1}^2} \sum_{j=0}^{\ceil{q^rn-1}} Var({D^{P(1)}_j}(1, x))\\
	&\rightarrow \frac{1}{q^r} \sum_{x\in S} E_{\pi(1)}\{{D^{P(1)}_j}(1,x)^{2}\}\\
	&=	\frac{1}{q^r} \sum_{x\in S} \pi(1, x)\sigma^2(1,x)\\
	&= 	 \sum_{x\in S} \frac{1}{q^r} \pi(1, x)\sigma^2(1,x)
\end{align}
In the same way,
\begin{align}
	&nVar(\frac{1}{\ceil{(1-q^r)n-1}}\sum_{j=1}^{\ceil{(1-q^r)n-1}}{{D}^{P(2)}_j}(2,x)\rightarrow\sum_{x\in S} \frac{1}{1-q^r} \pi(2, x)\sigma^2(2,x)
\end{align}
Therefore,
\begin{align}
    n Var(\alpha_n)\rightarrow \sum_{x\in S} \frac{1}{q^r} \pi(1, x)\sigma^2(1,x)+ \sum_{x\in S} \frac{1}{1-q^r} \pi(2, x)\sigma^2(2,x)
\end{align}
\end{proof}

\begin{remark} For irreducible $P(\ell)$s and stationary regenerative policies with constant and strictly positive $p^r$, the choice of the regeneration state $x^r$ does not effect the scaled asymptotic variance of the SAE since (\ref{eq: SAE Asym Var}) is independent of such choice.
\end{remark}

\begin{remark}[Equivalence of MLE and SAE for Regenerative Policies]\label{thm: equiv sae mle} From Corollaries \ref{cor:asymptotic_var_constant_TAR} and \ref{thm: asym var sample average}, and Proposition \ref{prop: stationary reg policy limits}, stationary regenerative policy $A$ with constant $p^r\in (0,1)$ results in same scaled asymptotic variance for SAE and MLE.
\end{remark}

We now characterize efficient regenerative policies, i.e., those that achieve minimum scaled asymptotic variance within the class of TAR stationary regenerative policies with almost surely $p^r\in (0,1)$ (Note that we know such policies are consistent from Corollary \ref{cor: SAE consistency}, and thus we focus solely on asymptotic variance in considering efficiency).  We show that the policy limits of any such policy can be characterized via the solution to a particular convex optimization problem (We require the mild additional assumption in this section that $\sum_{x\in S} \pi(1,x)\sigma^2(\ell,x) > 0$ for $\ell=1,2$; this will hold, e.g., if rewards are random in some states for each $P(\ell)$. \mr{can we extend to non-stationary policies?}

We start with the following formal definition of efficiency.
\begin{definition}
\label{def:efficient reg}
Let $A^*$ be a stationary regenerative policy with almost surely $p^r\in (0,1)$ and associated MLE $\hat{\alpha}^*_n$.  We say that $A^*$ is {\em efficient} if it has lower (scaled) asymptotic variance than any other stationary regenerative policy with almost surely $p^r\in (0,1)$; i.e., for any such policy $A$ with associated MLE $\hat{\alpha}_n$, there holds:
\begin{equation}
\label{eq:efficient reg}
 \limsup_{n \to \infty} n \Var(\hat{\alpha}^*_n - \alpha) \leq \liminf_{n \to \infty} n \Var(\hat{\alpha}_n - \alpha).
 \end{equation}
\end{definition}

We now identify the optimal policy among the class of stationary regenerative policies with almost surely $p^r\in (0,1)$.
\begin{theorem}[Optimal Regenerative Policy]\label{thm: optimal reg policy} Define
	\begin{align}
	\overline{\sigma}^2(1)=\sum_{x\in S} \pi(1,x)\sigma^2(1,x),\\	\overline{\sigma}^2(2)=\sum_{x\in S} \pi(2,x)\sigma^2(2,x).
		\end{align}
 	 Assume $\overline{\sigma}^2(1)>0$ for $\ell=1,2$. Then a regenerative policy with
	\begin{align}\label{eq: optimal p'}
		{p^r}^* =\frac{\eta(2){\overline{\sigma}}(1)}{\eta(2, x^r){\overline{\sigma}(1)}+\eta(1, x^r){\overline{\sigma}(2)}}
	\end{align}
	is efficient. The policy limits are
	\begin{align}\label{eq: optimal policy limit reg}
	    \gamma^*(1, x)=\frac{\overline{\sigma}(1)}{\overline{\sigma}(1)+\overline{\sigma}(2)}\pi(1, x), \quad
	    \gamma^*(2, x)=\frac{\overline{\sigma}(2)}{\overline{\sigma}(1)+\overline{\sigma}(2)}\pi(2, x),\\
	\end{align}
	and the scaled asymptotic variance of the policy is
	\begin{align}\label{eq: asym variance optimal}
	   nVar(\alpha^*_n)\rightarrow \sigma^{*2}_{reg}= ({\overline{\sigma}}(1)+{\overline{\sigma}}(2))^2.
	\end{align}

\iffalse
	Assume for a single run of $P(1)$, the MLE estimator has the following asymptotic performance:
	\begin{align}
		\hat{r}^{P(1)}_{MLE}\sqrt{t}\rightarrow N\big({r}^{P(1)}, \sigma^2(\hat{r}^{P(1)}_{MLE})\big)
	\end{align}
	and similarly for $P(2)$,
	\begin{align}
	\hat{r}^{P(2)}_{MLE}\sqrt{t}\rightarrow N\big({r}^{P(2)}, \sigma^2(\hat{r}^{P(2)}_{MLE})\big).
	\end{align}
Then the optimal policy in the class of regenerative policies is the one that asymptotically assigns
\begin{align}
p^*=\frac{\sigma(\hat{r}^{P(1)}_{MLE})}{\sigma(\hat{r}^{P(1)}_{MLE})+\sigma(\hat{r}^{P(2)}_{MLE})}
	\end{align}
fraction of the total samples to $P(1)$, or equivalently
\begin{align}
	p'^*=\frac{\eta(2)\sigma(\hat{r}^{P(1)}_{MLE})}{\eta(2)\sigma(\hat{r}^{P(1)}_{MLE})+\eta(1)\sigma(\hat{r}^{P(2)}_{MLE})}.
\end{align}\fi
\end{theorem}

\begin{proof}

Note that the minimum scaled asymptotic variance of stationary regenerative policies with constant $p^r$ is achieved by minimizing the variance in \ref{eq: SAE Asym Var},
\begin{align}
     \arg\min_{q^r\in (0,1)}   \sum_{x\in S} \frac{1}{q^r} \pi(1, x)\sigma^2(1,x)+ \sum_{x\in S} \frac{1}{1-q^r} \pi(2, x)\sigma^2(2,x).
\end{align}
which has a unique solution
\begin{align}\label{eq: optimal q}
    {q^r}^*=\frac{\overline{\sigma}(1)}{\overline{\sigma}(1)+\overline{\sigma}(2)}.
\end{align}
${q^r}^*$ is in $(0,1)$ due to positivity of $\overline{\sigma}(\ell)$s. Also, ${q^r}^*$ from (\ref{eq: p from q}) results in ${p^r}^*$ given in (\ref{eq: optimal p'}), the policy limits in  \eqref{eq: optimal policy limit reg} from \eqref{eq: stationary reg limit},  and the scaled variance in (\ref{eq: asym variance optimal}) from (\ref{eq: SAE Asym Var}).

Next, note that the limit inferior of the scaled asymptotic variance of the SAE under any stationary regenerative policy with almost surely $p^r\in (0,1)$ is bounded below by the optimal value of \eqref{eq: SAE Asym Var}.  This follows by applying Corollary \ref{cor:var_lowerbound reg}.  In particular, from Proposition \ref{prop: stationary reg policy limits}, we know $q^r$ is a probability measure over the set $[0,1]$ which is convex, and so $E\{q^r\}\in [0,1]$.
\end{proof}

\begin{remark}
$\overline{\sigma}^2(\ell)$ is equivalent to the variance of a $x^r$-regenerative cycle under $\ell$. \mr{shall we add a proof here?}
\end{remark}

\begin{remark} Since TAR regenerative policies have only one degree of freedom in setting $p^r$, they have sub-optimal performance compared to TAR Markov policies with $|S|$ degrees of freedom in setting $p(1, x)$ for $x\in S$.  The following proposition shows this fact.\end{remark}
\begin{proposition} TAR regenerative policies are unboundedly inefficient compared to Markov policies under MLE.\mr{inefficiency may be vague here. The complete statement of this proposition would be: The scaled asymptotic variance of the MLE under Markov policies is smaller than that under regenerative policies. Moreover their ratio can be unboundedly large.}

\mr{should we try extending this to SAE? we do not have results for variance of Markov policies under SAE. Although it may not matter since Markovs under SAE are not necessarily consistent in the first place.}
\end{proposition}
\begin{proof} First from  \ref{thm: equiv sae mle}, for every TAR regenerative policy there exists a Markov policy with the same policy limits. Therefore Markov policies have an equal or lower asymptotic variance compared to regenerative policies. Next we provide an example for which the minimum scaled asymptotic variance of MLE for TAR regenerative policies is unboundedly larger than that for Markov policies.

Consider the example in Appendix \ref{sec:example_cooperative} and assume $q(1)=q(2)$. For this example, due to symmetry of the chains, the optimal regenerative policy is to set $p^r=0.5$ with any regenerative state $x^r\in S$. Note that the choice of regenerative state $x^r$ does not impact the asymptotic properties of the SAE, since it does not change the asymptotic properties of the concatenated $P(\ell)$ chains. On the other hand the optimal Markov policy is to set $p(1)=0, p(s)=1$ and $p(1)=0.5$, due to symmetry of the chains plus deterministic outcome and transitions for $x\in S-\{1\}$ (the Markov policy from other states does not matter). Using the same arguments in Section \ref{sec:example_cooperative} shows the variance of optimal regenerative policy scales with $\Theta(s/n)$ while the variance of the optimal Markov policy scales with $\Theta(4/n)$ and does not grow in $s$. Therefore their ratio can be made unboundedly large with increasing $S$.\mr{We can not use our MLE CLT and variance results here for a more exact argument, because most of $\sigma(\ell, x)$s are zero. Hence the example is made more stylized to characterize the shape of optimal policies and their corresponding scaled asymptotic variances}.
\end{proof}

\iffalse
\begin{align}
	\hat{r}^{P(1)}_{MLE}\sqrt{t}\rightarrow N\big({r}^{P(1)}, \sigma^2(\hat{r}^{P(1)}_{MLE})\times \frac{p'\eta(1)+(1-p')\eta(2)}{p'\eta(1)}\big)
\end{align}
and
\begin{align}
	\hat{r}^{P(2)}_{MLE}\sqrt{t}\rightarrow N\big({r}^{P(2)}, \sigma^2(\hat{r}^{P(2)}_{MLE})\times \frac{p'\eta(1)+(1-p')\eta(2)}{(1-p')\eta(2)}\big)
\end{align}
Since, $\hat{r}^{P(1)}_{MLE}$ and  $\hat{r}^{P(2)}_{MLE}$ are independent, we have:
\begin{align}
	\hat{\tau}_{MLE}^{reg}\sqrt{t}\rightarrow N\big(\tau, {\sigma^2(\hat{r}^{P(1)}_{MLE})\times \frac{p'\eta(1)+(1-p')\eta(2)}{p'\eta(1)}+\sigma^2(\hat{r}^{P(2)}_{MLE})\times \frac{p'\eta(1)+(1-p')\eta(2)}{(1-p')\eta(2)}}\big).
\end{align}

An oracle that knows the $\sigma^2(\hat{r}^{P(1)}_{MLE})$ and $\sigma^2(\hat{r}^{P(2)}_{MLE})$ and wants to design the most asymptotically efficient regenerative assignment policy can run an experiment by setting $p' =\frac{\eta(2)\sigma(\hat{r}^{P(1)}_{MLE})}{\eta(2)\sigma(\hat{r}^{P(1)}_{MLE})+\eta(1)\sigma(\hat{r}^{P(2)}_{MLE})}$ and $p=\frac{\sigma(\hat{r}^{P(1)}_{MLE})}{\sigma(\hat{r}^{P(1)}_{MLE})+\sigma(\hat{r}^{P(2)}_{MLE})}$. The asymptotic variance of this experiment will be
\begin{align}
	\label{eq: asymp reg}
	\hat{\tau}_{MLE}^{reg}\sqrt{t}\rightarrow N\big(\tau, \sigma^2(\hat{r}^{P(1)}_{MLE})+\sigma^2(\hat{r}^{P(2)}_{MLE})\big).
\end{align}
\fi

\iffalse
\begin{align}
	\hat{r}^{P(1)}_{MLE}\sqrt{t}\rightarrow N\big({r}^{P(1)}, \sigma^2(\hat{r}^{P(1)}_{MLE})\times \frac{p'\eta(1)+(1-p')\eta(2)}{p'\eta(1)}\big)
\end{align}
and
\begin{align}
	\hat{r}^{P(2)}_{MLE}\sqrt{t}\rightarrow N\big({r}^{P(2)}, \sigma^2(\hat{r}^{P(2)}_{MLE})\times \frac{p'\eta(1)+(1-p')\eta(2)}{(1-p')\eta(2)}\big)
\end{align}
Since, $\hat{r}^{P(1)}_{MLE}$ and  $\hat{r}^{P(2)}_{MLE}$ are independent, we have:
\begin{align}
	\hat{\tau}_{MLE}^{reg}\sqrt{t}\rightarrow N\big(\tau, {\sigma^2(\hat{r}^{P(1)}_{MLE})\times \frac{p'\eta(1)+(1-p')\eta(2)}{p'\eta(1)}+\sigma^2(\hat{r}^{P(2)}_{MLE})\times \frac{p'\eta(1)+(1-p')\eta(2)}{(1-p')\eta(2)}}\big).
\end{align}

An oracle that knows the $\sigma^2(\hat{r}^{P(1)}_{MLE})$ and $\sigma^2(\hat{r}^{P(2)}_{MLE})$ and wants to design the most asymptotically efficient regenerative assignment policy can run an experiment by setting $p' =\frac{\eta(2)\sigma(\hat{r}^{P(1)}_{MLE})}{\eta(2)\sigma(\hat{r}^{P(1)}_{MLE})+\eta(1)\sigma(\hat{r}^{P(2)}_{MLE})}$ and $p=\frac{\sigma(\hat{r}^{P(1)}_{MLE})}{\sigma(\hat{r}^{P(1)}_{MLE})+\sigma(\hat{r}^{P(2)}_{MLE})}$. The asymptotic variance of this experiment will be
\begin{align}
	\label{eq: asymp reg}
	\hat{\tau}_{MLE}^{reg}\sqrt{t}\rightarrow N\big(\tau, \sigma^2(\hat{r}^{P(1)}_{MLE})+\sigma^2(\hat{r}^{P(2)}_{MLE})\big).
\end{align}
\fi

\iffalse

Now we show in general the performance of the regenerative policies can be unboundely worse than Markov policies. We first show in Example \ref{ex: non-optimality of reg} that regenerative policies are not optimal. Next, in Theorem \ref{thm: unboundedly sub-optimal regenerative policy} we show regenerative policies can be in fact unboundedly sub-optimal via an example.

\textbf{[[Should we keep the example below? It does not add considering the example in the proof of Theorem \ref{thm: unboundedly sub-optimal regenerative policy}. However, it is a nice structure and can provide good intuition! ]]}
[Non-Optimality of the Regenerative Policies]\label{ex: non-optimality of reg}
    Consider a Markov chain with deterministic rewards (no reward uncertainty). Partition state space $S$ into $m$ subsets $S_1, ... ,S_m$ where $m$ is even and each subset $S_i$ has at least two states. We construct transition matrices $P(1)$ and $P(2)$ that are periodic of period $m$. For $x$ in $S_i$, we put $P(1,x,y) = q(1,y)$ for $y$ in $S_{i+1}$ (for $i<m$) and for $y$ in $S_1$ when $i=m$. Similarly, for $x$ in $S_i$, we put $P(2,x,y) = q(2,y)$ for $y$ in $S_{i+1}$ (for $i<p$) and for $y$ in $S_1$ when $i=m$. Furthermore assume for $y\in S_i$ with $i$ even, $q(1,y)=q(2,y)$. We make $P(1)$ and $P(2)$ different, and modify as a function of $i$. Define $B_j=S_{2j-1}\cup S_{2j}$ as block $j$.

	The optimal stationary Markov policy is determined by Theorem \ref{thm: stationary optimality}. In this example, it can be decomposed into $m/2$ smaller ones as follows. The above Markov chains $P(1)$ and $P(2)$ are periodic with periods equal to $m$. Any stationary Markov policy $p=\big(p(x_1), p(x_2), ..., p(x_{|S|})\big)$ induces a Markov chain $V$ with distributions
	\begin{align}
		V(x,y)= p(x) q(1, y)+ (1-p(x))q(2, y)= v(y)
	\end{align}
	Note that for $y\in S_{2i}$, because $P(1, x,y)= P(2, x,y)$, $V(x,y)$ is independent of the stationary Markov policy and
	\begin{align}\label{eq: r equal p and q}
		V(x,y)= P(1, x,y)=P(2, x,y).
	\end{align}
	The stationary distributions are then
	\begin{align}
		\pi^v(x)= \frac{1}{m}\frac{v(x)}{\sum_{y\in S_{i}}v(y)}, \qquad x\in S_i.
	\end{align}

	As a consequence of Equations (\ref{eq: r equal p and q}), the stationary distribution for the states $x\in S_{2i+1}$ induced by $V$ is independent of the stationary Markov policy. As a consequence, the stationary distribution of each block is shielded from the policy selected in the other blocks. Therefore, the stationary distribution equations can be decomposed into $m/2$ independent set of distributions such that the stationary distribution of the states in each block is a function of the stationary Markov policy in that same block and independent of the stationary Markov policy in other blocks. This implies that $\kappa(x,i)$ is only a function of $p(x)$, $x\in B_i$. Hence the optimal policy problem can be decomposed into $m/2$ smaller optimization. Furthermore, the special structure of $P(1)$ and $P(2)$, allows for simpler representation of the objective function. The solution of the Poission equation is the same for all $x\in S_i$ as follows:
	\begin{align}
		g(x)= r(x)-\sum_{y\in S_i} r(y)p(y),
	\end{align}
	Therefore, the $P(1)$-variance and $P(2)$-variance of state $x$ are:
	\begin{align}
		\sigma^2(1,x)&= \sum_{y} P(1, x,y)[\tilde{g}(1, y)-(P\tilde{g})(1, x)]^2\\
		&=\sum_{y\in S_{i+1}} q(1,y) [r(y)- \sum_{y\in S_{i+1}} q(1,y)r(y)]^2\\
		\sigma^2(2,x)&= \sum_{y} P(2, x,y)[\tilde{g}(2, y)-(P\tilde{g})(2, x)]^2\\
		&=\sum_{y\in S_{i+1}} q(2,y) [r(y)- \sum_{y\in S_{i+1}} q(2,y)r(y)]^2.
	\end{align}
	The variances are constant over $x$ in $S_i$ which is just the $P(1)$-variance (respectively $P(2)$-variance) of the rewards over $S_{i+1}$. We denote them by $\sigma^2(1, S_i)$ (respectively $\sigma^2(2 ,S_i)$). This simplifies the equations for optimal policy in this especial case. Consequently, the problem of the optimal policy can be decomposed into $m/2$ problems as follows:
	\begin{align}
		\min_{p(x) , x\in B_j} &	\sum_{x\in S_{2j-1}}\bigg[ \frac{\pi^2(1,x)}{p(x)\pi^v(x)}\sigma_0^2(S_{2j-1})+ \frac{\pi^2(2,x)}{\big(1-p(x)\big)\pi^v(x)} \sigma^2(1,S_{2j-1}) \bigg]\nonumber\\
		&+\sum_{x\in S_{2j}}\bigg[ \frac{\pi^2(1,x)}{p(x)\pi^v(x)}\sigma_0^2(S_{2j})+ \frac{\pi^2(2,x)}{\big(1-p(x)\big)\pi^v(x)x} \sigma^2(1,S_{2j}) \bigg]\label{eq: optimal policy markov decomposed}\\
		s.t.\qquad	& v(y)= p(y)q(1,y)+\big(1-p(y)\big) q(2,y)\\
		&\pi^v(x)= \frac{v(x)}{\sum_{y\in S_{i}}v(y)}, \qquad x\in B_{i}.
	\end{align}
	In general by fixing one block and changing the distribution of $P(1)$ and $P(2)$ in the other blocks, the optimal policy in the fixed block does not change and hence ratio of $P(1)$ sampling to $P(2)$ sampling remains fixed; this is while the optimal regenerative policy for the entire chain can change and induce a different ratio of $P(1)$ to $P(2)$ sampling in all states. Combining this with the unique optimal sampling ratio means the regenerative policy is not optimal. Finally note that non-periodic cases can be made where the regenerative policy is not optimal by perturbing slightly the matrices $P(1)$ and $P(2)$ and the results will still hold due to continuity of the analysis. \hfill$\square$

	The bound between the Markov policies and regenerative policies can be arbitrarily large since the Markov policy allow for using one chain to explore the other but regenerative polices do not. We show this by an example below.

	\begin{theorem}[Arbitrary Large Gap between Regenerative and Markov Policies]\label{thm: unboundedly sub-optimal regenerative policy}
	The asymptotic variance of the optimal regenerative policy divided by the variance of the optimal stationary Markov policy can be arbitrary large.
	\end{theorem}
	\textbf{PROOF} Consider a periodic Markov chain with states partitioned into $\{x_1\}, \{x_2\}, \{x_3\}, \{x_4\}$ and $S_1$ where $S_1$ consists of multiple states. we construct two parallel paths. State $x_0$ has transitions to either $x_2$ or $x_3$. On first path, $x_2$ transits to $x_4$ and $x_4$ transits to $x_1$. On the second path, $x_3$ transits to states in $S_1$ and all states in $S_1$ transit to $x_1$. The transition distributions of $P(1)$ and $P(2)$ differ in their transition probability from $x_1$ to $x_2$ and to $x_3$ such that $P(1)$ allocates $.5$ to each, while $P(2)$ allocates $\epsilon$ to $x_3$ and $1-\epsilon$ to $x_2$. Assume all states $x\not\in S_1$ have a reward equal to zero but states in $S_1$ can have arbitrary constant rewards (no reward uncertainty). In this example, $\pi(1,x_2)=\frac{1}{6}$ and $\pi(2,x_2)=\frac{\epsilon}{3}$. Also $\sigma^2(\ell, x)=0, \quad \forall x\neq x_2, \ell \in \{1,2\}$. We set the number of states in $S_1$, their rewards, and transition distributions $P(1)$ and $P(2)$ from $x_2$ to $S_1$ such that the $P(1)$-variance of $x_3$ is $6$ while the $P(2)$-variance of $x_3$ is $(1/\epsilon)^2$. Then,
    \begin{align}
        \sigma^2(1,x_2)&=\frac{1}{6}\times 6=1,\\
        \sigma^2(2,x_2)&=\frac{\epsilon}{3}\times \frac{1}{\epsilon^2}=\frac{1}{3\epsilon},
    \end{align}
	and the optimal regenerative policy from Theorem \ref{thm: optimal reg policy} achieves an asymptotic variance of
	\begin{align}\label{eq: reg example 2}
	    \sigma^{2}_{reg}= (1+\frac{1}{\epsilon}\times \frac{1}{\sqrt{3}})^2.
	\end{align}
    Now consider the (non-optimal) stationary Markov policy with $p(x_1)=1$, i.e. always runs $P(1)$ in $x_1$, and also $p(x_3)=0.5$. It achieves,
    \begin{align}
        \kappa(1, x_3)=\frac{1}{12}\\
        \kappa(2, x_3)=\frac{1}{12}.
    \end{align}
    Then, the corresponding asymptotic variance from Theorem \ref{thm: asymptotic var} is
    \begin{align}\label{eq: Markov example 2}
        \sigma^2_{Markov}= \frac{(\frac{1}{6})^2\times 6}{1/12}+\frac{(\frac{\epsilon}{3})^2\frac{1}{\epsilon^2}}{1/12}= 3.3
    \end{align}
	Moving $\epsilon$ toward zero, the fraction of Eq. (\ref{eq: reg example 2}) to Eq.  (\ref{eq: Markov example 2}) becomes arbitrarily large. Note that in this case $P(1)$ is used for better exploring $P(2)$.

\fi

	\iffalse
	\begin{theorem}[Gap Between Regenerative and Markov Policies 2]
    The fraction of Variance of the optimal regenerative policy to the variance of the optimal stationary Markov policy is tightly bounded from above by one. Moreover any tight bound from below is less than or equal to
    \begin{align}
     & \lim_{m\rightarrow \infty}  \min_{x_i, y_i, i=1,2,...,m } \frac{\sum_{i=1}^{m} (x_i+y_i)^2}{\bigg(\sqrt{\sum_{1,2,...,m}x_i^2}+\sqrt{\sum_{i=1}^{m}y_i^2} \bigg)^2}\\
     & s.t. \quad x_i\ge 0, y_i\ge 0
    \end{align}
	\end{theorem}
	\textbf{PROOF} Since the regenerative policies are a subset of the Markov policies, the fraction of their optimal variances are bounded by one from above. To see the bound is tight by considering the trivial case where $P=Q$ and hence the regenerative policy is optimal.

	We construct an example that achieves the suggested lower bound. We now show that the gap between the optimal regenerative policy and the optimal stationary Markov policy can be arbitrary large by extending our example. To do so, we also introduce locally regenerative policies which is a superset of regenerative policies but a subset of Markov polices. Then we show the gap between optimal locally regenerative policy and the optimal regenerative policy can be arbitrarily large. The arbitrarily large gap between optimal regenerative and optimal Markov policies is then a direct consequence.

	Consider the case where all the even subsets have the same number of states and all the odds have the same. Assume there exists an ordering of states in each subset that for the $k$th state of each two even subsets $2j$ and $2l$, on top of $p(x_{2j}^k)=q(x_{2j}^k)$, but also $p(x_{2j}^k)= p(x_{2l}^k)$. This assumption results that concatenating all the samples from block $j$ is statistically equivalent to a Markov chain with $|B_j|$ states and probability of transition from $P_j(x,y)=P(X,y)$, $Q_j(x,y)=Q_(x,y)$.

	Also for the $k$th state of each two odd subsets $2j-1$ and $2l-1$, the rewards are the same, $r(x_{2j-1}^k)=r(x_{2k-1}^r)$. As a result of this assumptions,
    \begin{align}\label{eq: same even sigma}
        \sigma_0^2(S_{2j})=\sigma_0^2(S_{2k})=A^2\\
        \sigma^2(1,S_{2j})=\sigma^2(1,S_{2k})=B^2
    \end{align}
    which indicates the variance of each block is equivalent to $m$ times the variance of the MLE estimator of the stationary reward for our hypothetical Markov chain (with $|B_j|$ states and probability of transition from $P_j(x,y)=P(X,y)$, $Q_j(x,y)=Q_(x,y)$).

	Now define a locally regenerative policy as a policy that each clock has its own regeneration clock. Formally, the policy assigns to each block $j=1, 2, ..., m/2$ a probability $p'(j)$ and a regenerative state $x_j\in S_{2j-1}$. Every time the Markov chain returns to block $j$, if it hits state $x_j$ then the policy switches from $P(1)$ to $P(2)$ sampling with probability $p'(j)$ for the duration that the Markov chain is still in block $j$, but any other state in $S_j\backslash x_j$ are hit then the chains continues as per the last sampling decision in block $j$. Clearly, a simple case where $p'(j)=0$ for all $j\neq 1$, defines a (globally) regenerative policy. Define
	\begin{align}
	    &\sigma_0(j)=\sum_{x\in S_{2j-1}} \pi_0(x)\sigma_0^2(S_{2j-1})+\sum_{x\in S_{2j}} \pi_0(x)\sigma_0^2(S_{2j})\\
	    &\sigma_1(j)=\sum_{x\in S_{2j}}
	    \pi(1, x) \sigma^2(1,S_{2j-1})+\sum_{x\in S_{2j}}
	    \pi(1, x) \sigma^2(1,S_{2j})
	\end{align}
	Then optimal regenerative policy have an asymptotic variance of
	\begin{align}\label{eq: optimal reg example}
	  \bigg(\sqrt{\sum_{j=1,2,..., m/2} \sigma_0^2(j)}+\sqrt{\sum_{j=1,2,..., m/2} \sigma^2(1,j)}\bigg)^2.
	\end{align}
	with the asymptotic fraction of $P(1)$ samples equal to
	\begin{align}
	    p=\frac{\sqrt{\sum_{j=1,2,..., m/2} \sigma_0^2(j)}}{\bigg(\sqrt{\sum_{j=1,2,..., m/2} \sigma_0^2(j)}+\sqrt{\sum_{j=1,2,..., m/2} \sigma^2(1,j)}\bigg)}.
	\end{align}
	Considering Eq. (\ref{eq: same even sigma}), the optimal variance is
	\begin{align}
	 p=\frac{\sqrt{A^2\times m/2+\sum_{j \text{ odd}} \sigma_0^2(j)}}{\bigg(\sqrt{A^2\times m/2+\sum_{j \text{ odd}} \sigma_0^2(j)}+\sqrt{B^2\times m/2+\sum_{j \text{ even}} \sigma^2(1,j)}\bigg)}.
	\end{align}

	While the optimal locally regenerative policy for each block $j$ can be calculated using the variance of the optimal (globally) regenerative policy for the corresponding hypothetical chain:
	\begin{align}
	    \big(\sigma_0(j)+\sigma_1(j)\big)^2.
	\end{align}
	which is achieved with the asymptotic fraction of $P(1)$ samples in the block $j$ equal to
	\begin{align}
	    p(j)=\frac{\sigma_0(j)}{\sigma_0(j)+\sigma_1(j)}.
	\end{align}
	And due to the independence of the blocks, the total variance of the optimal locally regenerative policy is:
	\begin{align}\label{eq: optimal locally reg example}
	    \sum_{j=1,2,...,m/2} \big(\sigma_0(j)+\sigma_1(j)\big)^2
	\end{align}
	Considering Eq. (\ref{eq: same even sigma}), the optimal variance is
	\begin{align}
     \frac{m}{2}(A+B)^2+\sum_{j \text{odd}} \big(\sigma_0(j)+\sigma_1(j)\big)^2
    \end{align}
    The fraction of Eq. (\ref{eq: optimal locally reg example}) to (\ref{eq: optimal reg example}) results in the proposed lower bound. We further show that the solution to this problem is less than or equal to $.5$. To construct an example with $.5$, consider the case where we set the parameter such that $A=B=0$ and ${\sigma^2_0(4j-3)}=0$ and $\sigma^2(1,4j-3)= 1$ for all $j$s and $\sigma^2_0(4j-1)=1$ and $\sigma^2(1,4j-1j)=0$ for all $j$s.
\fi
	\iffalse
	In this example, a general randomized stationary Markov policy gives us the ability to independently choose the amount of $P(1)$-sampling versus $P(2)$-sampling when in each $S_i$. On the other hand, a regenerative policy forces a single choice across all states. For such Markov chain we have:
	\begin{align}
		\pi(x)=\frac{1}{|S|} \frac{p(x)}{\sum_{y\in S_i} p(y)}, \quad  \forall x\in S_i.
	\end{align}
	Moreover,
	\begin{align}
		g(x)= r(x)-\sum_{y\in S_i} r(y)p(y),
	\end{align}
	and as a consequence
	\begin{align}
		\sigma^2_0(x)&= \sum_{y} P(x,y)[g(y)-(Pg)(x)]^2\\
		&=\sum_{y\in S_{i+1}} p(y) [r(y)- \sum_{y\in S_{i+1}} p(y)r(y)]^2.
	\end{align}
	and therefore the same for all $x\in S_i$.
	Now consider the following especial case where $|S|=4$ and $m=2$:
	\begin{align}
		P=
		\left[ {\begin{array}{cccc}
				0 & 0 & p3 & p4\\
				0 & 0 & p3 & p4\\
				p1 & p2 & 0 & 0\\
				p1 & p2 & 0 & 0\\
		\end{array} } \right]
	\end{align}
	and
	\begin{align}
		Q=
		\left[ {\begin{array}{cccc}
				0 & 0 & q3 & q4\\
				0 & 0 & q3 & q4\\
				q1 & q2& 0 & 0\\
				q1 & q2 & 0 & 0\\
		\end{array} } \right]
	\end{align}
	\iffalse where
	\begin{align}
		P13=P23, \quad P14=P24\\
		Q13=Q23, \quad Q14=Q24\\
		P31=P41, \quad P32=P42\\
		Q31=Q41, \quad Q32=Q42
	\end{align}\fi
	$P(1)$ and $P(2)$ determine periodic Markov chains with periods equal to the number of states, $4$. Also in this case, Then:
	\begin{align}
		\pi_0{'}= \frac{1}{2}(p1, p2, p3, p4)
	\end{align}
	\begin{align}
		\pi_1{'}= \frac{1}{2}(q1, q2, q3, q4)
	\end{align}

	\begin{align}
		\sigma_0^2(x1)&=\sigma_0^2(x2)= p3(r3-p3r3-p4r4)^2+p4(r4-p3r3-p4r4)^2\\
		&= p3p4(r3+r4)^2=  \sigma_0^2(S_1)\\
		\sigma_0^2(x3)&=\sigma_0^2(x4)= p1(r1-p1r1-p2r2)^2+p2(r2-p1r1-p2r2)^2\\
		&= p1p2(r1+r2)^2= \sigma_0^2(S_2)
	\end{align}
	Consider the stationary Markov policy with $\psi_0=[\alpha(2), \alpha_2, \alpha_3, \alpha_4]$, then it implies the Markov chain:
	\begin{align}
		R=
		\left[ {\begin{array}{cccc}
				0 & 0 & \alpha(2) p3+(1-\alpha(2)) q3 & \alpha(2) p4+ (1-\alpha(2)) q4\\
				0 & 0 &  \alpha_2p3+(1-\alpha_2)q3 & \alpha_2p4+(1-\alpha_2)q4\\
				\alpha_3 p1+(1-\alpha_3)q1 & \alpha_3p2+(1-\alpha_3)q2& 0 & 0\\
				\alpha_4 p1+(1-\alpha_4)q1 & \alpha_4p2+(1-\alpha_4)q2 & 0 & 0\\
		\end{array} } \right]
	\end{align}
	and considering the fact that $\pi^R_1+\pi^R_2=\pi^R_3+\pi^R_4=0.5$ we have
	\begin{align}
		(.5-\pi^R_3)R_{41}+\pi^R_3R_{31}=\pi^R_1\\
		\pi^R_1R_{13}+(0.5-\pi^R_1)R_{23}=\pi^R_3\\
		\pi^R_1+\pi^R_2=\pi^R_3+\pi^R_4=0.5
	\end{align}
	Therefore,
	\begin{align}
		\pi^R_1&=\frac{.5 R_{41}+0.5R_{23}(\alpha_3-\alpha_4)(p2-q2)}{1-(\alpha_3-\alpha_4)(p1-q1)(\alpha(2)-\alpha_2)(p3-q3)}	=\\
		&=\frac{0.5\alpha_4p1+.5(1-\alpha_4)q1+.5(\alpha_2p3+(1-\alpha_2)q3)(\alpha_3-\alpha_4)(p_2-q_2)}{1-(\alpha_3-\alpha_4)(p1-q1)(\alpha(2)-\alpha_2)(p3-q3)}
	\end{align}
	Finally the optimal stationary Markov policy is a solution to the following:
	\begin{align}
		\min_{\alpha} &	\bigg[ \frac{p1^2}{\alpha(2)\pi^R_1}+\frac{p2^2}{\alpha_2\pi^R_2}\bigg] \sigma_0^2(S_1)+ \bigg[ \frac{p3^2}{\alpha_3\pi^R_3}+\frac{p4^2}{\alpha_4\pi^R_4}\bigg] \sigma_0^2(S_2)+\\
		&\bigg[ \frac{q1^2}{(1-\alpha(2))\pi^R_1}+\frac{q2^2}{(1-\alpha_2)\pi^R_2}\bigg] \sigma^2(1,S_1)+ \bigg[ \frac{q3^2}{(1-\alpha_3\pi^R_3)}+\frac{q4^2}{(1-\alpha_4)\pi^R_4}\bigg] \sigma^2(1,S_2)\\
		&s.t.\qquad	 0\leq \alpha_i\leq 1,\qquad i=1,2,3,4
	\end{align}
	The solution to the above problem is not necessarily
	\begin{align}
		\alpha(2)=\alpha_2=\frac{\sigma_0(S_2)}{\sigma_0(S_2)+\sigma_1(S_2)}\\
		\alpha_3=\alpha_4=\frac{\sigma_0(S_1)}{\sigma_0(S_1)+\sigma_1(S_1)}
	\end{align}
	This would be optimal policy in case the estimator was built conditioned on the knowledge that $P(x, y)=p(y) \forall x\in S_i$ and $Q(x,y)=q(y), \forall x\in S_i$.

	The question is if the solution to the above is regenerative i.e if it is
	\begin{align}
		\alpha_i=\frac{\sqrt{(p2+p1)p3p4+(p3+p4)p1p2}}{\sqrt{(p2+p1)p3p4+(p3+p4)p1p2}+\sqrt{(q2+q1)q3q4+(q3+q4)q1q2}} \quad \forall i=1,2,3,4
	\end{align}
	\fi

\iffalse

\begin{theorem}[Conditions for Optimality of Regenerative Policies] \label{thm: optimality of reg} Regenerative policies are optimal under SAE, in the space of TAR SAE-consistent policies if and only if the solution of
\begin{align}\label{eq: kappa optimal}
    \kappa^* \in \arg\min_{\kappa\in \mathcal{K}} \sum_{\ell=1}^{2}\sum_{x\in S} \frac{\pi^2(\ell,x)\sigma^2(\ell,x)}{\kappa(\ell,x)}
\end{align}
where $K$ is determined by the following
\begin{align}
    \kappa(1,y)+\kappa(2,y)&=\sum_{\ell=1}^{2}\sum_{x\in S} \kappa(\ell,x)P(\ell,x,y), \quad y\in S\label{eq: kappa eq 1}\\
    \sum_{\ell=1}^{2}\sum_{x\in S}\kappa(\ell,x)&=1\label{eq: kappa eq 2}\\
    \kappa(\ell,x)&\ge 0, \quad x\in S, \ell=1,2.\label{eq: kappa eq 3}
\end{align}
takes the form
	\begin{align}
		\kappa^*(1,x)&=p \pi(1, x)\label{eq: reg cond 1}\\
		\kappa^*(2,x)&= (1-p) \pi(2, x)\label{eq: reg cond 2}
	\end{align}
	for some $0\leq p\leq 1$.
\end{theorem}

\textbf{PROOF}
Remark 3 identifies the space of policy limits of the TAR policies by (\ref{eq: kappa eq 1})-(\ref{eq: kappa eq 3}), and the optimal TAR policy as a solution to (\ref{eq: kappa optimal}).  Considering Equations (\ref{eq: reg kappa 1}) and (\ref{eq: reg kappa 2}), if a regenerative policy is optimal, then Eq. (\ref{eq: reg cond 1}) and (\ref{eq: reg cond 2}) should hold. Vice versa if these equations hold, then the following regenerative policy will achieve the minimum variance. Choose a regenerative state $x$ with expected cycle lengths $\eta(1)$ and $\eta(2)$, and set
\begin{align}
p'= \frac{p\eta(2)}{p\eta(2)+(1-P)\eta(1)}.
\end{align}
\qed
\fi

\iffalse
\section{Geometric Analysis of Stationary Markov Policies and Regenerative Policies}
We characterize the space of the Markov policies. We consider a $2|S|$-dimensional space and show a point in this space by $\kappa= (\kappa(x_0,0), \kappa(x_1,0), ..., \kappa(x_S, 0), \kappa(x_0, 1), \kappa(x_0,1), ..., \kappa(x_S, 1))$. The set of feasible $\kappa$ considering constraints (\ref{eq: const 1})-(\ref{eq: const 3}) is denoted by $K$.

From Theorem \ref{thm: Markov optimality}, the space of the feasible policies can be described in two different ways where there exists a mapping between them. First it can be characterized with the set of vectors $\kappa$ denoted by $K$. $K$ is determine by the following constraints:
\begin{align}\label{eq: K 1}
& \kappa(y,0)+\kappa(y,1)= \sum_{x\in S} \kappa(x, 0)P(x,y)+\sum_{x\in S} \kappa(x,2)Q(x,y) \qquad \forall y\in S\\
& \sum_{x\in S, i\in \{0,1\}} \kappa(x,i)=1  \\
& \kappa(x,i)\ge 0, \quad x\in S, i\in \{0,1\} .\label{eq: K 3}
\end{align}
And second, it can be characterized with the set $\psi_0$s where $\psi_0=(\psi_0(x):x\in S)$ denoted $\Psi_0$. $\Psi_0$ is determine by the following constraints:
\begin{align}
0 \le \psi_0(x) \le 1 \qquad \forall x\in S.
\end{align}
Note that $\Psi_0$ is defined in an $|S|$-dimensional space. $\Psi_0$ is a hypercube with $2^{|S|}$ vertices at points where $\psi_0(x)\in \{0,1\}, \forall x\in S$.  On the other hand, $K$ is $|S|$-dimensional polyhedron in a $2|S|$-dimensional space.  In the case where no two rows of $P(1)$ and $P(2)$ are the same, There are at least $2^{|S|}$ extreme points (vertices) of this polyhedron (vertices) which are determined by choosing a subset of the $|S|$ states and set $\kappa(x, 0)=0$ at those states (Note that $\kappa(x,1)=0$ does not imply $\kappa(x,2)=1$). To show this note that every point $\kappa$ such that there exists some $(x,i)$ were $\kappa(x,i)=0$ should be on the surface of the $K$ polyhedron (because of constrains $ \kappa(x,i)\ge 0, \quad x\in S, i\in \{0,1\}$. Moreover, the points described above belong to $K$ (one can easily check the constraints to ensure). Therefore, these points are in fact at the surface of polyhedron. Moreover, these points can not be constructed by convex combination of the other points. Therefore, these points should be the vertices (extreme points) of the polyhedron.  \textbf{COMMENT: Are there any other extreme points for $K$?} Note that since $K$ is convex, any point in $K$ is determined as a convex combination of the extreme points.

\begin{remark}[Transformation Function between $K$ and $\Psi_0$] There is a mapping between any point in $\Psi_0$  and in $K$ in the sense that for every point in one there exists a point in the other that results in the same value for the objective function. A point in $\Psi_0$ corresponds to a point in $K$ through the stationary distribution of Markov chain $R$:
\begin{align}
& R(x,y)= \psi_0(x)P(x,y)+\psi_1(x)Q(x,y)\\
&\pi^R= \pi^R\times R\\
&\sum_x \pi^R(x)=1\\
&\kappa(x,i)= \pi^R(x)\times \psi_i(x), i\in \{0,1\}.
\end{align}
Vice versa, any point in $K$ can corresponds to the following point in $\Psi_0$:
\begin{align}
	\psi_0(x)=\frac{\kappa(x,1)}{\kappa(x,1)+\kappa(x,2)}.
\end{align}
\end{remark}
\begin{remark}
	The transformation between $\Psi_0$ and $K$ is such that a point at surface of $\Psi$ is not on the surface the polyhedron $K$. An example is the regenerative policies shown below.
\end{remark}
\begin{remark} [Space of Regenerative Policies in $\Psi_0$] The curve line representing the space of regenerative policies in $\Psi_0$ is:
\begin{align}
\psi_0(x)= \frac{p\times \pi(1,x)}{p\times \pi(1,x)_+(1-p)\times \pi(2,x)}, \quad \forall x\in S,
\end{align}
where
\begin{align}
p\in [0,1].
\end{align}
This curve line starts from point $\Psi_0=(0,0,...,0)$ (corresponding to $R=P$) and ends at $\Psi_0=(1,1,1,...,1)$ (corresponding to $R=Q$). Other than these two points, the curve is located in the interior of the hypercube because for all $p\in (0,1)$, $\psi_0(x)>0, \forall x\in S$.
\end{remark}
\fi

\iffalse
\begin{claim} The objective function is strictly convex. The set $K$ is also convex and close because it is determined by a set of linear constraints over the space of $\mathbb{R}^{2|S|}$ where none of them is in the form of a strict inequality.

\end{claim}

\begin{claim}[Necessary Condition for Optimality of the Regenerative policies] The set of points $\kappa$ due to regenerative policies, denoted by $K_{reg}$ is a line segment that connects $\kappa^{P(1)}$ corresponding to $P(1)$ and $P(2)$...

	The necessity of this condition follows the following steps:
 \begin{enumerate}
 	\item  Any point $\kappa$ where $\kappa(x,i)=0$ for at least one $x\in S, i\in \{0,1\}$ is a boundary point for the feasible set $A$ (the converse is not true, i.e. there exist boundary points where no $\kappa(x,i)=0$).
 	\item Hence, the two extreme regenerative policies  where $p=0$ or $p=1$, i.e $\kappa(x,1)=0, \forall x$ or $\kappa(x,2)=0, \forall x$, are boundary points for the feasible set $A$. We denote these two extreme points with $\kappa_P$ and $\kappa_Q$.
 	\item These two extreme points are not optimal clearly because the value of the objective function is infinity at these points.
 	\item $A_{reg}$ is a line segment connecting these two extreme points, i.e. $\kappa= \beta \kappa_P +(1-\beta)\kappa_Q, \quad \beta\in [0,1]$.
 	\item  Then, if the optimal $\kappa^*$ lies on the line $A_{reg}$, since $\kappa^*$ is also a boundary point of $A$ due to Claim 4 and since $A$ is convex due to Claim 1, the whole $A_{reg}$ should be a boundary line for $A$.
 \end{enumerate}
\end{claim}

\begin{claim}[Sufficient Condition for Optimality of the Regenerative Policies] Considering Claim 5 to be true, a sufficient condition for optimality of the regenerative policies is that any line segment connecting the relaxed optimal point $\kappa^*_{relaxed}$ to a point in $A$ crosses the boundary line $A_{reg}$.
\end{claim}

\begin{claim}[Optimal Point on the Surface of the Polyhedron] The optimal point is either
\begin{align}
			\kappa^*_{relaxed}(x,i)= \frac{\pi_i(x) \sigma_i(x)}{C} \qquad \forall x\in S, i\in \{0,1\}
	\end{align}
where $C=\sqrt{\overline{\sigma}^2}$ is a constant with $\overline{\sigma}^2$ the Lagrange multiplier for Eq. (\ref{eq: const 2}) or the line segment connecting $\kappa^*$ to $\kappa^*_{relaxed}$ does not have any other intersection with $K$. To see this consider the following steps:
\begin{itemize}
	\item	If we relax the constraint in Eq. (\ref{eq: const 1}), then the feasible set $K$ is all probability distributions over $(x,i), x\in S, i\in \{0,1\}$. In this case, the Lagrangian will be:
	\begin{align}
		L= \sum_{x\in S}\bigg[ \frac{\pi_0^2(x)}{\kappa(x, 0)}\sigma_0^2(x)+ \frac{\pi^2_1(x)}{\kappa(x,2)} \sigma^2(1,x) \bigg]+\overline{\sigma}^2(\sum_{x\in S, i\in \{0,1\}} \kappa(x,i)-1)+\sum_{x,i} \gamma(x,i) \kappa(x,i).
	\end{align}
	The first order condition for optimality is
	\begin{align}
		-\frac{\pi^2_i(x)}{\kappa^2(x,i)} \sigma^2_i(x)+\overline{\sigma}^2=0,
	\end{align}
	which means
	\begin{align}
		\kappa^*_{relaxed}(x,i)= \frac{\pi_i(x) \sigma_i(x)}{\overline{\sigma}^2^{1/2}} \qquad \forall x\in S, i\in \{0,1\}.
	\end{align}
	We refer to these set of points by the relaxed optimal point. Note that this point can not be attained with a regenerative assignment since it does not meet the condition fin Eq. (\ref{eq: reg cond 1}) and Eq. (\ref{eq: reg cond 2}), unless $\sigma_1(x)=\sigma_2(x)$ for all $x\in S$ i.e. $P(1)$ and $P(2)$ are exactly the same.
	\item 	$\kappa^*_{relaxed}$ is not necessarily in $K$. To show this we can construct a two state Markov chain were constraint Eq. (\ref{eq: const 1}) does not hold at $\kappa^{*}_{relaxed}$, i.e.
		\begin{align}
		&\kappa^*(x_0,0)+\kappa^*(x_0, 1)=\pi_0(x_0)\sigma_0(x_0)+\pi_1(x_0)\sigma_1(x_0)=\nonumber\\
		&\frac{P21}{P21+P12}\frac{\sqrt{P11P12}(r1-r2)}{P12+P21}+\frac{Q21}{Q21+Q12}\frac{\sqrt{Q11Q12}(r1-r2)}{Q12+Q21}\neq\nonumber\\
		&\sum_y \kappa(y,0) P(y,x_0)+\kappa(y,1) Q(y, x_0)=\nonumber\\
		&\sum_{y\in S} \pi_0(y)\sigma_0(y)P(x,y)+\pi_1(y)\sigma_1(y)Q(x,y)=\nonumber\\
		&\frac{P21}{P21+P12}\frac{\sqrt{P11P12}(r1-r2)}{P12+P21}\times P11+\frac{P12}{P21+P12}\frac{\sqrt{P22P21}(r1-r2)}{P12+P21}P21+\\
		&\frac{Q21}{Q21+P12}\frac{\sqrt{Q11Q12}(r1-r2)}{Q12+Q21}\times Q11+\frac{Q12}{Q21+Q12}\frac{\sqrt{Q22Q21}(r1-r2)}{Q12+Q21}Q21.
	\end{align}
	\item If $\kappa^*_{relaxed}$ is not in the feasible set, then the line segment between $\kappa^*$ and $\kappa^*_{relaxed}$ should not have any other intersection with $K$ because otherwise the objective function can not be monotonically decreasing in this line segment and this is in contrast to the strict convexity of the objective function.
	\end{itemize}
\end{claim}

\begin{claim}
	As a consequence of Claim 1, Claim 2, and Claim 3, if $\kappa^*_{relaxed}$ is outside of $K$ then the line connecting $\kappa^*_{relaxed}$ to $\kappa^*$ does not have any intersection with $K$ other than $\kappa^*$ (because otherwise the objective function can not be monotonically decreasing in the line segment that connects $\kappa^*$ to $\kappa_{relaxed}^*$ and this is in contrast to the strict convexity of the objective function.)
\end{claim}
\fi

\mr{Edited up to here}

\subsection{An Online Experimental Design: \OnlineETIReg}\label{sec:online reg}
Similar to Section \ref{sec:online}, and for the same reasons, we propose an online experiment with regenerative sampling policy in this section. Based on Theorem \ref{thm: optimal reg policy}, it follows that one efficient regenerative policy is the stationary one obtained by inserting ${p^r}^*$ in (\ref{eq: optimal p'}).  Our online policy (i.e., one that does not use {\em a priori} knowledge of system parameters) that is consistent and efficient in the limit as $n \to \infty$.  In particular, the policy we construct will be TAR with policy limits ${q^r}^*\pi(1, x)$ and $(1-{q^r}^*)\pi(2,x)$ obtained from \eqref{eq: q from p} correspondingly.  Our proposed policy, called \OnlineETIReg (for {\em Online Experimentation with Temporal Interference two}) works as follows.

At every time visit to state $x^r$ \OnlineETIReg updates an estimator of $\overline{\eta}(\ell, x^r)$ and using them to form estimates of $\overline{\sigma}(\ell)$s, all based on \eqref{eq: reg rev 2}.  Initially, the policy sets $p^r_0=0.5$ and therefore in every regenerative state samples chain $\ell$ with probability $0.5$. This continues until there are at least one cycle from each $P(\ell)$, $\ell=1,2$ and furthermore, the estimates for  $\overline{\sigma}(\ell)$s are positive for both $\ell=1,2$. From that point, using these estimates, \OnlineETIReg computes $\hat{p}_n$ according to \eqref{eq: optimal p'}.  At each time step $n$, \OnlineETIReg then samples from chain $\ell$ with the following probability:
\begin{equation}
\label{eq:p_n(ell,x)}
  \hat{p}_n(\ell,x) = (1-m_n^{-1/2})\hat{p}^r_n +\frac{1}{2}m_n^{-1/2},
\end{equation}
where $m_n$ is the cumulative number of $x^r$-cycles up to time $n$. The additional $\frac{1}{2} m_n^{-1/2}$ is the forced exploration: it ensures sufficient exploration of both chains to give consistent estimates of $\overline{\sigma}(\ell)$ and therefore ${p^r}^*$ without influencing the policy limits, and thus the asymptotic variance, of the policy. The full pseudocode of $\OnlineETIReg$ is in Algorithm \ref{alg: reg}.

\begin{algorithm}[ht]
\caption{\OnlineETIReg (Online Experimentation with Temporal Interference Two)}\label{alg: reg}
\begin{algorithmic}[1]

\Procedure{Experiment}{initial state $x_0$}
\State Set initial state $X_0 = x^r$
\State Initialization: Set $m=0$, for $\ell = 1,2$, set ${\hat{\alpha}}_0(\ell,x^r)=0$, $C_0(\ell,x^r)=0$;
\For{$n = 1, 2, \ldots$}
\If{ $x_{n-1}=x^r$}
\State Set $m\gets m+1$
\If {$C_{m-1}(\ell, x^r)>0$ for $\ell=1,2$}
\State Set $\hat{\alpha}_{n-1}(\ell)= \frac{\sum_{j=1}^{C_{m-1}(\ell, x^r)} Y_j(\ell, x^r)}{\sum_{j=1}^{C_{m-1}(\ell, x^r)}\eta_{j}(\ell, x^r)}$
\State Set $\hat{\eta}_{n-1}(\ell, x^r)=\frac{\sum_{j=1}^{C_{m-1}(\ell, x^r)} \eta_{j}(\ell, x^r)}{C_{m-1}(\ell,x^r)}$
\State Set $\hat{\overline{\sigma}}_{n-1}(\ell)=\big( \frac{\sum_{j=1}^{C_{m-1}(\ell, x^r)} \big(Y_j(\ell, x^r)-\hat{\alpha}_{n-1}(\ell)\eta_j(\ell, x^r)\big)^2}{\sum_{j=1}^{C_{m-1}(\ell, x^r)}\eta_{j}(\ell, x^r)})^{1/2}$
\If {$\hat{\overline{\sigma}}(\ell)>0$ for $\ell=1,2$}
\State Set $\hat{p}_{n-1}= (1-m^{-1/2})\frac{\hat{\eta}_{n-1}(2, x_r)\hat{\overline{\sigma}}_{n-1}(1)}{\hat{\eta}_{n-1}(2, x^r){\hat{\overline{\sigma}}_{n-1}(1)}+\frac{1}{2}\hat{\eta}_{n-1}(1, x^r){\hat{\overline{\sigma}}_{n-1}(2)}}+m^{-1/2}$
\Else
\State $\hat{p}_{n-1}=0.5$
\EndIf
\Else
\State Set $\hat{p}_{n-1}=0.5$, $\hat{\alpha}_{n-1}=0$
\EndIf
\State Set $A_{n-1} = \ell$ with probability $\hat{p}^r_{n-1}$, i.e.:
\State \indent $A_{n-1} = 1$ if $U_{n-1} \leq \hat{p}_{n-1}^r$, and  otherwise $A_{n-1} = 2$
\State $C_m(\ell, x^r)\gets C_m(\ell, x^r)+I(A_{n-1}=\ell)$
\Else \State Set $A_{n-1} = A_{n-2}$
\State $\hat{\alpha}_{n-1}(\ell)=\hat{\alpha}_{n-2}(\ell)$
\EndIf
\State Run chain $A_{n-1}$, and obtain reward $R_n$ and new state $X_n$

\State For all $\ell = 1,2$, $x,y \in S$:
\State \indent $Y_{C_m(\ell, x^r)}\gets Y_{C_m(\ell, x^r)}+I(A_{n-1}=\ell)R_n$
\State \indent $\eta_{C_m(\ell, x^r)}\gets \eta_{C_m(\ell, x^r)}+I(A_{n-1}=\ell)$
\State Set $\hat{\alpha}_n=\hat{\alpha}_n(2)-\hat{\alpha}_n(1)$
\EndFor

\EndProcedure
\end{algorithmic}
\end{algorithm}

We have the following theorem.
\begin{theorem}\label{thm: alg efficiency} Suppose that for both $\ell=1,2$, there holds $\overline{\sigma}(\ell) > 0$. Then \OnlineETIReg is a TAR policy with policy limits $\kappa^*$ (as defined in Theorem  \ref{thm: optimal reg policy}), and thus it is consistent and efficient. \mr{under MLE yes, under SAE we do not know unless we extend the variance results to non-stationary SAE}
\end{theorem}

\begin{theorem} The proposed experiment achieves the same asymptotic variance of the optimal regenerative algorithm.
\end{theorem}
\textbf{Proof} First note that since the Markov chains are irreducible with finite states, the regenerative cycles are finite with probability one. Therefore, the number of cycles by time $n$ denoted by $m(n)$ satisfies
\begin{align}\label{eq: infinite cycles}
    m(n)\xrightarrow{a.s.} \infty
\end{align}
as $n\rigthtarrow \infty$.
On the other hand, for  regenerative cycle $m$, $m^{-1/2}<\hat{p}^r_n<1-m^{-1/2}$. Since $\sum_{m=1}^{\infty} m^{1/2} \to \infty$ almost surely, there are infinite cycles of each chain \begin{align}\label{eq: Cm infinitity}
    C_m(\ell, x^r)\xrightarrow{a.s.}\infty
\end{align}
for $\ell=1,2$ as $m$ goes to infinity, due to the forced exploration term, and the Borel-Cantelli Lemma. Consequently, from law of large numbers,
\begin{align}
     \frac{1}{k}\sum_{j=1}^{k} Y_j(\ell, x^r)&\xrightarrow{a.s.}E\{Y_1{\ell, x^r}\}\\
     \frac{1}{k}\sum_{j=1}^{k}\eta_j(\ell, x^r)&\xrightarrow{a.s.} \eta(\ell, x^r)
\end{align}
as $k$ goes to infinity. Then from \eqref{eq: Cm infinitity} and Theorem \ref{prop: iid}
\begin{align}
    \frac{\sum_{j=1}^{C_m(\ell)} Y_j(\ell, x^r)}{\sum_{j=1}^{C_m(\ell)}\eta_j(\ell, x^r)}\xrightarrow{a.s.} E_{\pi(\ell)}\{r(\ell, x)\}=\alpha(\ell)
\end{align}
as $k$ goes to infinity. Consequently, the estimator $\hat{\alpha}_n$ is consistent. In the same way we show
\begin{align}
    \hat{\overline{\sigma}}_{n-1}(\ell)=\big( \frac{\sum_{j=1}^{C_{m-1}(\ell, x^r)} \big(Y_j(\ell, x^r)-\hat{\alpha}_{n-1}(\ell)\eta_j(\ell, x^r)\big)^2}{\sum_{j=1}^{C_{m-1}(\ell, x^r)}\eta_{j}(\ell, x^r)})^{1/2}\xrightarrow{a.s.} \overline{\sigma}(\ell)
\end{align}
as $n$ goes to infinity \mr{this part needs some work. we should show $\overline{\sigma}(\ell)$ is equal the variance of a $P(\ell)$ cycle divided by the length of the cycle, and then show the variance of a $P(\ell)$ is consistently estimated with the empirical variance fraction. Using that and the consistency of $\hat{eta}_n(\ell, x^r)$ established earlier gives the result}. From \eqref{} and \eqref{},
\begin{align}
    \hat{p}^r_n \xrightarrow{a.s.} p^r_n.
\end{align}

(\textbf{We should also show the variance of $C_m(1, x^r)/m$ goes to zero}).
and therefore,
\begin{align}
    p_n\rightarrow p.
\end{align}
Consequently, from (\ref{eq: assignment policy 1}), (\ref{eq: assignment policy 1}), and (\ref{eq: epsilon n reg}), the share of the samples from $P(1)$ converges to $p$.

\iffalse
\begin{algorithm}[H]
\caption{Experiment with Time Interference}\label{alg: reg cycle}
\begin{algorithmic}[1]
\Procedure{Experiment}{}
\State $\textit{T} : \text{total number of samples}$
\State $k= 0, \hat{p}=0, l_1=0, l_2=0, n_1=0, n_2=0$
\State $\text{Fix a state } x\in X$
\State \textbf{while} $t\leq T$
\If {$n_1-\hat{p}t \le n_2-(1-\hat{p})t$ or both $\hat{P}=0$ and $q\leq t^{-1/3}$}
\State $\text{Run a x-cycle under P}$
\State $l_1 \gets l_1+1$
\State $A_{l_1}\gets \text{total reward accumulated over the z-cycle}$
\State $\eta_{l_1}\gets \text{size of the cycle}$
\State $n_1 \gets n_1+\eta_{l_1}$
\State $k \gets k+\eta_{l_1}$
\State $\textbf{else}$
\State $\text{Run a x-cycle under Q}$
\State $l_2 \gets l_2+1$
\State $V_{l_2}\gets \text{total reward accumulated over z-cycle}$
\State $\beta_{l_2}\gets \text{size of the cycle}$
\State $n_2 \gets n_2+\beta_{l_2}$
\State $k \gets k+\beta_{l_2}$
\EndIf
\State $\text{form the estimators } \hat{r}^{P(1)}= \frac{\sum_{i=1}^{l_1} A_i}{\sum_{i=1}^{l_1}\eta_{i}}  \text{  and  }\hat{r}^{P(2)}= \frac{\sum_{i=1}^{l_2} V_i}{\sum_{i=1}^{l_2}\beta_{i}}$
\State $\text{form the estimators } \hat{\sigma}^{P^2}= \frac{\sum_{i=1}^{l_1} (A_i-\hat{r}^{P(1)}\eta_i)^2}{\sum_{i=1}^{l_1}\eta_{i}}  \text{  and  }\hat{\sigma}^{Q^2}= \frac{\sum_{i=1}^{l_2} (V_i-\hat{r}^{P(2)}\beta_i)^2}{\sum_{i=1}^{l_2}\beta_{i}}$
\State $\text{set  } \hat{p}=\frac{\hat{\sigma}^{P}}{\hat{\sigma}^{P}+\hat{\sigma}^{Q}}$
\State $\textbf{end while loop}$
\State $\text{return  } \hat{\tau}^*=\hat{r}^{P(1)}-\hat{r}^{P(2)}$
\EndProcedure
\end{algorithmic}
\end{algorithm}
\fi

config: arxiv


TITLE: Prove that a subgraph of a de Bruijn graph is still connected
QUESTION [1 upvotes]: I'm trying to prove the following: consider the de Bruijn graph $$ G(2,n) $$
I'm trying to prove that for $$ n \geq 4 $$  if I remove the vertices $$ v_1 = 00..0, v_2 = 11..1 $$ and all the edges that touch them, the new graph that is left is still connected.
can someone please help me out with a formal proof? I understand why it's true, because I remove the vertices "from the side" which does not touch any inner vertices (and this inner group of vertices is connected).
I tried to show it by creating new abc where each of the vertices that is left after the elimination of $$ v_1,v_2 $$ together with the adequate edges in the old graph will be copied to a new one in accordance to it's place in the abc. basically I'm trying to "shift" the abc backwards and create new de Bruijn graph $$ G(2,n-2) $$ but I'm not sure if it's correct or how to write that formally.
Thank you very much for your help!

REPLY [1 votes]: I don't 100% understand your plan, but I suspect you're overthinking it.
Let's let $G'$ be the graph $G(2,n)$ with the two vertices removed.  Let $u,v$ be two arbitrary vertices in $G'$.  Note that $u$ and $v$ are two binary strings of the length $n$ by the construction of the De Bruijn graph.
Also keep in mind that there is a natural correspondence between a $(u,v)$-path in $G(2,n)$ and a binary string whose first $n$ characters are $u$ and whose last $n$ characters are $v$.  So all we need to do to show that $G'$ is strongly diconnected is to show that there is a binary string that starts with $u$, ends with $v$, and does not contain $n$ or more consecutive common bits.
To that end, let $x$ be the binary string of shortest length whose first $n$ characters are $u$ and whose last $n$ characters are $v$.  ($uv$ itself is such a string, so there must be a shortest one by the well-ordering of the natural numbers.) Could $x$ contain $n$ consecutive digits?  No.  The digits could not be at the beginning or end of the string, since $u$ and $v$ were vertices in $G'$ and $000...0$ and $111...1$ were removed.  And if the consecutive digits were in the middle, you could remove one of the extra digits and have a shorter string satisfying the conditions, contrary to the choice of $x$ as the shortest such string.  Therefore, $x$ corresponds to a $(u,v)$-path that exists completely in $G'$.  Since $u$ and $v$ were arbitrary vertices, $G'$ is strongly diconnected.


TITLE: Proving $\text{rank}(A+B) \leq \text{rank}(A) + \text{rank}(B) - \text{rank}(AB)$ when $A,B$ commute
QUESTION [7 upvotes]: Let $A,B$ be $n \times n$ matrices and $AB=BA$. Show that $$\text{rank}(A+B) \leq \text{rank}(A) + \text{rank}(B) - \text{rank}(AB)$$

Attempt at the solution:
I first proved that $$R(A+B) \subseteq R(A) + R(B)$$ where R(A) is Range(A).
Then I used the dimension formula that states that $$\dim(U+V) = \dim(U) + \dim(V) - \dim(U \cap V)$$ so that I get $$r(A+B) \leq r(A) +r(B) - \dim(R(A)\cap R(B))$$
The last part would be to show that $$\dim(R(A)\cap R(B)) = \dim(R(AB))$$ using the fact that $AB=BA$.
I need help with this last part. Also please critique me if the above solution is acceptable or if there is something wrong with it.
Thank you!!

REPLY [7 votes]: You do not need $\dim(R(A)\cap R(B)) = \dim(R(AB))$. All you need is $\dim(R(A)\cap R(B)) \ge \dim(R(AB))$, which is easy to prove using $AB=BA$.


text:
\vspace{-7pt}
\section*{Acknowledgements}

The authors are grateful to Max Goldstein for initiating the grasping example in Section \ref{sec:grasping} and contributions to the conference version of this paper presented at CoRL 2018. We also gratefully acknowledge the support of NVIDIA Corporation with the donation of the Titan Xp GPU used for this research.

\vspace{-5pt}
\section*{Funding}

The authors were partially supported by the Office of Naval Research [Award Number: N00014-18-1-2873], the National Science Foundation [IIS-1755038], the Google Faculty Research Award, and the Amazon Research Award.


TITLE: Evaluating $b=1+2^\sqrt{\log_23}-3^\sqrt{\log_23}$
QUESTION [2 upvotes]: Evaluating $b=1+2^\sqrt{\log_23}-3^\sqrt{\log_23}$
I am aware that $a^{\log_ax}=x$ but that doesn't seem to apply here.
$b=1+e^{\ln 2^\sqrt{\log_23}}-e^{\ln3^\sqrt{\log_23}}=1+e^{\sqrt{\frac{\ln3}{\ln2}}\ln2}-e^{\sqrt{\frac{\ln3}{\ln2}}\ln3}$
Not able to proceed next.

REPLY [1 votes]: I also assume the expression is $b=1+2^\sqrt{\log_23}-3^\sqrt{\log_32}$.
By the substitution , $\log_23=t\Rightarrow 3=2^t$ we have,
$$b=1+2^{\sqrt t}-(2^t)^{\sqrt{\tfrac1t}}=1$$


TITLE: Help with Geometric or Arithmetic progression
QUESTION [0 upvotes]: Evaluate
$$2004\cdot\left(\frac{1}{1\cdot2} + \frac{1}{2\cdot3} + \frac{1}{3\cdot4}+\dots + \frac{1}{2003\cdot2004}\right)$$
I think that this is based on either geometric or arithmetic progressions but I am not sure.
Please help me solve this problem.

REPLY [2 votes]: You should know that $\dfrac{1}{x(x+1)}=\dfrac{1}{x}-\dfrac{1}{x+1}$.
Apply this to your series. I will ignore the $2004$ factor for now.
$$\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\dots+\frac{1}{2003\cdot 2004}=1\color{red}{\underbrace{-\frac{1}{2}+\frac{1}{2}}}\color{#AB4DEF}{\underbrace{-\frac{1}{3}+\frac{1}{3}}}\dots\color{orange}{\underbrace{-\frac{1}{2003}+\frac{1}{2003}}}-\frac{1}{2004}$$
See how you can cancel pretty much all the terms? What you are left with is $1-\dfrac{1}{2004}$, which equals $\dfrac{2003}{2004}$. Now don't forget that $2004$ factor at the left.
$$\color{blue}{2004}\cdot\frac{2003}{\color{blue}{2004}}=2003$$
$$\displaystyle \color{green}{\boxed{\therefore 2004\cdot\left(\dfrac{1}{1\cdot 2}+\dfrac{1}{2\cdot 3}+\dfrac{1}{3\cdot 4}+\dots + \dfrac{1}{2003\cdot 2004}\right)=2003}}$$

If you want to see why $\dfrac{1}{x(x+1)}=\dfrac{1}{x}-\dfrac{1}{x+1}$, it is easy to prove. Just use LHS-RHS. I will try to make $\dfrac{1}{x}-\dfrac{1}{x+1}$ equal to $\dfrac{1}{x(x+1)}$.
$$\frac{1}{x}-\dfrac{1}{x+1}=\frac{x+1}{x(x+1)}-\frac{x}{x(x+1)}=\frac{x+1-x}{x(x+1)}=\frac{1}{x(x+1)}$$
$$\therefore \frac{1}{x}-\frac{1}{x+1}=\frac{1}{x(x+1)} \ \ \text{by LHS-RHS}$$


TITLE: $T \circ R=R \circ T$ for Linear Operators
QUESTION [0 upvotes]: Let $T,R: V \rightarrow V$ be two linear maps of rank 1 with the same kernel and the same image.  Prove that $T \circ R=R \circ T$.
I cannot use the rank/nullity theorem since $V$ is not necessarily finite-dimensional?. Do I have to prove that $T \circ R= (T \circ R)^{-1}$? How do I proceed? any hints

REPLY [1 votes]: We have $T(v) = \varphi(v)w_1$ for some $0 \neq w_1 \in V$ and $0 \neq \varphi \in V^{*}$. Similarly, $R(v) = \psi(v)w_2$ for some $0 \neq w_2 \in V$ and $0 \neq \psi \in V^{*}$. If $T$ and $R$ have the same image, then $w_2 = \lambda w_1$ for some $0 \neq \lambda \in \mathbb{F}$. If $T$ and $R$ have the same kernel, then
$$ \ker \varphi = \ker T = \ker R = \ker \psi $$
so $\psi = \mu \varphi$ for some $0 \neq \mu \in \mathbb{F}$. Thus,
$$ R(v) = \lambda \mu \varphi(v) w_1 = \lambda \mu T(v) $$
so $R = cT$ for $0 \neq c = \lambda \mu$. This immediately implies that $R$ and $T$ commute.


TITLE: How to show that the following function is continuous at 0?
QUESTION [1 upvotes]: Define a function $f$ as
$$ f(x) =
\begin{cases}
\frac{p}{q^2},  & \text{if $x \in \Bbb Q,$ $p,q\in \Bbb Z $ $p$ and $q$ are relatively prime} \\
x^2, & \text{if $x \notin \Bbb Q$}
\end{cases}$$
Is $f$ continues at $x=0$ ?
I understand that I have to prove or disprove that the limit exists at $0$, i.e. prove or disprove that for any $\epsilon>0$ there exists $\delta>0$ so that if $0<|x−0|<δ$ then $|f(x)−f(0)|<ϵ$. I am confused as to how I can actually go about this proof.

REPLY [0 votes]: Notice that $f(0)=0$, so we need to prove that for all $\epsilon$, there exists a $\delta$ such that $|x|<\delta\Rightarrow |f(x)|<\epsilon$. Since for $x<1$, $f(x)<x$, we see that setting $\delta=\min\{1,\epsilon\}$ gives us the desired result, as when $|x|<\epsilon$, we immediately get $|f(x)|<|x|<\epsilon$ and when $\epsilon>1$, $|x|<1\Rightarrow |f(x)|<1<\epsilon$


TITLE: What is the mathematical motivation behind the "Second Fundamental Form" and How is it related to Gaussian Curvature?
QUESTION [0 upvotes]: I understand the first fundamental form but couldn't understand the second fundamental form and How these two are related to Gaussian Curvature. Could you explain?

REPLY [0 votes]: ADDED: Since Ted didn't completely like my answer, I thought I'd provide another way to explain the second fundamental form. If you have a surface in $3$-space, you can move it around by rotations and translations without changing its shape. So, given any point on the surface, you can move the surface so that the point is at the origin and the tangent plane at that point is the $xy$-plane. The surface near the origin is now a graph of a function,
$$ z= f(x,y), $$
where $f(0,0) = 0$ and the partial derivatives satisfy $f_x(0,0) = f_y(0,0) = 0$. In other words, the origin is a critical point of $f$. With the surface positioned like this, the second fundamental form at the origin is simply the Hessian of $f$ there,
$$
H = \begin{bmatrix} f_{xx} & f_{xy} \\ f_{yx} & f_{yy} \end{bmatrix}
$$
As you know, eigenvalues and eigenvectors of $H$ tell you something about the shape of the surface near that point. So that's what the second fundamental form tells you about the shape of the surface near any given point on it.
ORIGINAL ANSWER:
Here's the short version: The second fundamental form, as you must know, encodes the directional derivative of the unit normal vector, as a function of the point on the surface. If the surface is flat, the unit normal is constant and therefore the derivative is zero in every direction. Otherwise, the second fundamental form tell you how curved the surface is, if you head in a given direction. Since the second fundamental form turns out to be represented as a symmetric matrix, there is a direction with minimal curvature and an orthogonal direction with maximal curvature. The Gauss curvature is simply the product of these so-called principal curvatures, which is also the determinant of the second fundamental form written as a matrix with respect to an orthonormal frame.
This explanation is not enough to really understand what's going on. You achieve that only by studying the details carefully, say from @TedShifrin's book and doing all the calculations yourself. It might not make sense at first, but if you persist, it eventually will.