Let us first condition on this constant-probability event over the build-clean process. Next, let us condition on the realization of the hash function $h$, which is independent of the randomness in the snaking. Conditioned on this realization, for $loc_p[i]=H(z_i)[p]$ and $sloc_p=\textsc{LazySnake}(loc_p, M/d)$ we have from <Ref> that

\begin{align*}
\E_{\snake}\left[|sloc_p[i]-sloc_p[j]|\right] \ge \Omega(1) \cdot \dcap{M/d}(loc_p[i], loc_p[j]).
\end{align*}

Now, taking an expectation with respect to the choice of the hash function, we get

\begin{align*}
\E_h\E_{\snake}\left[|sloc_p[i]-sloc_p[j]|\right] \ge \Omega(1) \cdot \E_h\left[\dcap{M/d}(loc_p[i], loc_p[j])\right].
\end{align*}

Let $A$ be the event that only one of the $k'$ special coordinates hashes to $p$. Then, we have that $\Pr[A]=\left(1-\frac1k\right)^{k'-1} \ge \Omega(1)$, yielding

\begin{align*}
\E_h\left[\dcap{M/d}(loc_p[i], loc_p[j])\right] &\ge \Omega(1)\cdot\E_h\left[\dcap{M/d}(loc_p[i], loc_p[j]) ~|~ A\right]
\end{align*}

Furthermore, conditioned on $A$, we have

\begin{align*}
&\E_h\left[\dcap{M/d}(loc_p[i], loc_p[j]) ~|~ A\right] \\
&\qquad=\sum_{r=1}^{k'} \frac{1}{k'} \cdot \E_h\left[\dcap{M/d}(loc_p[i], loc_p[j]) ~|~ \text{only $r^{\text{th}}$ special coordinate hashes to $p$}\right].
\end{align*}

But now, observe that if only the $r^{\text{th}}$ special coordinate hashes to $p$, we have $\dcap{M/d}(loc_p[i], loc_p[j]) =|z_i[c_r]-z_j[c_r]|$. This is because $|z_i[c_r]-z_j[c_r]|$ is at most $M/100d$, which is smaller than the cap $\frac{M}{d}$. Finally, recalling <Ref>,

\begin{align*}
\E_h\left[\dcap{M/d}(loc_p[i], loc_p[j]) ~|~ A\right] &= \sum_{r=1}^{k'}\frac{1}{k'}\left|z_i[c_r]-z_j[c_r]\right| \ge \Omega(1)\cdot \frac{1}{k'}\cdot \|x_i-x_j\|_1 \ge \Omega(1)\cdot \frac{1}{k}\cdot \|x_i-x_j\|_1.
\end{align*}

Putting everything together, we get

\begin{align*}
\E_{\bc}\E_h\E_{\snake}\left[|sloc_p[i]-sloc_p[j]|\right] &\ge \Omega(1) \cdot \frac{\|x_i-x_j\|_1}{k}.
\end{align*}

Case 2: $\|x_i-x_j\|_1 > M.$

In this case, $\dcap{M}(x_i, x_j)=M$. First, by <Ref>, we have that with constant probability over the build-clean process, $\|z_i - z_j\|_1 > cM$ for some constant $c$. We condition on this constant probability event. Given that this event holds, let us count the number of coordinates in $z_i-z_j$ that have magnitude smaller than $\frac{cM}{100d}$. Recall that by the properties of the build-clean algorithm (<Ref>), there are at most $2d$ “not-full" coordinates in $z_i-z_j$ that are neither exactly 0 or $\frac{M}{100d}$, and are in $\left[0, \frac{M}{100d}\right]$. Thus, coordinates that are smaller than $\frac{cM}{100d}$ must lie in this set of at most $2d$ not-full coordinates, and their contribution to $\|z_i-z_j\|_1$ is no more than $2d\cdot \frac{cM}{100d}=\frac{cM}{50}$. Since $\|z_i-z_j\|_1$ is at least $cM$, there is at least $\frac{49cM}{50}$ distance left, and this must be contributed to by the set of “full" coordinates that is exactly $\frac{M}{100d}$ and the not-full coordinates that are at least $\frac{cM}{100d}$. The total number of these coordinates is at the very lest $\frac{49cM}{50}\cdot \frac{100d}{M}=98cd=\Omega(d)$, and their sum is at least $\frac{49cM}{50}=\Omega(M)$.

Thus, under the conditioned event, we know that $z_i-z_j$ has a set of $k'=\Omega(d)$ “special" coordinates $c_1,\dots,c_r,\dots,c_{k'}$ such that the sum of their absolute values is $\Omega(M)$. Fix $p \in \{1,\dots,k\}$, and let $A$ be the event that the non-special coordinates that get hashed to $p$ amount for a distance of at least $\frac{M}{C_1d}$ for a suitable constant $C_1$. Concretely, under $A$, $\left|\sum_{q \in [8d^2]:q \text{ not special},h(q)=p}(z_i[q]-z_j[q])\right| \ge \frac{M}{C_1d}$.
We have that

\begin{align*}
\E\left[|sloc_p[i]-sloc_p[j]|\right] &= \Pr[A]\cdot \E\left[|sloc_p[i]-sloc_p[j]| ~|~ A\right] \\
&\quad + \Pr[\neg A]\cdot \E\left[|sloc_p[i]-sloc_p[j]| ~|~ \neg A\right]
\end{align*}

Conditioned on $A$, we are happy even if none of the special coordinates hash to $p$, which happens with probability $\left(1-\frac{1}{k}\right)^{k'}  \ge \Omega(1)$. In this case, by <Ref>, lazy snaking will capture at least a constant fraction of $\frac{M}{C_1d}$, yielding

\begin{align*}
\E\left[|sloc_p[i]-sloc_p[j]| ~|~ A\right] &\ge \Omega(1) \cdot \frac{M}{d}.
\end{align*}

If $A$ does not occur, we have that $\left|\sum_{q \in [8d^2]:q \text{ not special},h(q)=p}(z_i[q]-z_j[q])\right| < \frac{M}{C_1d}$. In this case, we are happy if exactly one of the special coordinates hashes to $p$, which happens with probability $\left(1-\frac{1}{k}\right)^{k'-1} \ge \left(1-\frac{1}{k}\right)^{k'} \ge \Omega(1)$. This will ensure a distance of at least $\frac{cM}{100d} - \frac{M}{C_1d}=\Omega(1)\cdot\frac{M}{d}$. Lazy snaking will yet again capture at least a constant fraction of this distance in expectation, yielding

\begin{align*}
\E\left[|sloc_p[i]-sloc_p[j]| ~|~ \neg A\right] &\ge \Omega(1) \cdot \frac{M}{d}.
\end{align*}

In total, we get that

\begin{align*}
\E\left[|sloc_p[i]-sloc_p[j]|\right] &\ge \Pr[A]\cdot \Omega(1) \cdot \frac{M}{d}
+ \Pr[\neg A]\cdot \Omega(1)\cdot \frac{M}{d} \\
&\ge \Omega(1) \cdot \frac{M}{d} \\
&= \Omega(1)\cdot \frac{\dcap{M}(x_i, x_j)}{k}.
\end{align*}

Finally, boosting with $O(\log(n))$ copies of the $O(d)$-sized embeddings gives us <Ref>.

We note that <Ref> provides a tool potentially of general interest. For example, in <Ref>, we provided a novel proof for embedding fixed cap tree metrics into $\polylog(n)$ dimensions. However, note how we can also instead obtain this result as a direct corollary of <Ref>, and Theorem 3 of [21] that embeds tree metrics into $\ell_1$.

§ DISCUSSION AND OPEN PROBLEMS

Our results show that $\ell_1$ metrics that can be derived by Tree Ising Models allow for low-dimensional embeddings into $\ell_1$ with constant distortion. Recall that Tree Ising Models are the class of undirected graphical models on trees, or equivalently, the class of Bayesian networks where the underlying graph is a directed tree with all edges pointing away from a designated root. It is natural to wonder if we can obtain low-dimensional $\ell_1$ embeddings for more general classes of Bayesian networks. Tree-structured Bayesian networks are especially convenient because they allow for an efficient top-down sampling procedure. For general Bayesian networks that are not trees, the treewidth of the underlying graph is a relevant quantity that is known to characterize the difficulty of sampling from the model [57]. The treewidth of a graph measures how “tree-like" a graph is, and given that sampling from tree-structured Bayesian networks is easy, it seems natural that the difficulty of sampling from general graphical models scales with its treewidth.

Because trees have treewidth 1, our result can be stated as the following—of the class of Bayesian networks on $N$ variables whose underlying undirected graph has treewidth 1, the sub-class that has the special property that all the directed edges point away from the root allow for embedding into $\ell_1$ with $\polylog(N)$ dimensions and constant distortion. However, the question about general Bayesian networks with treewidth 1 still remains open. This class consists of directed trees where a single node can have multiple parents (also known as polytrees) [24, 22, 23], and is known to be structurally very different from trees where all edges point away from a single root. In particular, our techniques don't readily generalize to this class, because of the more complicated nature of dependencies in these models.

Let $D$ be a joint distribution on $N$ binary random variables $X_1,\dots,X_N$ given by a Bayesian network whose underlying undirected graph is a tree (has treewidth 1).[Note again that all the edges in the Bayesian network need not be pointing away from a single root node.] Consider the metric $d_D(X_i, X_j)=\Pr_D[X_i \neq X_j]$. Does this metric embed into $\ell_1$ with constant distortion and with $N^{o(1)}$ dimensions?

The next natural direction is to see how far this agenda can be pushed—how about Bayesian networks having treewidth $> 1$? As it turns out, we cannot even hope to obtain a low-dimensional $\ell_1$ embedding for all metrics dictated by treewidth-3 Bayesian networks.

There exists a Bayesian network $D$ on $N$ binary random variables $X_1,\dots,X_N$ whose underlying undirected graph has treewidth 3, such that embedding the metric $d_D(X_i, X_j)=\Pr_D[X_i \neq X_j]$ into $\ell_1$ with $O(1)$ distortion requires $N^{\Omega(1)}$ dimensions.

We instantiate the lower bound instance based on the recursive diamond graph from [21] in the form of a graphical model. [21] obtain their lower bound via recursive construction in Hamming space shown in <Ref>.

The recursive diamond graph in Hamming space.

The $n^{\text{th}}$ level of this recursive construction $H^{(n)}$ has $M=\frac{2}{3}\cdot4^n + \frac43$ many Hamming vectors. To obtain $H^{(n+1)}$ from $H^{(n)}$, any edge connecting two vectors at a (normalized) Hamming distance of $1/2^{n}$ is split up, and two new vectors that are at a distance of $1/2^{n+1}$ from each of the these are introduced. <cit.> asserts that embedding these vectors into $\ell_1$ with $O(1)$ distortion requires $M^{\Omega(1)}$ dimensions.

We construct a Bayesian network that has the same distances as the diamond graph above. Refer to <Ref>.

A Bayesian network based on the recursive diamond graph.

Each level $G^{(n)}$ of the instance consists of some $D$ nodes and some $X$ nodes. The $D$ nodes correspond to the points in Hamming space from <Ref>, while the $X$ nodes simulate 50-50 coin flips. The $(n+1)^\text{th}$ level $G^{(n+1)}$ of the instance is constructed from $G^{(n)}$ by splitting every edge connecting two $D^{(n)}$ nodes at a distance of $1/2^{n}$, introducing two new $D^{(n+1)}$ nodes and an $X^{(n+1)}$ node in the process. <Ref> summarizes the properties of this recursive construction:

Level     $G^{(0)}$     $G^{(1)}$     $G^{(2)}$     $G^{(3)}$     …    $G^{(n)}$

#splittable edges     1     4     16     64     …    $4^n$

#$D$ nodes     2     4     12     44     …    $\frac{2}{3}\cdot4^n + \frac43$

#$X$ nodes     0     1     5     21     …    $\frac13\cdot4^n-\frac13$

Properties of $G^{(n)}$.

To obtain a sample from the Bayesian network, we first independently sample a 50-50 coin flip for every $X$ node in the network. The $D$ nodes can then be sampled in a hierarchical manner. First, the $D$ nodes in the $0^{\text{th}}$ level are deterministically set: $D^{(0)}_{0\dots0}=0$ and $D^{(0)}_{1\dots1}=1$ with probability 1. Then, for $n=1,2,\dots$, we inductively realize $D^{(n)}$ nodes as follows: let $D^{(n)}_x$ and $D^{(n)}_y$ be nodes that arise from splitting an edge $(D^{(n-1)}_u, D^{(n-1)}_v)$ with node $X^{(n)}_i$, and let $x < y$ and $u < v$ lexicographically. Recall that $D^{(n-1)}_u, D^{(n-1)}_v$ and $X^{(n)}_i$ have already been realized. Then,

\begin{align*}
&D^{(n)}_x \gets D^{(n-1)}_u, D^{(n)}_y \gets D^{(n-1)}_v,  \qquad\text{if } X^{(n)}_i = 0 \\
&D^{(n)}_x \gets D^{(n-1)}_v, D^{(n)}_y \gets D^{(n-1)}_u,  \qquad\text{if } X^{(n)}_i = 1.
\end{align*}

In other words, $X^{(n)}_i$ acts as a “switch" node.
We can verify that the distances between the $D$ nodes mimic the distances between the corresponding Hamming vectors. Concretely,

\Pr[D^{(n)}_{x} \neq D^{(n)}_{y}] = \|x-y\|_1.

Furthermore, the marginal probability of a $D$ node being equal to 1 is exactly equal to the fraction of $1$'s in the Hamming vector representing it.

Observe that $G^{(n)}$ has $N<2M$ many $D$+$X$ nodes in total, where $M=\frac{2}{3}\cdot4^n + \frac43$ is the number of Hamming vectors in $H^{(n)}$ above. If we were able to embed the nodes of $G^{(n)}$ into $\ell_1$ with constant distortion in $N^{o(1)}=M^{o(1)}$ dimensions, we can use the embeddings of the $D$ nodes as the embeddings of the Hamming vectors in the lower bound instance from [21] (i.e., <Ref> above), and this will give us an $M^{o(1)}$ dimensional embedding of the recursive diamond graph, which we know is not possible. Thus, any constant-distortion embedding of $G^{(n)}$—a Bayesian network on $N$ nodes—into $\ell_1$, necessarily requires $N^{\Omega(1)}$ many dimensions.

We will now argue that the undirected graph underlying $G^{(n)}$ for any $n \ge 1$ has treewidth equal to 3. We will slightly abuse notation and refer to the undirected graph underlying $G^{(n)}$ by $G^{(n)}$.

To see that the treewidth is at least 3, we note that the treewidth of a graph is at least the treewidth of any subgraph of the graph. For $n \ge 1$, observe that $G^{(n)}$ contains the subgraph underlying $G^{(1)}$, and we can verify, e.g., by brute-force, that this small subgraph has treewidth equal to 3.

We will now show that the treewidth of $G^{(n)}$ is at most 3. For this, we appeal to the definition of the treewidth based on elimination orderings of the nodes <cit.>. This definition is especially well-suited in the context of inference via variable elimination in graphical models. An equivalent form of this definition is as follows: first, we specify an ordering over the nodes in the graph. Then, we eliminate nodes in the graph in this order. Whenever we eliminate a node, we add an edge (if there isn't one already) between every pair of its neighbors that are still surviving. Before we eliminate a node, we record the count of nodes it is connected to. The maximum count that we see until we eliminate all nodes is the treewidth with respect to this ordering, and the smallest maximum count over all orderings is the graph's treewidth.

Thus, to show that the treewidth of $G^{(n)}$ is at most 3, we only need to come up with an ordering that witnesses treewidth to be at most $3$. Given the hierarchical structure of $G^{(n)}$, this ordering is natural—we start eliminating nodes from the highest level to the lowest level. Concretely, we first eliminate all the $D^{(n)}$ nodes, in say lexicographical order. Then, we eliminate all the $X^{(n)}$ nodes (again, in say lexicographical order). We then eliminate all the $D^{(n-1)}$ nodes, followed by all the $X^{(n-1)}$ nodes, and so on, all the way until we empty the graph.

Half the $D^{(2)}$ nodes eliminated.

All $D^{(2)}$ nodes eliminated.

$X^{(2)}$ nodes eliminated. This is $G^{(1)}$.

Level-wise elimination of nodes in $G^{(n)}$.

To see that the maximum degree of any node that is about to be eliminated is at most 3, consider what happens in the example in <Ref>, where we start with $G^{(2)}$. First, we eliminate $D^{(2)}$ nodes, followed by $X^{(2)}$ nodes. Observe that the degree of any $D^{(2)}$ node prior to elimination is exactly 3—this corresponds to the two $D^{(1)}$ nodes and $X^{(1)}$ node generating it. After we eliminate a $D^{(2)}$ node, we must introduce pairwise edges between its neighbors—since there is already an edge between its parent $D^{(1)}$ nodes, we only need to add edges between the $X^{(1)}$ and $D^{(1)}$ nodes. Next, when it comes to eliminating the $X^{(2)}$ nodes, observe that the degree of these nodes prior to elimination is exactly 2—this corresponds to the two $D^{(1)}$ nodes that it split. Finally, when we eliminate these nodes, we don't need to introduce any new edges, because the $D^{(1)}$ nodes that they are adjacent to were already connected by an edge. More importantly, observe that after this round of eliminating $D^{(2)}$ and $X^{(2)}$ nodes, we end up exactly with the graph underlying $G^{(1)}$! Thus, the same argument carries forward. More generally, for any $n$, when we eliminate $D^{(n)}$ and $X^{(n)}$ nodes, we end up with the graph underlying $G^{(n-1)}$, and the maximum degree of any node prior to elimination is at most 3. Thus, this ordering witnesses that the treewidth of $G^{(n)}$ is at most 3, as required.

Given that we have a (partial) positive answer for the treewidth-1 case, and that there isn't hope for a general result in the treewidth-3 case, this leaves the treewidth-2 case wide open (in addition to the open treewidth-1 case mentioned in <Ref>).

Let $D$ be a joint distribution on $N$ binary random variables $X_1,\dots,X_N$ given by a Bayesian network whose underlying undirected graph has treewidth 2. Consider the metric $d_D(X_i, X_j)=\Pr_D[X_i \neq X_j]$. Does this metric embed into $\ell_1$ with constant distortion and with $N^{o(1)}$ dimensions?

Finally, our lower bound for treewidth-3 is not an Ising model, so it remains open whether more general classes of Ising models permit low dimension embeddings. For example, it is simple to embed an Ising model whose underlying graph is a cycle.[Consider conditioning on the value of an arbitrary node in the cycle. The induced distribution is a tree Ising model (with an external field). Thus, any Ising model over a cycle can be written as the mixture of two tree Ising models, and accordingly we can embed its corresponding metric in $O(\log^2(N))$ dimension with $\Theta(1)$ distortion.]

Let $D$ be a joint distribution on $N$ binary random variables $X_1,\dots,X_n$ given by an Ising model. Consider the metric $d_D(X_i, X_j) = \Pr_D[X_i \ne X_j]$. For what classes of graphs (e.g. bounded treewidth, general graphs) does this metric embed into $\ell_1$ with constant distortion and with $N^{o(1)}$ dimensions?

§ ACKNOWLEDGEMENTS

We thank Frederic Koehler for helpful discussions. This work is supported by Moses Charikar's and Gregory Valiant's Simons Investigator Awards, Tselil Schramm's NSF CAREER Grant no. 2143246, and the National Defense Science & Engineering Graduate (NDSEG) Fellowship Program.

[1]
Alexandr Andoni, Moses S Charikar, Ofer Neiman, and Huy L Nguyen.
Near linear lower bound for dimension reduction in $\ell_1$.
In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 315–323. IEEE, 2011.

[2]
Amirali Abdullah, Ravi Kumar, Andrew McGregor, Sergei Vassilvitskii, and Suresh Venkatasubramanian.
Sketching, embedding and dimensionality reduction in information theoretic spaces.
In Artificial Intelligence and Statistics, pages 948–956. PMLR, 2016.

[3]
Gonzalo R Arce, Daniel Otero, Ana B Ramirez, and Jose-Luis Paredes.
Reconstruction of sparse signals from $\ell_1$ dimensionality-reduced cauchy random-projections.
In 2010 IEEE International Conference on Acoustics, Speech and Signal Processing, pages 4014–4017. IEEE, 2010.

[4]
Christopher JC Burges et al.
Dimension reduction: A guided tour.
Foundations and Trends® in Machine Learning, 2(4):275–365, 2010.

[5]
Enric Boix-Adsera, Guy Bresler, and Frederic Koehler.
Chow-liu++: Optimal prediction-centric learning of tree ising models.
In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 417–426. IEEE, 2022.

[6]
Bo Brinkman and Moses Charikar.
On the impossibility of dimension reduction in l1.
Journal of the ACM (JACM), 52(5):766–788, 2005.

[7]
Yair Bartal, Nova Fandina, and Ofer Neiman.
Dimensionality reduction: theoretical perspective on practical measures.
Advances in Neural Information Processing Systems, 32, 2019.

[8]
Radu Berinde, Anna C Gilbert, Piotr Indyk, Howard Karloff, and Martin J Strauss.
Combining geometry and combinatorics: A unified approach to sparse signal recovery.
In 2008 46th Annual Allerton Conference on Communication, Control, and Computing, pages 798–805. IEEE, 2008.

[9]
Yair Bartal, Lee-Ad Gottlieb, and Ofer Neiman.
On the impossibility of dimension reduction for doubling subsets of $\ell_p$.
SIAM Journal on Discrete Mathematics, 29(3):1207–1222, 2015.

[10]
Arnab Bhattacharyya, Sutanu Gayen, Eric Price, and NV Vinodchandran.
Near-optimal learning of tree-structured distributions by chow-liu.
In Proceedings of the 53rd annual acm SIGACT symposium on theory of computing, pages 147–160, 2021.

[11]
Guy Bresler and Mina Karzand.
Learning a tree-structured ising model in order to make predictions.

[12]
Zsolt Bartha, Júlia Komjáthy, and Järvi Raes.
Sharp bound on the truncated metric dimension of trees.
Discrete Mathematics, 346(8):113410, 2023.

[13]
Alan F Beardon and Juan Alberto Rodríguez-Velázquez.
On the k-metric dimension of metric spaces.
arXiv preprint arXiv:1603.04049, 2016.

[14]
Florent Baudier, Krzysztof Swieçicki, and Andrew Swift.
No dimension reduction for doubling subsets of $\ell_q$ when $q>2$ revisited.
Journal of Mathematical Analysis and Applications, 504(2):125407, 2021.

[15]
Yuri Boykov, Olga Veksler, and Ramin Zabih.
Markov random fields with efficient approximations.
In Proceedings. 1998 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (Cat. No. 98CB36231), pages 648–655. IEEE, 1998.

[16]
John P Cunningham and Zoubin Ghahramani.
Linear dimensionality reduction: Survey, insights, and generalizations.
The Journal of Machine Learning Research, 16(1):2859–2900, 2015.

[17]
Chandra Chekuri, Anupam Gupta, Ilan Newman, Yuri Rabinovich, and Alistair Sinclair.
Embedding $k$-outerplanar graphs into $\ell_1$.
SIAM Journal on Discrete Mathematics, 20(1):119–136, 2006.

[18]
Ferdinando Cicalese, Luisa Gargano, and Ugo Vaccaro.
Approximating probability distributions with short vectors, via information theoretic distance measures.
In 2016 IEEE International Symposium on Information Theory (ISIT), pages 1138–1142. IEEE, 2016.

[19]
Chandra Chekuri, Sanjeev Khanna, Joseph Naor, and Leonid Zosin.
A linear programming formulation and approximation algorithms for the metric labeling problem.
SIAM Journal on Discrete Mathematics, 18(3):608–625, 2004.

[20]
CKCN Chow and Cong Liu.
Approximating discrete probability distributions with dependence trees.
IEEE transactions on Information Theory, 14(3):462–467, 1968.

[21]
Moses Charikar and Amit Sahai.
Dimension reduction in the $\ell_1$ norm.
In The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., pages 551–560. IEEE, 2002.

[22]
Sourav Chatterjee and Mathukumalli Vidyasagar.
Estimating large causal polytree skeletons from small samples.
arXiv preprint arXiv:2209.07028, 2022.

[23]
Davin Choo, Joy Qiping Yang, Arnab Bhattacharyya, and Clément L Canonne.
Learning bounded-degree polytrees with known skeleton.
arXiv preprint arXiv:2310.06333, 2023.

[24]
Sanjoy Dasgupta.
Learning polytrees.
arXiv preprint arXiv:1301.6688, 2013.

[25]
Erik Demaine, Adam Hesterberg, Frederic Koehler, Jayson Lynch, and John Urschel.
Multidimensional scaling: Approximation and complexity.
In International Conference on Machine Learning, pages 2568–2578. PMLR, 2021.

[26]
Constantinos Daskalakis and Qinxuan Pan.
Sample-optimal and efficient learning of tree ising models.
In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 133–146, 2021.

[27]
Ioannis Z Emiris, Vasilis Margonis, and Ioannis Psarros.
Near neighbor preserving dimension reduction for doubling subsets of $\ell_1$.
arXiv preprint arXiv:1902.08815, 2019.

[28]
Arnold Filtser.
A face cover perspective to $\ell_1$ embeddings of planar graphs.
In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1945–1954. SIAM, 2020.

[29]
Anupam Gupta, Robert Krauthgamer, and James R Lee.
Bounded geometries, fractals, and low-distortion embeddings.
In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., pages 534–543. IEEE, 2003.

[30]
Anupam Gupta, Ilan Newman, Yuri Rabinovich, and Alistair Sinclair.
Cuts, trees and $\ell_1$-embeddings of graphs.
Combinatorica, 24(2):233–269, 2004.

[31]
Anupam Gupta and Éva Tardos.
A constant factor approximation algorithm for a class of classification problems.
In Proceedings of the thirty-second annual ACM symposium on Theory of computing, pages 652–658, 2000.

[32]
Paul Gutkovich and Zi Song Yeoh.
Computing truncated metric dimension of trees.
arXiv preprint arXiv:2302.05960, 2023.

[33]
Hiroshi Ishikawa and Davi Geiger.
Segmentation by grouping junctions.
In Proceedings. 1998 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (Cat. No. 98CB36231), pages 125–131. IEEE, 1998.

[34]
Piotr Indyk and Assaf Naor.
Nearest-neighbor-preserving embeddings.
ACM Transactions on Algorithms (TALG), 3(3):31–es, 2007.

[35]
Laurent Jacques.
Small width, low distortions: quantized random embeddings of low-complexity sets.
IEEE Transactions on information theory, 63(9):5477–5495, 2017.

[36]
Mohsen Jannesari and Behnaz Omoomi.
The metric dimension of the lexicographic product of graphs.
Discrete mathematics, 312(22):3349–3356, 2012.

[37]
M Kumar and Puneet Dokania.
Rounding-based moves for semi-metric labeling.
Journal of Machine Learning Research, 2016.

[38]
Vardis Kandiros, Constantinos Daskalakis, Yuval Dagan, and Davin Choo.
Learning and testing latent-tree ising models efficiently.
In Gergely Neu and Lorenzo Rosasco, editors, Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 1666–1729. PMLR, 12–15 Jul 2023.

[39]
Howard Karloff, Subhash Khot, Aranyak Mehta, and Yuval Rabani.
On earthmover distance, metric labeling, and 0-extension.
In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 547–556, 2006.

[40]
Robert Krauthgamer, James R Lee, and Havana Rika.
Flow-cut gaps and face covers in planar graphs.
In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 525–534. SIAM, 2019.

[41]
M Pawan Kumar.
Rounding-based moves for metric labeling.
Advances in Neural Information Processing Systems, 27, 2014.

[42]
Nikhil Kumar.
An approximate generalization of the okamura-seymour theorem.
In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 1093–1101. IEEE, 2022.

[43]
M Pawan Kumar, Olga Veksler, and Philip HS Torr.
Improved moves for truncated convex models.
The Journal of Machine Learning Research, 12:31–67, 2011.

[44]
Felix Krahmer and Rachel Ward.
A unified framework for linear dimensionality reduction in l1.
Results in Mathematics, 70:209–231, 2016.

[45]
James R Lee, Arnaud de Mesmay, and Mohammad Moharrami.
Dimension reduction for finite trees in $\ell_1$.
Discrete & Computational Geometry, 50:977–1032, 2013.

[46]
Enrico Le Donne, Tapio Rajala, and Erik Walsberg.
Isometric embeddings of snowflakes into finite-dimensional banach spaces.
Proceedings of the American Mathematical Society, 146(2):685–693, 2018.

[47]
James R Lee and Mohammad Moharrami.
A lower bound on dimension reduction for trees in $\ell_1$.
arXiv preprint arXiv:1302.6542, 2013.

[48]
James R Lee and Assaf Naor.
Embedding the diamond graph in $l_p$ and dimension reduction in $l_1$.
Geometric & Functional Analysis GAFA, 14(4):745–747, 2004.

[49]
Vincent Lafforgue and Assaf Naor.
A doubling subset of $l_p$ for $p> 2$ that is inherently infinite dimensional.
Geometriae Dedicata, 172:387–398, 2014.

[50]
Martin Lotz.
Persistent homology for low-complexity models.
Proceedings of the Royal Society A, 475(2230):20190081, 2019.

[51]
Urs Lang and Conrad Plaut.
Bilipschitz embeddings of metric spaces into space forms.
Geometriae Dedicata, 87:285–307, 2001.

[52]
James R Lee and Anastasios Sidiropoulos.
On the geometry of graphs with a forbidden minor.
In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 245–254, 2009.

[53]
James R Lee and Anastasios Sidiropoulos.
Pathwidth, trees, and random embeddings.
Combinatorica, 33(3):349–374, 2013.

[54]
Massimo Melucci.
A brief survey on probability distribution approximation.
Computer Science Review, 33:91–97, 2019.

[55]
Assaf Naor.
Metric dimension reduction: a snapshot of the ribe program.
In Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018, pages 759–837. World Scientific, 2018.

[56]
Assaf Naor, Gilles Pisier, and Gideon Schechtman.
Impossibility of dimension reduction in the nuclear norm.
Discrete & Computational Geometry, 63(2):319–345, 2020.

[57]
Nathalie Peyrard, M-J Cros, Simon de Givry, Alain Franc, Stephane Robin, Regis Sabbadin, Thomas Schiex, and Matthieu Vignes.
Exact or approximate inference in graphical models: why the choice is dictated by the treewidth, and how variable elimination can be exploited.
Australian & New Zealand Journal of Statistics, 61(2):89–133, 2019.

[58]
Pankaj Pansari and M Pawan Kumar.
Truncated max-of-convex models.
In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2368–2376, 2017.

[59]
DA Rachkovskij.
Real-valued embeddings and sketches for fast distance and similarity estimation.
Cybernetics and Systems Analysis, 52(6):967–988, 2016.

[60]
Satish Rao.
Small distortion and volume preserving embeddings for planar and euclidean metrics.
In Proceedings of the fifteenth annual symposium on Computational geometry, pages 300–306, 1999.

[61]
Oded Regev.
Entropy-based bounds on dimension reduction in $l_1$.
Israel Journal of Mathematics, 195(2):825–832, 2013.

[62]
Oded Regev and Thomas Vidick.
Bounds on dimension reduction in the nuclear norm.
In Geometric Aspects of Functional Analysis: Israel Seminar (GAFA) 2017-2019 Volume II, pages 279–299. Springer, 2020.

[63]
Anastasios Sidiropoulos.
Non-positive curvature and the planar embedding conjecture.
In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 177–186. IEEE, 2013.

[64]
Terence Tao.
Embedding the heisenberg group into a bounded-dimensional euclidean space with optimal distortion.
Revista Matemática Iberoamericana, 37(1):1–44, 2020.

[65]
Richard C Tillquist, Rafael M Frongillo, and Manuel E Lladser.
Truncated metric dimension for finite graphs.
arXiv preprint arXiv:2106.14314, 2021.

[66]
Richard C Tillquist, Rafael M Frongillo, and Manuel E Lladser.
Getting the lay of the land in discrete space: A survey of metric dimension and its applications.
SIAM Review, 65(4):919–962, 2023.

§ LAZY SNAKING FOR LIPSCHITZ CAP LINE METRICS

We restate and prove <Ref>:

The first part of the claim is straightforward, since snaking can only reduce distance between two nodes.

For the second part, we will instead show that $\E[|\embed(i)-\embed(j)|] \ge \Omega(1)\cdot \dlcap{M'}(x_i, x_j)$, where $M'(t) = \frac{47}{7447}M(t)$. This is sufficient, because $\dlcap{M'}(x_i, x_j) \ge \frac{47}{7447}\dlcap{M}(x_i, x_j)$. Fix some $i < j$. Before reaching $loc[i]$, let $t_1$ be the last time we were at the origin and decided to either rest/snake, such that $t_1 \le loc[i]$. Then, it must have been the case that either (i) we decided to snake at $t_1$, and returned back to the origin at a time $t_2>loc[i]$, or (ii) we decided to rest but there was not another decision before $t_2>loc[i]$. Namely, we have

\begin{equation}
\label{eqn:lipschitz-line-proof-eqn1}
\frac{M(t_1)}{300} \le t_2 - t_1 \le \max \left(\frac{M(t_1)}{300} , \frac{2M(t_1)}{100} \right)= \frac{M(t_1)}{50}.
\end{equation}

\begin{equation}
\label{eqn:lipschitz-line-proof-eqn2}
t_2 > loc[i] \implies t_1 + \frac{M(t_1)}{50} > loc[i] \implies loc[i]-t_1 < \frac{M(t_1)}{50}.
\end{equation}

From Lipschitzness, we have,

\begin{align}
&|M(loc[i])-M(t_1))| \le |loc[i]-t_1| \le |t_2-t_1| \le \frac{M(t_1)}{50} \nonumber \\
\implies \qquad & \frac{49}{50}M(t_1) \le M(loc[i]) \le \frac{51}{50}M(t_1).
\end{align}

Combining with <Ref>, we get

\begin{equation}
\label{eqn:lipschitz-line-proof-eqn3}
loc[i]-t_1 < \frac{M(loc[i])}{49}.
\end{equation}

Observe also that by Lipschitzness, for every $t \in [t_1,t_2]$, we have

\begin{align}
&|M(loc[i])-M(t)| \le |loc[i]-t| \le |t_2-t_1| \le \frac{M(t_1)}{50} \le \frac{M(loc[i])}{49}\\
\implies \qquad & \frac{48M(loc[i])}{49} \le M(t) \le \frac{50M(loc[i])}{49}.
\end{align}

Let $E$ be the event that $snake[t_1]=0$ for some $t_1 \in \left[loc[i]-\frac{M(loc[i])}{49}, loc[i]\right]$, such that we are ready to flip a coin at $t_1$. Then, <Ref> implies that $\Pr[E]=1$. Repeating the same argument as above, but from the perspective of $t_1$, we get that there also exists a $t_0\in \left[loc[i]-\frac{M(loc[i])}{49}-\frac{50}{49}\frac{M(loc[i])}{49},loc[i]-\left(\frac{50}{51}\right)^2\frac{M(loc[i])}{300}\right]$ such that with probability 1, $snake[t_0]=0$ and we about to flip at $t_0$. We note here that $t$ was initialized to $-2M(0)$ in Step 1 of <Ref> precisely to ensure that such a $t_0$ always exists. Initializing in this manner ensures that there is always a distance of $\frac{M(loc[i])}{49}+\frac{50}{49}\frac{M(loc[i])}{49}$ before every $loc[i]$—if there wasn't, Lipschitzness would be violated.

We will first do the analysis for the setting where $M(loc[i]) \ge M(loc[j])$, so that $\max(M(loc[i]), M(loc[j]))$ $ = M(loc[i])$. The analysis for $M(loc[i]) < M(loc[j])$ is very similar, and is presented afterwards.
We have three cases:

Case 1a: $0 < |loc[i]-loc[j]|\le \frac{47}{7447}M(loc[i]).$

Here, $\dlcap{M'}(x_i, x_j)=|loc[i]-loc[j]|$. First, we invoke <Ref> and condition on arriving at $t_1 \in \left[ loc[i]-\frac{M(loc[i])}{49},loc[i]\right]$, where $snake[t_1]=0$ and we are about to flip a coin. Starting at $t_1$, observe that with at most $\frac{M(loc[i])}{49}\cdot \frac{49\cdot 300}{48M(loc[i])}=\Theta(1)$ “rest" flips, we get to a $t \in \left[loc[i]-\frac{50M(loc[i])}{49\cdot300}, loc[i]\right]$ such that $snake[t]=0$. This is because $t_1$ is at most $\frac{M(loc[i])}{49}$ away from $loc[i]$, and the each resting period is at least $\frac{48M(loc[i])}{49\cdot300}$ and at most $\frac{50M(loc[i])}{49\cdot300}$. Now, at $t$, we can flip a “snake", for which the snaking width is at least $\frac{48M(loc[i])}{49\cdot100}$. Observe that 1) $loc[i]$ is at most $\frac{50M(loc[i])}{49\cdot300}$ from $t$, 2) $loc[j]$ is at most $\frac{47}{7447}M(loc[i])$ away from $loc[i]$ and 3) $\frac{50M(loc[i])}{49\cdot300} + \frac{47}{7447}M(loc[i]) \le \frac{48M(loc[i])}{49\cdot100}$. Together, this ensures that both $loc[i]$ and $loc[j]$ are encountered going forward from $t$ within one snaking width, i.e., $snake[loc[j]]-snake[loc[i]]=loc[j]-loc[i]=\dlcap{M'}(x_i, x_j)$.

Case 2a: $\frac{47}{7447}M(loc[i]) < |loc[i]-loc[j]|\le \frac{99}{2401}M(loc[i]).$

In this case, $\dlcap{M'}(x_i, x_j)=\frac{47}{7447}M(loc[i])$. Repeating the same reasoning as above, we start at $t_1$, and then get to a $t \in \left[loc[i]-\frac{50M(loc[i])}{49\cdot300}, loc[i]\right]$ such that $snake[t]=0$ with a constant number of “rest" flips. Now, we flip another “rest", which ensures that $snake[loc[i]]=0$, and gets us to a $t \in \left[loc[i], loc[i]+\frac{50M(loc[i])}{49\cdot300}\right]$. Note that since $|loc[i]-loc[j]| > \frac{47}{7447}M(loc[i]) > \frac{50M(loc[i])}{49\cdot300}$ we know $t < loc[j]$ and that there is still some distance left to get to $loc[j]$. Now, for any $t \in [loc[i], loc[j]]$, by Lipschitzness, we have

|M(t)-M(loc[i])| \le |loc[i]-loc[j]| \le \frac{99}{2401}M(loc[i]),

which means that $M(t) \in \left[\frac{2392}{2401}M(loc[i]), \frac{2500}{2401}M(loc[i])\right]$. Therefore, with at most $\frac{99M(loc[i])}{2401}\cdot \frac{2401\cdot300}{2392 M(loc[i])}=\Theta(1)$ “rest" flips, we get to a $t$ which is in $\left[loc[j]-\frac{50M(loc[i])}{49\cdot300\cdot2}-\frac{2500M(loc[i])}{2401\cdot300}, loc[j]-\frac{50M(loc[i])}{49\cdot300\cdot2}\right]$. Once here, we can flip a “snake"—noting that 1) the snaking width is at least $\frac{2392}{2401\cdot100}M(loc[i])$ 2) the distance to $loc[j]$ is at most $\frac{50M(loc[i])}{49\cdot300\cdot2}+\frac{2500M(loc[i])}{2401\cdot300}$ and 3) the quantity in 2) is smaller than the quantity in 1), we get that $snake[loc[j]]$ is at least $\frac{50M(loc[i])}{49\cdot300\cdot2}$, which is at least a constant fraction of $\dlcap{M'}(x_i, x_j)$.

Case 3a: $\frac{99}{2401}M(loc[i]) < |loc[i]-loc[j]|.$

In this case, $\dlcap{M'}(x_i, x_j) = \frac{47}{7447}M(loc[i])$. We argued above that with probability 1, there exists a $t_0 \in \left[loc[i]-\frac{M(t_1)}{50} - \frac{M(t_0)}{50}, loc[i] - \frac{M(t_0)}{300} \right] \in \left[loc[i]-\frac{99M(loc[i])}{2401},loc[i]-\left(\frac{50}{51}\right)^2\frac{M(loc[i])}{300}\right]$ such that $snake[t_0]=0$ and we are about to flip a coin. Observe that by Lipschitzness, for any $t \in [t_0, loc[i]]$,

$$M(t) \in \left[\frac{2392}{2401}M(loc[i]), \frac{2500}{2401}M(loc[i])\right].$$

Therefore, with at most $\frac{99M(loc[i])}{2401}\cdot \frac{2401\cdot300}{2392M(loc[i])}=\Theta(1)$ “rest" flips, we get to a  $t$ which is in

$$\left[loc[i]-\left(\frac{50}{51}\right)^2\frac{M(loc[i])}{300}-\frac{2500M(loc[i])}{2401\cdot300}, loc[i]-\left(\frac{50}{51}\right)^2\frac{M(loc[i])}{300}\right].$$

Now, we may flip a “snake"—noting that 1) the snaking width is at least $\frac{2392M(loc[i])}{2401\cdot100}$ and 2) the distance to $loc[i]$ is at least $\left(\frac{50}{51}\right)^2\frac{M(loc[i])}{300}$ and at most $\left(\frac{50}{51}\right)^2\frac{M(loc[i])}{300}+\frac{2500M(loc[i])}{2401\cdot300}<\frac{2392M(loc[i])}{2401\cdot100}$, we can conclude that by the time we get to $loc[i]$, $snake[loc[i]]$ will at least be $\left(\frac{50}{51}\right)^2\frac{M(loc[i])}{300}=\Omega(1)\cdot\dlcap{M'}(x_i, x_j)$. Next, we know that with probability 1, there exists a $t'\in \left[loc[j]-\frac{M(loc[j])}{49}, loc[j]\right]$ such that $snake[t']=0$ and we are about flip a coin. Further, this $t'$ is larger than $loc[i]$, because $loc[j]-\frac{M(loc[j])}{49}$ needs to be larger than $loc[i]$ under the case we are studying. We catch hold of this $t'$, and with a constant number of “rest" flips, we ensure that $snake[loc[j]]=0$. Thus, we obtain that $|snake[loc[i]]-snake[loc[j]]| \ge \Omega(1)\cdot\dlcap{M'}(x_i, x_j)$.

Now, we will do the analysis for when $M(loc[i]) < M(loc[j])$, so that $\max(M(loc[i]), M(loc[j]))$ $ = M(loc[j])$. Again, we have three cases:

Case 1b: $0 < |loc[i]-loc[j]|\le \frac{47}{7447}M(loc[j]).$

Here, $\dlcap{M'}(x_i, x_j)=|loc[i]-loc[j]|$. By Lipschitzness, we have $M(loc[i])\in \left[\frac{7400}{7447}M(loc[j]),\frac{7494}{7447}M(loc[j])\right]$. First, we condition on arriving at $t_1$, where $snake[t_1]=0$ and we are about to flip a coin. Starting at $t_1$, observe that with at most $\frac{M(loc[i])}{49}\cdot \frac{49\cdot 300}{48M(loc[i])}=\Theta(1)$ “rest" flips, we get to a $t \in \left[loc[i]-\frac{50M(loc[i])}{49\cdot300}, loc[i]\right]$ such that $snake[t]=0$ and we are about to flip a coin. Now, at $t$, we can flip a “snake", for which the snaking width is at least $\frac{48M(loc[i])}{49\cdot100} \ge \frac{7400\cdot48M(loc[j])}{7447\cdot49\cdot100}$. Observe that 1) $loc[i]$ is at most $\frac{50M(loc[i])}{49\cdot300} \le \frac{7494\cdot50M(loc[j])}{7447\cdot49\cdot300}$ from $t$, 2) $loc[j]$ is at most $\frac{47}{7447}M(loc[j])$ away from $loc[i]$ and 3) $\frac{7494\cdot50M(loc[j])}{7447\cdot49\cdot300} + \frac{47}{7447}M(loc[j]) \le \frac{7400\cdot48M(loc[j])}{7447\cdot49\cdot100}$. Together, this ensures that both $loc[i]$ and $loc[j]$ are encountered going forward from $t$ within one snaking width, i.e., $snake[loc[j]]-snake[loc[i]]=loc[j]-loc[i]=\dlcap{M'}(x_i, x_j)$.

Case 2b: $\frac{47}{7447}M(loc[j]) < |loc[i]-loc[j]|\le \frac{99}{2401}M(loc[j]).$

In this case, $\dlcap{M'}(x_i, x_j)=\frac{47}{7447}M(loc[j])$. Repeating the same reasoning as above, we start at $t_1$, and then get to a $t \in \left[loc[i]-\frac{50M(loc[i])}{49\cdot300}, loc[i]\right]$ such that $snake[t]=0$ with a constant number of “rest" flips. Now, we flip another “rest", which ensures that $snake[loc[i]]=0$, and gets us to a $t \in \left[loc[i], loc[i]+\frac{50M(loc[i])}{49\cdot300}\right]$. Since, $M[loc[i]] < M[loc[j]]$, $t \in \left[loc[i], loc[i]+\frac{50M(loc[j])}{49\cdot300}\right]$. Note that since $|loc[i]-loc[j]| > \frac{47}{7447}M(loc[j])> \frac{50M(loc[j])}{49\cdot300}$ we know $t < loc[j]$ and there is still some distance left to reach $loc[j]$. Now, for any $t \in [loc[i], loc[j]]$, by Lipschitzness, we have

|M(t)-M(loc[j])| \le |loc[i]-loc[j]| \le \frac{99}{2401}M(loc[j]),

which means that $M(t) \in \left[\frac{2392}{2401}M(loc[j]), \frac{2500}{2401}M(loc[j])\right]$. Therefore, with at most $\frac{99M(loc[j])}{2401}\cdot \frac{2401\cdot300}{2392 M(loc[j])}=\Theta(1)$ “rest" flips, we get to a $t$ which is in $\left[loc[j]-\frac{50M(loc[j])}{49\cdot300\cdot2}-\frac{2500M(loc[j])}{2401\cdot300}, loc[j]-\frac{50M(loc[j])}{49\cdot300\cdot2}\right]$. Once here, we can flip a “snake"—noting that 1) the snaking width is at least $\frac{2392}{2401\cdot100}M(loc[j])$ and 2) the distance to $loc[j]$ is at most $\frac{50M(loc[j])}{49\cdot300\cdot2}+\frac{2500M(loc[j])}{2401\cdot300}$, and 3) the quantity in 2) is smaller than the quantity in 1), we get that $snake[loc[j]]$ is at least $\frac{50M(loc[j])}{49\cdot300\cdot2}$, which is at least a constant fraction of $\dlcap{M'}(x_i, x_j)$.

Case 3b: $\frac{99}{2401}M(loc[j]) < |loc[i]-loc[j]|.$

In this case, $\dlcap{M'}(x_i, x_j) = \frac{47}{7447}M(loc[j])$. We know that with probability 1, there exists a

$$t'\in \left[loc[i]-\frac{M(loc[i])}{49}, loc[i]\right]$$

such that $snake[t']=0$ and we are about flip a coin. We catch hold of $t'$, and with a constant number of “rest" flips, we ensure that $snake[loc[i]]=0$. Next, we argued above that with probability 1, there exists a $t_0 \in \left[ loc[j]-\frac{M(t_0)}{50} - \frac{M(t_1)}{50}\right] \in \left[loc[j]-\frac{99M(loc[j])}{2401},loc[j]-\left(\frac{50}{51}\right)^2\frac{M(loc[j])}{300}\right]$ such that $snake[t_0]=0$ and we are about to flip a coin. Observe that by Lipschitzness, for any $t \in [t_0, loc[j]]$, $M(t_0) \in \left[\frac{2392}{2401}M(loc[j]), \frac{2500}{2401}M(loc[j])\right]$. Therefore, with at most $\frac{99M(loc[j])}{2401}\cdot \frac{2401\cdot300}{2392M(loc[j])}=\Theta(1)$ “rest" flips, we get to a  $t$ which is in $\left[loc[j]-\left(\frac{50}{51}\right)^2\frac{M(loc[j])}{300}-\frac{2500M(loc[j])}{2401\cdot300}, loc[j]-\left(\frac{50}{51}\right)^2\frac{M(loc[j])}{300}\right]$. Now, we may flip a “snake"—noting that 1) the snaking width is at least $\frac{2392M(loc[j])}{2401\cdot100}$ and 2) the distance to $loc[j]$ is at least $\left(\frac{50}{51}\right)^2\frac{M(loc[j])}{300}$ and at most $\left(\frac{50}{51}\right)^2\frac{M(loc[j])}{300}+\frac{2500M(loc[j])}{2401\cdot300}<\frac{2392M(loc[j])}{2401\cdot100}$, we can conclude that by the time we get to $loc[j]$, $snake[loc[j]]$ will at least be $\left(\frac{50}{51}\right)^2\frac{M(loc[j])}{300}=\Omega(1)\cdot\dlcap{M'}(x_i, x_j)$.

Finally, note that in every case, we showed that, conditioned on the outcomes of at most a constant number of coin flips, $|snake[loc[i]]-snake[loc[j]]| = |\embed[i]-\embed[j]| \ge \Omega(1)\cdot \dlcap{M'}(x_i, x_j)$. This immediately gives that $\E[|\embed[i]-\embed[j]|] \ge \Omega(1)\cdot \dlcap{M'}(x_i, x_j)$, completing the proof.

§ PROOFS FOR GENERAL CAPPED Ł METRICS

§.§ Coordinate-wise Embeddings are Good

In this section, we will essentially reuse the analysis of the build-clean procedure from <Ref> in order to prove <Ref>. We restate the lemma here for convenience.

The proof is constructive. Without loss of generality, consider say the first coordinate of each of the $n$ points. We overload notation here and identify this coordinate of each point with $x_1,\dots,x_n$. If we map these coordinates to the line, we obtain a line graph metric. Our goal is to embed this line metric with a fixed cap $M$—we will do so using the build-clean framework from <Ref>. We will root the line at the leftmost point on the line (say this is $r$). For technical reasons again, we add an additional node $r_0$ at a distance $2M$ to the left of $r$. We will split up the line into edges of length $\frac{M}{100d}$—these edges correspond to the “shortened" caterpillar edges from the tree decomposition in <Ref>. We group edges into build and clean stages. As before, each edge $e$ has auxiliary information $a(e)$ associated with it which determines whether it is processed in the build/clean stage. We set $\lb=4d$ and $\lc=9d$. The auxiliary information for the leftmost/first edge is chosen uniformly at random from $\{0,\dots,\lb+\lc-1\}$. Thereafter, for every edge $e$, $a(e)=a(par(e))+1 \mod (\lb + \lc)$, where $par(e)$ is simply the adjacent edge to the left of $e$. If $a(e) \in \{0,\dots,\lb-1\}$, $e$ is processed in the build stage, else it is processed in the clean stage. After processing all the edges, all the points on the line will be mapped to an embedding of size $|H|=8d$.  We construct this $|H|$-sized embedding for every location on the line metric in the same way as described in <Ref> for Lipschitz-cap trees.  In the language of the analysis there, let $\embed[1],\dots,\embed[n]$ denote the embeddings thus obtained (these correspond to the vectors $v^{(1)}_1,\dots, v^{(1)}_n$ in the language of <Ref>). To avoid simply rewriting the entire analysis from <Ref>, we will walk through the claims therein in a stepwise manner, and only specify the parts relevant to the special case we are in, i.e., a line graph with a fixed cap.

Since the cap at every location is equal to $M$, we do not need to relate the caps of points on nearby edges, as we did in <Ref> and <Ref>.

Next, <Ref> holds too—at any location $x$ immediately after processing an entire clean stage, all the coordinates of $\embed[x]$ are identically 0. While the same proof in <Ref> works, we can also see this more directly here. The build stage, by virtue of processing only at most $4d$ edges, fills in only at most $4d$ coordinates to a value $\frac{M}{100d}$, while a complete clean stage comprises of $9d$ edges of length $\frac{M}{100d}$, and hence definitely zeros out all the nonzero coordinates.

Because of complete cleaning, the proof in <Ref> would similarly give us that for any location $x$, $\|\embed[x]\|_1 \le \frac{M}{2}$ (actually, we would obtain a stronger bound of $\frac{M}{25}$, but the weaker bound suffices).

At this point, we have already proved part (1) of <Ref>. Because of the way the build-clean procedure works, the embeddings as we move continuously along the line are coordinate-wise Lipschitz, and only ever capture distance in one coordinate along adjacent locations. This already gives us that $\|\embed[i]-\embed[j]\|_1 \le |x_i -x_j|$. From the norm bound on the embedding, we also have that

\|\embed[i]-\embed[j]\|_1 \le \|\embed[i]\|_1 + \|\embed[j]\|_1 \le M.

Hence, we have that $\|\embed[i]-\embed[j]\|_1 \le \min(|x_i-x_j|, M)$.

Next, we turn our attention towards proving part (2) of the lemma. Consider the guarantee given by <Ref>. Let $x_i$ be to the left of $x_j$ without loss of generality. Then, the LCA of $x_i$ and $x_j$ on the line would simply be $x_i$. The same proof, with “$\log(n)$" replaced with “$d$" would yield that

\begin{align}
\E\left[\|\embed[x_i]-\embed[x_j]\|_1\right] \ge \Omega(1) \cdot \min(|x_i-x_j|, M),
\end{align}

and this is precisely what we wanted to prove for the purposes of part(2) in <Ref>.

§.§ Concatenations of Coordinate-wise Embeddings are Good

First, we state a reverse application of Markov's inequality:

Let $F$ be a random variable such that $F \in [0, M]$ with probability 1, and $\E[F] \ge c_1 M$, for $c_1 \le 1$. Then, for any $C_2 \ge 1$,

\begin{align*}
\Pr\left[F \ge \frac{c_1}{C_2}\cdot M\right] \ge 1-\frac{1-c_1}{1-\frac{c_1}{C_2}}.
\end{align*}

Define $G = M-F$, so that $G \in [0, M]$. Then $\E[G] = M - \E[F] \le M-c_1M$. Applying Markov's inequality,

\begin{align*}
&\Pr\left[F < \frac{c_1}{C_2}\cdot M \right] = \Pr\left[G > \left(1-\frac{c_1}{C_2} \right)\cdot M \right] \le \frac{1-c_1}{1-\frac{c_1}{C_2}} \\
\implies \qquad& \Pr\left[F \ge \frac{c_1}{C_2}\cdot M\right] \ge 1-\frac{1-c_1}{1-\frac{c_1}{C_2}}.
\end{align*}

We can now use <Ref> to prove the following general result which we can directly use to prove that the $z_i$ vectors constructed in <Ref> capture the capped distance well.

Suppose $R_1,\dots,R_d$ are independent random variables such that each $R_i \in [0, M]$ with probability 1, and $\E[\sum_{i=1}^dR_i] \ge c \cdot M$ for a constant $c \le 1$. Then,

\begin{align*}
\Pr\left[\sum_{i=1}^dR_i \ge \frac{c^2}{100}\cdot M\right] \ge \Omega(1).
\end{align*}

Assume for the sake of contradiction that

$$\Pr\left[\sum_{i=1}^dR_i \ge \frac{c^2}{100}\cdot M\right] < \min\left(\frac{1}{100}, 1- \frac{1-\left(\frac{99c}{100}\right)^2}{1-\frac{c^2}{100}}\right).$$

In particular, since the $R_i$s are non-negative, this implies that

\begin{equation}
\label{eqn:reverse-markovish-contradiction}
\Pr\left[\sum_{i=1}^jR_i \ge \frac{c^2}{100}\cdot M\right] < \min\left(\frac{1}{100}, 1- \frac{1-\left(\frac{99c}{100}\right)^2}{1-\frac{c^2}{100}}\right) \quad\text{for all $j\in\{1,\dots,d\}$}.
\end{equation}

We will reason about the random variable

\min\left(\sum_{i=1}^dR_i, c M\right) = \sum_{i=1}^d\min\left[R_i, \max\left(0, c M - \sum_{j=1}^{i-1} R_j\right)\right].

Let $A_i$ be the event that $\sum_{j=1}^iR_j < \frac{c}{100}\cdot M$ and $B_i$ be the event that $\sum_{j=1}^iR_j < \frac{c^2}{100}\cdot M$. Further, let $\Ind[A_i]$ and $\Ind[B_i]$ be their indicators. Note that $\Pr[B_i] \le \Pr[A_i]$, since $c \le 1$. Then, observe that

\begin{align*}
\min\left[R_i, \max\left(0, c M - \sum_{j=1}^{i-1} R_j\right)\right] &\ge \Ind[A_{i-1}]\cdot \min\left(R_i, \frac{99c}{100}\cdot M\right) \\
&\ge \Ind[A_{i-1}]\cdot \frac{99c}{100}\cdot R_i.
\end{align*}

Here, the last inequality follows because $\frac{99c}{100}\cdot R_i \le \frac{99c}{100}\cdot M$ as well as $\frac{99c}{100}\cdot R_i \le R_i$, since $c \le 1$. Thus, we obtain that

\begin{align*}
\E\left[\min\left(\sum_{i=1}^dR_i, c M\right)\right] &= \E\left[ \sum_{i=1}^d\min\left[R_i, \max\left(0, c M - \sum_{j=1}^{i-1} R_j\right)\right]\right] \\
&\ge \E\left[ \sum_{i=1}^d \Ind[A_{i-1}]\cdot \frac{99c}{100}\cdot R_i \right]\\
&= \sum_{i=1}^d \E\left[\Ind[A_{i-1}]\cdot \frac{99c}{100}\cdot R_i \right] \qquad(\text{linearity of expectation}) \\
&= \frac{99c}{100}\cdot\sum_{i=1}^d \E\left[\Ind[A_{i-1}]\right]\cdot \E\left[R_i \right] \qquad \text{(independence of $R_i$s)} \\
&= \frac{99c}{100}\cdot\sum_{i=1}^d \Pr\left[A_{i-1}\right]\cdot \E\left[R_i \right]\\
&\ge \frac{99c}{100}\cdot\sum_{i=1}^d \Pr\left[B_{i-1}\right]\cdot \E\left[R_i \right] \qquad \left(\text{since $\Pr[B_{i-1}] \le \Pr[A_{i-1}]$}\right)\\
&\ge \frac{99c}{100}\cdot\frac{99}{100}\cdot \sum_{i=1}^d\E\left[R_i \right] \qquad \text{(\Cref{eqn:reverse-markovish-contradiction})} \\
&\ge \left(\frac{99c}{100}\right)^2 M.
\end{align*}

Now, we invoke <Ref> with $F = \min\left(\sum_{i=1}^dR_i, c M\right)$. Note that $F \in [0, M]$ with probability 1, and $\E[F] \ge \left(\frac{99c}{100}\right)^2 \cdot M$ — thus, for $C_2=100\cdot \left(\frac{99}{100}\right)^2$, we get

\begin{align*}
\Pr\left[\min\left(\sum_{i=1}^dR_i, c M\right) \ge \frac{c^2}{100}\cdot M\right] &\ge 1-\frac{1-\left(\frac{99c}{100}\right)^2}{1-\frac{c^2}{100}}.
\end{align*}

Notice that we have ended up showing

\begin{align*}
\Pr\left[\sum_{i=1}^d R_i \ge \frac{c^2}{100}\cdot M\right] \ge \Pr\left[\min\left(\sum_{i=1}^dR_i, c M\right) \ge \frac{c^2}{100}\cdot M\right] &\ge 1-\frac{1-\left(\frac{99c}{100}\right)^2}{1-\frac{c^2}{100}},
\end{align*}

which contradicts <Ref>. Hence, it must be true that

\Pr\left[\sum_{i=1}^dR_i \ge \frac{c^2}{100}\cdot M\right] \ge \min\left(\frac{1}{100}, 1- \frac{1-\left(\frac{99c}{100}\right)^2}{1-\frac{c^2}{100}}\right) = \Omega(1).

We are now ready to prove <Ref>, which we resatate here for convenience.

Recall that $z_i$ is the concatenation of independently constructed vectors $v^{(q)}_i$ for $q \in \{1,\dots,d\}$. Let $R_q$ be the random variable $\|v^{q}_i-v^{(q)}_j\|_1$. Observe that the $R_q$'s are independent of each other, and that $\|z_i-z_j\|_1 = \sum_{q=1}^dR_q$.

Case 1: $\|x_i-x_j\|_1 \le M.$

In this case, $\dcap{M}(x_i, x_j)=\|x_i-x_j\|_1$. Furthermore, for every $q$, $|x_i[q]-x_j[q]|\le \|x_i-x_j\|_1$. From part (1) of <Ref>, this means that for every $q$, $R_q=\|v^{q}_i-v^{(q)}_j\|_1\in [0,\|x_i-x_j\|_1]$ with probability 1. Furthermore, from part (2) of <Ref>, $\E[R_q] \ge \Omega(1)\cdot |x_i[q]-x_j[q]|$. Thus,

\E\left[\sum_{q=1}^dR_q\right] \ge \Omega(1)\cdot \sum_{q=1}^d|x_i[q]-x_j[q]| = \Omega(1)\cdot \|x_i-x_j\|_1.

Instantiating <Ref> with these $R_q$ variables, we get

\begin{align*}
&\Pr\left[\sum_{q=1}^dR_q \ge \Omega(1)\cdot \|x_i-x_j\|_1\right] \ge \Omega(1) \\
\implies \qquad &\Pr\left[\|z_i-z_j\|_1 \ge \Omega(1)\cdot \|x_i-x_j\|_1\right] \ge \Omega(1).
\end{align*}

Case 2: $\|x_i-x_j\|_1 > M.$

In this case, $\dcap{M}(x_i, x_j)=M$. Observe first that for any $q\in \{1,\dots,d\}$, by part 1 of <Ref>, $R_q \in [0, M]$ with probability 1. Next, observe also that $\E\left[\sum_{q=1}^dR_q\right] \ge \Omega(1)\cdot M$. To see this, consider two cases. In one case, there exists a coordinate $q$ such that $|x_i[q]-x_j[q]| > M$. In this case, part (2) of <Ref> already promises us that for this $q$, $\E[R_q] \ge \Omega(1)\cdot M$, and since the $R_q$'s are non-negative, we have the same lower bound on $\E\left[\sum_{q=1}^dR_q\right]$. In the remaining case, $|x_i[q]-x_j[q]| \le M$ for all $q$. In this case, we can still apply part (2) of <Ref>, to say that

\begin{align*}
\E\left[\sum_{q=1}^dR_q\right] &= \sum_{q=1}^d\E\left[R_q\right] \\
&\ge \sum_{q=1}^d\Omega(1)\cdot |x_i[q]-x_j[q]| \\
&= \Omega(1)\cdot \|x_i-x_j\|_1 \\
&\ge \Omega(1) \cdot M,
\end{align*}

where the last inequality follows because $\|x_i-x_j\|_1 > M$ in the present case. Thus, we have shown that every $R_q$ is in $[0, M]$, and $\E\left[\sum_{q=1}^dR_q\right] \ge \Omega(1)\cdot M$. Instantiating <Ref> gives

\begin{align*}
&\Pr\left[\sum_{q=1}^dR_q \ge \Omega(1)\cdot M\right] \ge \Omega(1) \\
\implies \qquad &\Pr\left[\|z_i-z_j\|_1 \ge \Omega(1)\cdot M\right] \ge \Omega(1).
\end{align*}


t,a,|\hat{\mu}_{I,a}(t)-\mu_{I,a}|<2\sqrt{\frac{1}{D_{a}(t)}\log\left(\frac{2n\log(2t)}{\delta}\right)}\right\\},$

then $\Pr\\{\mathcal{E}^{c}_{2}\\}\leq\delta$.

Consider the observational confidence bound. First, if
$a\notin\mathcal{A}_{known}$, $[L_{O,a}^{t},U_{O,a}^{t}]=(-\infty,\infty)$ and
then the $\hat{\mu}_{O,a}(t)\in[L_{O,a}^{t},U_{O,a}^{t}]$. Now we consider
that if $a=do(X=x)\in\mathcal{A}_{known}$ and the parent of $X$ is
$\boldsymbol{P}$. By Hoeffding’s inequality, with probability at least
$1-\delta/16n^{2}Z_{a}t^{3}$, for $a=do(X=x)$,

$\displaystyle|r_{a,\boldsymbol{z}}(t)-P(Y=1\mid
X=x,\boldsymbol{P}=\boldsymbol{z})|$
$\displaystyle>\sqrt{\frac{1}{2T_{a,\boldsymbol{z}}(t)}\log\frac{16n^{2}Z_{a}t^{3}}{\delta}}$
(41)

Also, by Chernoff’s inequality, since $q_{a}\leq
P(\boldsymbol{P}=\boldsymbol{z})$ for all
$\boldsymbol{z}\in\\{0,1\\}^{|\boldsymbol{P}|}$, when
$t\geq\frac{6}{q_{a}}\log\left(\frac{16n^{2}Z_{a}t^{3}}{\delta}\right)$ with
probability at least $1-\delta/16n^{2}Z_{a}t^{3}$ we will have

$\displaystyle|p_{a,\boldsymbol{z}}(t)-P(\boldsymbol{P}=\boldsymbol{z})|$
$\displaystyle>\sqrt{\frac{6P(\boldsymbol{P}=z)}{t}\log\frac{16n^{2}Z_{a}t^{3}}{\delta}},$
(42)

then

$\displaystyle\hat{\mu}_{O,a}$
$\displaystyle=\sum_{\boldsymbol{z}}r_{a,\boldsymbol{z}}(t)\cdot
p_{a,\boldsymbol{z}}(t)$ $\displaystyle\leq\sum_{\boldsymbol{z}}P(Y=1\mid
X=x,\boldsymbol{P}=\boldsymbol{z})p_{a,\boldsymbol{z}}(t)+\sum_{\boldsymbol{z}}p_{a,\boldsymbol{z}}(t)\sqrt{\frac{1}{2T_{a,\boldsymbol{z}}(t)}\log\frac{16n^{2}Z_{a}t^{3}}{\delta}}$
$\displaystyle\leq\sum_{\boldsymbol{z}}P(Y=1\mid
X=x,\boldsymbol{P}=\boldsymbol{z})p_{a,\boldsymbol{z}}(t)+\sqrt{\frac{1}{2T_{a}(t)}\log\frac{16n^{2}Z_{a}t^{3}}{\delta}}$
$\displaystyle\leq\sum_{\boldsymbol{z}}P(Y=1\mid
X=x,\boldsymbol{P}=\boldsymbol{z})P(\boldsymbol{P}=\boldsymbol{z})+\sum_{\boldsymbol{z}}\sqrt{\frac{6P(\boldsymbol{P}=\boldsymbol{z})}{t}\log\frac{16n^{2}Z_{a}t^{3}}{\delta}}+$
$\displaystyle\sqrt{\frac{1}{2T_{a}(t)}\log\frac{16n^{2}Z_{a}t^{3}}{\delta}}$
$\displaystyle\leq\mu_{a}+\sqrt{\frac{6Z}{t}\log\frac{16n^{2}Z_{a}t^{3}}{\delta}}+\sqrt{\frac{1}{2T_{a}(t)}\log\frac{16n^{2}Z_{a}t^{3}}{\delta}}$
$\displaystyle\leq\mu_{a}+\sqrt{\frac{6}{T_{a}(t)}\log\frac{16n^{2}Z_{a}t^{3}}{\delta}}+\sqrt{\frac{1}{2T_{a}(t)}\log\frac{16n^{2}Z_{a}t^{3}}{\delta}},$
$\displaystyle=\mu_{a}+\sqrt{\frac{8}{T_{a}(t)}\log\frac{16n^{2}Z_{a}t^{3}}{\delta}}.$

Also, if $t\leq\frac{6}{q_{a}}\log\frac{16n^{2}Z_{a}t^{3}}{\delta}$, first by
Chernoff inequality, set
$Q=\frac{6}{q_{a}}\log\frac{16n^{2}Z_{a}t^{3}}{\delta}$, then with probability
at least $1-\delta/16n^{2}Z_{a}t^{3}$, we have

$\displaystyle\hat{q}_{a}(Q)\leq 2q_{a}.$ (43)

by $\mathcal{E}_{1}(Q)$.

$\displaystyle T_{a}(t)\leq T_{a}(Q)\leq\hat{q}_{a}(Q)\cdot Q\leq 2q_{a}\cdot
Q=\frac{12}{q_{a}}\log\frac{16n^{2}Z_{a}t^{3}}{\delta}.$

Then $\sqrt{\frac{12}{T_{a}(t)}\log\frac{16n^{2}Z_{a}t^{3}}{\delta}}\geq 1$
and the inequality

$\displaystyle|\hat{\mu}_{O,a}(t)-\mu_{O,a}|\leq\sqrt{\frac{12}{T_{a}(t)}\log\frac{16n^{2}Z_{a}t^{3}}{\delta}}$

also holds. Thus we define the event

$\displaystyle\mathcal{E}_{3}=\left\\{\forall
a,t,|\hat{\mu}_{O,a}(t)-\mu_{O,a}|\leq\sqrt{\frac{12}{T_{a}(t)}\log\frac{16n^{2}Z_{a}t^{3}}{\delta}}\right\\}$

then by taking the union bound of (41), (42) and (43),

$\displaystyle\Pr\\{\mathcal{E}^{c}_{3}\\}$
$\displaystyle\leq\sum_{t=1}^{\infty}\sum_{a\in\boldsymbol{A}}\sum_{\boldsymbol{z}}3\cdot\frac{\delta}{16n^{2}Z_{a}t^{3}}$
$\displaystyle\leq\sum_{t=1}^{\infty}\frac{\delta}{4t^{3}}$
$\displaystyle\leq\delta.$

Now we consider how to bound our sample complexity based on events
$\mathcal{E}_{1},\mathcal{E}_{2}$ and $\mathcal{E}_{3}$. First, we provide the
following lemma in [36]:

######  Lemma 10 (Lemma 6 in [36]).

Under the event $\mathcal{E}_{1},\mathcal{E}_{2}$ and $\mathcal{E}_{3}$, at
round $t$, if we have

$\beta_{a_{h}^{t}}(t)\leq\frac{\max\\{\Delta_{a_{h}^{t}},\varepsilon/2\\}}{4},\beta_{a_{l}^{t}}(t)\leq\frac{\max\\{\Delta_{a_{l}^{t}},\varepsilon/2\\}}{4},$

where $a_{h}^{t},a_{l}^{t}$ are the actions performed by algorithm at round
$t$. then the algorithm will stop at round $t+1$.

Now assume the algorithm does not terminate at
$T_{1}=192H\log(nZT_{1}^{3}/\delta)$, where $Z=\max_{a}Z_{a}$. For $a\in S$,
$D_{a}(t)$. Note that $H\geq H_{m_{\varepsilon,\Delta}}$. Thus at round
$T_{1}$, for action $a$ with
$q_{a}\geq\frac{1}{H_{m_{\varepsilon,\Delta}}\cdot\max\\{\Delta_{a},\varepsilon/2\\}^{2}}\geq\frac{192}{T_{1}}\log\frac{16nZ_{a}T_{1}^{3}}{\delta}$,
if $a\in\mathcal{A}_{known}$, then under event $\mathcal{E}_{1}(T_{1})$, we
have

$\displaystyle\hat{q}_{a}(T_{1})\geq
q_{a}-\sqrt{\frac{6q_{a}}{T_{1}}\log\frac{16nZ_{a}T_{1}^{3}}{\delta}}\geq\frac{q_{a}}{2}.$

Then

$\displaystyle\beta_{a}(T_{1})\leq\beta_{O,a}(T_{1})=\sqrt{\frac{12}{T_{a}(T_{1})}\log\frac{16n^{2}Z_{a}t^{3}}{\delta}}\leq\sqrt{\frac{12q_{a}}{2T_{1}}}\leq\frac{\max\\{\Delta_{a},\varepsilon/2\\}^{2}}{4}.$

Now we prove that if $D_{a}(t)$ is large for some $a$, then
$a\in\mathcal{A}_{known}$.

######  Lemma 11.

With probability at least $1-\delta$, denote
$C_{a}=\frac{1}{c_{a}^{2}}+\sum_{e:X^{\prime}\to X}\frac{1}{c_{e}^{2}}$. If
$D_{a}(t)\geq 32C_{a}\log(4n^{2}t^{2}/\delta)$, $a\in\mathcal{A}_{known}$.

###### Proof.

If $D_{a}(t)\geq 8C_{a}\log t$, we have called sub-procedure RECOVER-EDGE$(a)$
for $D_{a}(t)$ times. Then, for each edge $e:X\to X^{\prime}$, we will perform
intervention $do(X=1)$, $do(X=0)$ for at least $D_{a}(t)$ times and observe
the empirical difference $|\hat{P}(X^{\prime}\mid
do(X=1))-\hat{P}(X^{\prime}\mid do(X=0))|$. By Hoeffding’s inequality and
union bound on all time $t$ and the $\binom{n-1}{2}$ ordered-pair
$(X^{\prime},X)$, with probability at least $1-\delta$, for all $t\in[T]$ and
all $X^{\prime},X$ we have

$\displaystyle|\hat{P}(X^{\prime}\mid do(X=1))-P(X^{\prime}\mid do(X=1))|$
$\displaystyle\leq\sqrt{\frac{2}{D_{a}(t)}\log\frac{4n^{2}t^{2}}{\delta}}$
$\displaystyle|\hat{P}(X^{\prime}\mid do(X=0)-P(X^{\prime}\mid do(X=0))|$
$\displaystyle\leq\sqrt{\frac{2}{D_{a}(t)}\log\frac{4n^{2}t^{2}}{\delta}}$

Then for the confidence bounds

$\displaystyle[L_{X^{\prime}\mid do(X=1)},U_{X^{\prime}\mid do(X=1)}]$
$\displaystyle=\left[\hat{P}(X^{\prime}\mid
do(X=1))-\sqrt{\frac{2}{D_{a}(t)}\log\frac{4n^{2}t^{2}}{\delta}},\hat{P}(X^{\prime}\mid
do(X=1))+\sqrt{\frac{2}{D_{a}(t)}\log\frac{4n^{2}t^{2}}{\delta}}\right]$
$\displaystyle[L_{X^{\prime}\mid do(X=0)},U_{X^{\prime}\mid do(X=0)}]$
$\displaystyle=\left[\hat{P}(X^{\prime}\mid
do(X=0))-\sqrt{\frac{2}{D_{a}(t)}\log\frac{4n^{2}t^{2}}{\delta}},\hat{P}(X^{\prime}\mid
do(X=0))+\sqrt{\frac{2}{D_{a}(t)}\log\frac{4n^{2}t^{2}}{\delta}}\right]$

the intersection

$\displaystyle[L_{X^{\prime}\mid do(X=1)},U_{X^{\prime}\mid
do(X=1)}]\cap[L_{X^{\prime}\mid do(X=0)},U_{X^{\prime}\mid
do(X=0)}]=\emptyset$

since

$\displaystyle|\hat{P}(X^{\prime}\mid do(X=1)-\hat{P}(X^{\prime}\mid
do(X=0))|$ $\displaystyle\geq$ $\displaystyle|P(X^{\prime}\mid
do(X=1)-P(X^{\prime}\mid do(X=0))|-|P(X^{\prime}\mid
do(X=1)-\hat{P}(X^{\prime}\mid do(X=1))|$ $\displaystyle\ \ \ \
-|P(X^{\prime}\mid do(X=0)-\hat{P}(X^{\prime}\mid do(X=0))|$
$\displaystyle\geq$ $\displaystyle
c_{a}-2\sqrt{\frac{2}{D_{a}(t)}\log\frac{4n^{2}t^{2}}{\delta}}$
$\displaystyle\geq$ $\displaystyle
2\sqrt{\frac{2}{D_{a}(t)}\log\frac{4n^{2}t^{2}}{\delta}}.$

where we use $D_{a}(t)\geq\frac{1}{c_{a}^{2}}\log\frac{4n^{2}t^{2}}{\delta}$.
Then the edge’s direction will be identified correctly.

Consider the edge $e:X^{\prime}\to X$, then if we sample $do(X^{\prime}=1)$
and $do(X^{\prime}=0)$ for $\frac{1}{c_{e}^{2}}\log\frac{4n^{2}t^{2}}{\delta}$
times within sub-procedures RECOVER-EDGE$(a)$, similarly we will identify the
edge $X^{\prime}\to X$. Then because the RECOVER-EDGE$(a)$ will perform
intervention $do(X^{\prime}=0)$ and $do(X^{\prime}=1)$ for the $X^{\prime}$
that the direction of $(X^{\prime},X)$ has not been discovered each time,
after $\sum_{e:X^{\prime}\to
X}\frac{1}{c_{e}^{2}}\log\frac{4n^{2}t^{2}}{\delta}$. ∎

Then we define

$\displaystyle\mathcal{E}_{4}=\\{\mbox{Lemma~{}\ref{lemma:identify} holds}\\}$

Then $\Pr\\{\mathcal{E}_{4}^{c}\\}\leq\delta$. Also, under the event
$\mathcal{E}_{2}$, the following lemma shows that if $D_{a}(t)$ is really
large, we can estimate the $\mu_{a}$ accurately.

######  Lemma 12.

Under event $\mathcal{E}_{2}$, if
$D_{a}(t)\geq\frac{64}{\max\\{\Delta_{a},\varepsilon/2\\}^{2}}\log\frac{16n^{2}Z_{a}t^{3}}{\delta}$,
then

$\displaystyle\beta_{a}(T_{1})\leq\frac{\max\\{\Delta_{a},\varepsilon/2\\}^{2}}{4}.$

###### Proof.

In fact,

$\displaystyle\beta_{a}(t)\leq\beta_{I,a}(t)=2\sqrt{\frac{1}{D_{a}(t)}\log\left(\frac{2n\log(2t)}{\delta}\right)}\leq
2\sqrt{\frac{1}{D_{a}(t)}\log\frac{16n^{2}Z_{a}t^{3}}{\delta}}\leq\frac{\max\\{\Delta_{a},\varepsilon/2\\}^{2}}{4}.$

∎

Now we turn to our main result. From the Lemma 10, at least one arm $a$ with
$\beta_{a}(t)\geq\frac{\max\\{\Delta_{a},\varepsilon/2\\}}{4}$ will be
performed an intervention at each round $t\geq T_{1}$. Under the event
$\mathcal{E}_{1},\mathcal{E}_{2},\mathcal{E}_{3}$ and $\mathcal{E}_{4}$, these
interventions will only performed in two types of action $a$:

  * •

$q_{a}\leq\frac{1}{H_{m_{\varepsilon,\Delta}}\cdot\max\\{\Delta_{a},\varepsilon/2\\}^{2}}$
and
$D_{a}(t)\leq\frac{64}{\max\\{\Delta_{a},\varepsilon/2\\}^{2}}\log\frac{16n^{2}Z_{a}t^{3}}{\delta}$.

  * •

$D_{a}(t)\leq\min\\{MC_{a}\log(t),\frac{64}{\max\\{\Delta_{a},\varepsilon/2\\}^{2}}\log\frac{16n^{2}Z_{a}t^{3}}{\delta}\\}$.

Note that
$q_{a}\leq\frac{1}{H_{m_{\varepsilon,\Delta}}\cdot\max\\{\Delta_{a},\varepsilon/2\\}^{2}}$
implies that $a\in S$, then after at most $T_{2}$ rounds, where

$\displaystyle T_{2}=64\left(\sum_{a\in
S}\frac{1}{\max\\{\Delta_{a},\varepsilon/2\\}^{2}}+\sum_{a\notin
S}\min\left\\{\frac{1}{\max\\{\Delta_{a},\varepsilon/2\\}^{2}},\frac{1}{c_{a}^{2}}+\sum_{e:X^{\prime}\to
X}\frac{1}{c_{e}^{2}}\right\\}\right)\log\frac{16n^{2}ZT_{2}^{3}}{\delta}=64H\log\frac{16n^{2}ZT_{2}^{3}}{\delta}$

the algorithm should terminates. The fist term is the summation of all actions
in $S$, and the second term is for the second type of actions, which
$D_{a}(t)\leq\min\\{MC_{a}\log(t),\frac{64}{\max\\{\Delta_{a},\varepsilon/2\\}^{2}}\log\frac{16n^{2}Z_{a}t^{3}}{\delta}\\}.$
Denote $T=T_{1}+T_{2}$, then

$\displaystyle T=T_{1}+T_{2}\leq 256H\log\frac{16n^{2}ZT^{3}}{\delta}\leq
768H\log\frac{16nZT}{\delta}$

Then by the Lemma 13, with probability at least $1-4\delta$, the sample
complexity has the upper bound

$\displaystyle T=O\left(H\log\left(\frac{nZH}{\delta}\right)\right)$

Replace $\delta$ to $\delta/4$, we derive the sample complexity in the Theorem
6. The correctness of algorithm can be derived by LUCB1 algorithm. We provide
a short argument here. Because the stopping rule is
$\hat{\mu}_{a_{l}^{t}}^{t}+\beta_{a_{l}^{t}}(t)\leq\hat{\mu}_{a_{h}^{t}}^{t}-\beta_{a_{h}^{t}}(t)+\varepsilon$,
if $a^{*}\neq a_{h}^{t}$, we have

$\displaystyle\mu_{a_{h}^{t}}+\varepsilon\geq\hat{\mu}_{a_{h}^{t}}-\beta_{a_{h}^{t}}(t)+\varepsilon\geq\hat{\mu}_{a_{l}^{t}}+\beta_{a_{l}^{t}}(t)\geq\hat{\mu}_{a^{*}}+\beta_{a^{*}}(t)\geq\mu_{a^{*}}.$

Hence either $a^{*}=a_{h}^{t}$ or $a_{h}^{t}$ is $\varepsilon$-optimal arm.

###  E.3 Proof of Lemma 10

For completeness, we provide the proof in [36].

###### Proof.

If the optimal arm $a^{*}=a_{h}^{t}$,

$\displaystyle\hat{\mu}_{a_{l}^{t}}+\beta_{a_{l}^{t}}(t)$
$\displaystyle\leq\mu_{a_{l}^{t}}+2\beta_{a_{l}^{t}}(t)$
$\displaystyle\leq\mu_{a_{l}^{t}}+\frac{\max\\{\Delta_{a_{l}^{t}},\varepsilon/2\\}}{2}$
$\displaystyle\leq\mu_{a_{h}^{t}}-\Delta_{a_{l}^{t}}+\frac{\max\\{\Delta_{a_{l}^{t}},\varepsilon/2\\}}{2}$
$\displaystyle\leq\hat{\mu}_{a_{h}^{t}}+\beta_{a^{*}}(T_{a^{*}}(t))-\Delta_{a_{l}^{t}}+\frac{\max\\{\Delta_{a_{l}^{t}},\varepsilon/2\\}}{2}$
$\displaystyle\leq\hat{\mu}_{a_{h}^{t}}-\beta_{a^{*}}(T_{a^{*}}(t))+\frac{\max\\{\Delta_{a^{*}},\varepsilon/2\\}+\max\\{\Delta_{a_{l}^{t}},\varepsilon/2\\}}{2}-\Delta_{a_{l}^{t}}$
$\displaystyle\leq\hat{\mu}_{a_{h}^{t}}-\beta_{a^{*}}(T_{a^{*}}(t))+\frac{\Delta_{a^{*}}+\varepsilon/2+\Delta_{a_{l}^{t}}+\varepsilon/2}{2}-\Delta_{a_{l}^{t}}$
$\displaystyle\leq\hat{\mu}_{a_{h}^{t}}-\beta_{a^{*}}(T_{a^{*}}(t))+\varepsilon.$

If optimal arm $a^{*}\neq a_{h}^{t}$, and the algorithm doesn’t stop at round
$t+1$, then we prove $a^{*}\neq a_{l}^{t}$. Otherwise, assume
$a^{*}=a_{l}^{t}$

$\displaystyle\hat{\mu}_{a_{h}^{t}}^{t}$
$\displaystyle\leq\mu_{a_{h}^{t}}^{t}+\frac{\max\\{\Delta_{a_{h}^{t}},\varepsilon/2\\}}{4}$
(44)
$\displaystyle=\mu_{a_{l}^{t}}^{t}-\Delta_{a_{h}^{t}}+\frac{\max\\{\Delta_{a_{h}^{t}},\varepsilon/2\\}}{4}$
(45)
$\displaystyle\leq\mu_{a_{l}^{t}}^{t}-\frac{3\Delta_{a_{h}^{t}}}{4}+\varepsilon/4$
(46)
$\displaystyle\leq\hat{\mu}_{a_{l}^{t}}^{t}+\frac{\max\\{\Delta_{a^{*}},\varepsilon/2\\}}{4}-\frac{3\Delta_{a_{h}^{t}}}{4}+\varepsilon/4$
(47)
$\displaystyle\leq\hat{\mu}_{a_{l}^{t}}^{t}+\varepsilon/2-\frac{\Delta_{a_{h}^{t}}}{2}.$
(48)

From the definition of $a_{h}^{t}$, we know
$\varepsilon>\Delta_{a_{h}^{t}}\geq\Delta_{a^{*}},\beta_{a_{h}^{t}}(t)\leq\varepsilon/4,\beta_{a_{l}^{t}}(t)\leq\varepsilon/4$.
Then
$\hat{\mu}_{a_{l}^{t}}^{t}+\beta_{a_{l}^{t}}(t)+\beta_{a_{h}^{t}}(t)\leq\hat{\mu}_{a_{l}^{t}}+\varepsilon/2\leq\hat{\mu}_{a_{h}^{t}}^{t}+\varepsilon,$
which means the algorithm stops at round $t+1$.

Now we can assume $a^{*}\neq a_{l}^{t},a^{*}\neq a_{h}^{t}$. Then

$\displaystyle\mu_{a_{l}^{t}}+2\beta_{a_{l}^{t}}(t)\geq\hat{\mu}_{a_{l}^{t}}+\beta_{a_{l}^{t}}(t)\geq\hat{\mu}_{a^{*}}+\beta_{a^{*}}(T_{a^{*}}(t))\geq\mu_{a^{*}}=\mu_{a_{l}^{t}}+\Delta_{a_{l}^{t}}.$
(49)

Thus

$\displaystyle\Delta_{a_{l}^{t}}\leq
2\beta_{a_{l}^{t}}(t)\leq\frac{\max\\{\Delta_{a_{l}^{t}},\varepsilon/2\\}}{2},$
(50)

which leads to
$\Delta_{a_{l}^{t}}\leq\varepsilon/2,\beta_{a_{l}^{t}}(t)\leq\varepsilon/8$.
Since

Also,

$\displaystyle\mu_{a_{h}^{t}}+\beta_{a_{h}^{t}}(t)\geq\hat{\mu}_{a_{h}^{t}}\geq\hat{\mu}_{a_{l}^{t}}\geq\mu_{a^{*}}-\beta_{a_{l}^{t}}(t)=\mu_{a_{h}^{t}}+\Delta_{a_{h}^{t}}-\beta_{a_{l}^{t}}(t),$
(51)

which leads to

$\displaystyle\frac{\max\\{\Delta_{a_{h}^{t}},\varepsilon/2\\}}{4}\geq\Delta_{a_{h}^{t}}-\varepsilon/8,$
(52)

and
$\Delta_{a_{h}^{t}}\leq\varepsilon/2,\beta_{a_{h}^{t}}(t)\leq\varepsilon/8.$
Hence
$\hat{\mu}_{a_{l}^{t}}^{t}+\beta_{a_{l}^{t}}(t)+\beta_{a_{h}^{t}}(t)\leq\hat{\mu}_{a_{l}^{t}}+\varepsilon/2\leq\hat{\mu}_{a_{h}^{t}}^{t}+\varepsilon,$
which means the algorithm stops at round $t+1$. ∎

###  E.4 Proof of Theorem 7

###### Proof.

We construct $n-1$ graphs with the same distribution $P(\boldsymbol{X},Y)$ but
different causal graph. Indeed, We construct the bandit instances
$\\{\xi_{i}\\}_{2\leq i\leq n}$ as follows. For instance $\xi_{2}$, the graph
structure contains edge $X_{1}\to Y,X_{2}\to X_{1},X_{1}\to X_{i}(3\leq i\leq
n)$ and $X_{2}\to X_{i}(3\leq i\leq n)$. For instances $\xi_{i}(3\leq i\leq
n)$, we change $X_{1}\to X_{i}$ to $X_{i}\to X_{1}$. The graph structure are
shown in the Figure 3 and Figure 4.

The observational distribution for all instance is:

$\displaystyle P(\boldsymbol{X},Y)=p_{1}p_{2}\ldots p_{n},$ (53)

where

$\displaystyle p_{1}$ $\displaystyle=0.5,$ (54) $\displaystyle\ p_{2}$
$\displaystyle=\left\\{\begin{array}[]{cc}0.5+\varepsilon&x_{2}=x_{1}\\\
0.5-\varepsilon&x_{2}\neq x_{1}\end{array}\right.$ (57) $\displaystyle\ \
p_{i}$
$\displaystyle=\left\\{\begin{array}[]{cc}0.5+4\varepsilon&x_{i}=x_{1}\\\
0.5-4\varepsilon&x_{i}\neq x_{1}\end{array}\right..$ (60)

Figure 3: Causal Bandits Instance $\tau_{2}$ Figure 4: Causal Bandits Instance
$\tau_{i}(i=3)$

It is easy to check that
$\sum_{\boldsymbol{x},y}P(\boldsymbol{X}=\boldsymbol{x},Y=y)=1$ and
$P(X_{i}=1)=0.5$. The action set is $do(),do(X_{i}=1),do(X_{i}=0)$ where
$2\leq i\leq n$, which means the action set does not contain $do(X_{1}=x)$ for
$x=0,1$.

Now in $\xi_{2}$, we consider $P(Y=1\mid do(X_{2}=1))$. Actually, it is easy
to show that $P(Y=1\mid do(X_{2}=1))=P(X_{1}=1\mid
do(X_{2}=1))=0.5+\varepsilon$. Similarly, $P(Y=1\mid
do(X_{2}=0))=0.5-\varepsilon$. For other actions, $P(Y=1\mid a)=P(X_{1}=1\mid
a)=0.5$ since other actions $a$ will not influence the value of $X_{1}$.

Now consider instance $\xi_{i}$ for $3\leq i\leq n$. For action $do()$ and
$do(X_{j}=x)$ with $j\neq 2,i$, it will not influence the value of $X_{1}$ and
then $P(Y=1\mid a)=0.5$. Now consider action $a=do(X_{2}=1)$, we have

$\displaystyle P(Y=1\mid do(X_{2}=1))$ $\displaystyle=P(X_{1}=1\mid
do(X_{2}=1))$ $\displaystyle=P(X_{1}=1\mid X_{2}=1)=0.5+\varepsilon.$

Similarly, $P(Y=1\mid do(X_{2}=0))=0.5-\varepsilon$.

Now we calculate $P(Y=1\mid do(X_{i}=1))$ in instance $\xi_{i}$. In fact,
denote $q=0.5+4\varepsilon$ and by do-calculus,

$\displaystyle P(X_{1}=1\mid do(X_{i}=1))$
$\displaystyle=\sum_{x=0,1}P(X_{1}=1\mid X_{i}=1,X_{2}=x)P(X_{2}=x)$
$\displaystyle=0.5(P(X_{1}=1\mid X_{i}=1,X_{2}=0)+P(X_{1}=1\mid
X_{i}=1,X_{2}=1)$
$\displaystyle=0.5\left(\frac{P(X_{1}=1,X_{i}=1,X_{2}=0)}{P(X_{i}=1,X_{2}=0)}+\frac{P(X_{1}=1,X_{i}=1,X_{2}=1)}{P(X_{i}=1,X_{2}=1)}\right)$
$\displaystyle=0.5\left(\frac{(0.5+4\varepsilon)(0.5-\varepsilon)}{(0.5+4\varepsilon)(0.5-\varepsilon)+(0.5-4\varepsilon)(0.5+\varepsilon)}+\frac{(0.5+4\varepsilon)(0.5+\varepsilon)}{(0.5+4\varepsilon)(0.5+\varepsilon)+(0.5-4\varepsilon)(0.5-\varepsilon)}\right)$
$\displaystyle=0.5\left(\frac{q(0.5-\varepsilon)}{q(0.5-\varepsilon)+(1-q)(0.5+\varepsilon)}+\frac{q(0.5+\varepsilon)}{q(0.5+\varepsilon)+(1-q)(0.5-\varepsilon)}\right)$
$\displaystyle=0.5\left(\frac{q(0.5-\varepsilon)}{0.5-(2q-1)\varepsilon}+\frac{q(0.5+\varepsilon)}{0.5+(2q-1)\varepsilon}\right)$
$\displaystyle=q\left(\frac{0.5^{2}-(2q-1)\varepsilon^{2}}{0.5^{2}-(2q-1)^{2}\varepsilon^{2}}\right)\leq
q=0.5+4\varepsilon.$

Also, we prove that

$\displaystyle
q\left(\frac{0.5^{2}-(2q-1)\varepsilon^{2}}{0.5^{2}-(2q-1)^{2}\varepsilon^{2}}\right)\geq
0.5+2\varepsilon.$

Actually, this inequality is equal to

$\displaystyle(0.5+4\varepsilon)(0.5^{2}-8\varepsilon^{3})$
$\displaystyle\geq(0.5+2\varepsilon)(0.5^{2}-8\varepsilon^{4})$
$\displaystyle\iff 1$ $\displaystyle\geq
56\varepsilon^{3}+8\varepsilon^{2}-32\varepsilon^{4}.$

When $\varepsilon$ is small enough, this inequality holds. In summary, we have

$\displaystyle P(X_{1}=1\mid
do(X_{i}=1))\in[0.5+2\varepsilon,0.5+4\varepsilon].$

Similarly, we can get

$\displaystyle P(X_{1}=1\mid do(X_{i}=0))$ $\displaystyle=0.5(P(X_{1}=1\mid
X_{i}=0,X_{2}=1)+P(X_{1}=1\mid X_{i}=0,X_{2}=0))$
$\displaystyle=(1-q)\left(\frac{0.5^{2}-(1-2q)\varepsilon^{2}}{0.5^{2}-(1-2q)^{2}\varepsilon^{2}}\right)\in[0.5-4\varepsilon,0.5].$

Now in instance $\xi_{2}$, the output action should be $do(X_{2}=1)$, while in
instance $\xi_{i}$, the output action should be $do(X_{i}=1)$.

Now by Pinkser’s inequality, for an policy $\pi$, we have

$\displaystyle 2\delta\geq
P_{\xi_{2}}(a^{o}=do(X_{i}=1))+P_{\xi_{i}}(a^{o}\neq
do(X_{i}=1))\geq\exp(-\mbox{KL}(\xi_{2}^{\pi},\xi_{i}^{\pi})).$

Also, assume the stopping time as $\tau$ for the environment $\mathcal{E}$,
the KL divergence can be rewritten as

$\displaystyle\mbox{KL}(\xi_{2}^{\pi},\xi_{i}^{\pi})$
$\displaystyle=\mathbb{E}_{A_{t}\sim\xi_{2}^{\pi}}\left[\sum_{t=1}^{\tau}\mbox{KL}(P_{\xi_{2}}(\boldsymbol{X}_{t},Y_{t}\mid
A_{t}),P_{\xi_{i}}(\boldsymbol{X}_{t},Y_{t}\mid A_{t}))\right]$ (61)
$\displaystyle=\mathbb{E}_{\xi_{2}^{\pi}}\left[\sum_{t=1}^{\tau}P_{\xi_{2}}(\boldsymbol{X}_{t},Y_{t}\mid
A_{t})\left(\log\frac{P_{\xi_{2}}(\boldsymbol{X}_{t},Y_{t}\mid
A_{t})}{P_{\xi_{i}}(\boldsymbol{X}_{t},Y_{t}\mid A_{t})}\right)\right]$ (62)
$\displaystyle=\mathbb{E}_{\xi_{2}^{\pi}}\left[\sum_{t=1}^{\tau}P_{\xi_{2}}(X_{t,i},X_{t,1}\mid
A_{t})\left(\log\frac{P_{\xi_{2}}(X_{t,i},X_{t,1}\mid
A_{t})}{P_{\xi_{i}}(X_{t,i},X_{t,1}\mid A_{t})}\right)\right]$ (63)

where the last equation is derived as follows:

$\displaystyle\frac{P_{\xi_{2}}(\boldsymbol{X}_{t},Y_{t}\mid
A_{t})}{P_{\xi_{i}}(\boldsymbol{X}_{t},Y_{t}\mid
A_{t})}=\frac{P_{\xi_{2}}(X_{t,i},X_{t,1}\mid A_{t})\cdot
P_{\xi_{2}}(\bar{\boldsymbol{X}}_{t,i},Y_{t}\mid
X_{t,i},X_{t,1},A_{t})}{P_{\xi_{i}}(X_{t,i},X_{t,1}\mid A_{t})\cdot
P_{\xi_{i}}(\bar{\boldsymbol{X}}_{t,i},Y_{t}\mid X_{t,i},X_{t,1},A_{t})}$

where
$\bar{\boldsymbol{X}}_{t,i}=\boldsymbol{X}_{t}\setminus\\{X_{t,i},X_{t,1}\\}$.
Now since $\bar{\boldsymbol{X}}_{t,i}$ is only decided by $X_{1},X_{2}$ and
$X_{2}$ is only decided by $A_{t}$, then

$P_{\xi_{2}}(\bar{\boldsymbol{X}}_{t,i},Y_{t}\mid
X_{t,i},X_{t,1},A_{t})=P_{\xi_{i}}(\bar{\boldsymbol{X}}_{t,i},Y_{t}\mid
X_{t,i},X_{t,1},A_{t})$

and then

$\displaystyle\frac{P_{\xi_{2}}(\boldsymbol{X}_{t},Y_{t}\mid
A_{t})}{P_{\xi_{i}}(\boldsymbol{X}_{t},Y_{t}\mid
A_{t})}=\frac{P_{\xi_{2}}(X_{t,i},X_{t,1}\mid
A_{t})}{P_{\xi_{i}}(X_{t,i},X_{t,1}\mid A_{t})}.$

Note that only when $A_{t}=do(X_{i}=1),do(X_{i}=0)$,
$P_{\xi_{2}}(X_{t,i},X_{t,1}\mid A_{t})\neq P_{\xi_{i}}(X_{t,i},X_{t,1}\mid
A_{t})$. Then the equation (63) can be further calculated as

(63)
$\displaystyle=\sum_{x=0,1}\mathbb{E}_{\xi_{2}^{\pi}}\left[\sum_{t=1}^{\tau}\mathbb{I}\\{A_{t}=do(X_{i}=x)\\}\right]\cdot
P_{\xi_{2}}(X_{t,i},X_{t,1}\mid
do(X_{i}=x))\left(\log\frac{P_{\xi_{2}}(X_{t,i},X_{t,1}\mid
do(X_{i}=x))}{P_{\xi_{i}}(X_{t,i},X_{t,1}\mid do(X_{i}=x))}\right)$
$\displaystyle=\sum_{x=0,1}\mathbb{E}_{\xi_{2}^{\pi}}\left[\sum_{t=1}^{\tau}\mathbb{I}\\{A_{t}=do(X_{i}=x)\\}\right]\cdot
P_{\xi_{2}}(X_{t,1}\mid do(X_{i}=x))\left(\log\frac{P_{\xi_{2}}(X_{t,1}\mid
do(X_{i}=x))}{P_{\xi_{i}}(X_{t,1}\mid do(X_{i}=x))}\right)$
$\displaystyle\leq\sum_{x=0,1}\mathbb{E}_{\xi_{2}^{\pi}}\left[\sum_{t=1}^{\tau}\mathbb{I}\\{A_{t}=do(X_{i}=x)\\}\right]\left(0.5\cdot\left(\log\frac{0.5}{0.5+4\varepsilon}+\log\frac{0.5}{0.5-4\varepsilon}\right)\right)$
$\displaystyle\leq\sum_{x=0,1}\mathbb{E}_{\xi_{2}^{\pi}}\left[\sum_{t=1}^{\tau}\mathbb{I}\\{A_{t}=do(X_{i}=x)\\}\right]96\varepsilon^{2}$
$\displaystyle=96\varepsilon^{2}\cdot\mathbb{E}_{\xi_{2}^{\pi}}[N(do(X_{i}=1))+N(do(X_{i}=0))].$

where the $\mathbb{E}_{\xi_{2}^{\pi}}N(a)$ represents that the number of times
taking action $a$ for policy $\pi$ under the instance $\xi_{2}$. Now we have

$\displaystyle\mathbb{E}_{\xi_{2}^{\pi}}[N(do(X_{i}=1))+N(do(X_{i}=0))]\geq\frac{\mbox{KL}(\xi_{2}^{\pi},\xi_{i}^{\pi})}{96\varepsilon^{2}}\geq\frac{1}{96\varepsilon^{2}}\log\frac{1}{2\delta}.$

Hence the stopping time $\tau$ under policy $\pi$ can be lower bounded by

$\displaystyle\mathbb{E}_{\xi_{2}^{\pi}}[\tau]\geq\sum_{i=3}^{n}\mathbb{E}_{\xi_{2}^{\pi}}[N(do(X_{i}=1))+N(do(X_{i}=0))]\geq\frac{n-2}{96\varepsilon^{2}}\log\frac{1}{2\delta}=O\left(\frac{n}{\varepsilon^{2}}\log\frac{1}{\delta}\right).$

∎

###  E.5 Technical Lemma

######  Lemma 13.

If $T=CH\log\frac{dT}{\delta}$ for some constant $C$ and parameter $d$ such
that $d\geq e\delta$, then $T=O(H\log\frac{Hd}{\delta})$.

###### Proof.

Let $f(x)=\frac{x}{\log(dx/\delta)}$, then for $x\geq 1$

$\displaystyle f^{\prime}(x)=\frac{\log(dx/\delta)-1}{\log^{2}dx/\delta}\geq
0$

because $dx/\delta>e$. Then $f(x)$ is non-decreasing for $x\geq 1$.

To prove $T=O(H\log\frac{Hd}{\delta})$, we only need to show that $f(T)\leq
f(C^{\prime}H\log\frac{Hd}{\delta})$ for some constant $C^{\prime}$. Since

$\displaystyle\log\frac{C^{\prime}Hd\log\frac{Hd}{\delta}}{\delta}$
$\displaystyle=\log\frac{C^{\prime}Hd}{\delta}+\log\log\frac{Hd}{\delta}$

we only need to prove

$\displaystyle
f(C^{\prime}H\log\frac{Hd}{\delta})=\frac{C^{\prime}H\log\frac{Hd}{\delta}}{\log\frac{C^{\prime}Hd}{\delta}+\log\log\frac{Hd}{\delta}}\geq
CH=f(T).$

If we choose $C^{\prime}\geq 2C+C\log C^{\prime}$, then

$\displaystyle
CH\left(\log\frac{C^{\prime}Hd}{\delta}+\log\log\frac{Hd}{\delta}\right)$
$\displaystyle\leq CH(\log\frac{C^{\prime}Hd}{\delta}+\log\frac{Hd}{\delta})$
$\displaystyle\leq 2CH\log\frac{Hd}{\delta}+CH\log C^{\prime}$
$\displaystyle\leq(2C+C\log C^{\prime})H\log\frac{Hd}{\delta}$
$\displaystyle\leq C^{\prime}H\log\frac{Hd}{\delta}.$

∎