{'fraction_non_alphanumeric': 0.042554715764587886, 'fraction_numerical': 0.011498370168714403, 'mean_word_length': 4.116935483870968, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 19, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Provably Efficient Third-Person Imitation from Offline Observation

Domain adaptation in imitation learning represents an essential step towards improving generalizability. However, even in the restricted setting of third-person imitation where transfer is between isomorphic Markov Decision Processes, there are no strong guarantees on the performance of transferred policies. We present problem-dependent, statistical learning guarantees for third-person imitation from observation in an offline setting, and a lower bound on performance in the online setting.


Introduction
Imitation learning typically performs training and testing in the same environment. This is by necessity as the Markov Decision Process (MDP) formalism defines a policy on a particular state space. However, real world environments are rarely so cleanly defined and benign changes to the environment can induce a completely new state space. Although deep imitation learning (Ho and Ermon, 2016) still defines a policy on unseen states, it remains extremely difficult to effectively generalize (Duan et al., 2017).
Domain adaptation addresses how to generalize a policy defined in a source domain to perform the same task in a target domain (Higgins et al., 2017). Unfortunately, this objective is inherently ill-defined. One wouldn't expect to successfully transfer from a 2D gridworld to a self-driving car, but there is ambiguity in how to define a similarity measure on MDPs.
Third-person imitation  resolves this ambiguity by considering transfer between isomorphic MDPs (formally defined in Section 2), where the objective is to observe a policy in the source domain, and imitate that policy in the target domain. In contrast to domain adaptation between unaligned distributions, the dynamics structure constrains the space of possible isomorphisms, and in some cases the source and target may be related by a unique isomorphism.
We consider an idealized setting for third-person imitation with complete information about the source domain, where we perfectly understand the dynamics and the policy to be imitated. This work offers a theoretical analysis, in particular demonstrating that restricting to isomorphic MDPs with complete knowledge does not trivialize the problem. Specifically, regarding how the agent may observe the target domain, we consider two regimes, summarized in Figure 1: • In the offline regime (Section 4), an oracle perfectly transfers the source policy into the target domain, and the agent observes trajectories from the oracle policy (without seeing the MM τ ∼ φτ ∼ φ • π −1 * π −1 * π * (a)Mτ ∼φ (b) Figure 1: The observation regimes. In the offline setting (a), the agent observes trajectories τ sampled from the policy φ that have been perfectly transferred into the isomorphic target domain. In the online setting (b), the MDPs are still isomorphic but the agent only observes trajectories after playing their own policyφ.
oracle's actions). In this regime, we provide positive results establishing that with limited, state-only observations in the target domain, we can still efficiently imitate a policy defined in the source domain (Theorem 4.10).
• In the online regime (Section 5), the agent chooses policies in the target domain and draws trajectories. Our negative results in this setting (Theorem 5.1) prove that with full interaction in the target domain, imitation is extremely difficult in the presence of structural symmetry.
A Motivating Example: To clarify the setup and distinguish the two observation regimes, we elaborate upon an example. Suppose our source domain is a video game, where the state space corresponds to the monitor screen and the action space corresponds to key presses. And we wish to imitate an expert player of the game. The target domain is the same game played on a new monitor with higher screen brightness. Clearly the underlying game hasn't changed, and there is a natural bijection from screen states of the target monitor to those of the source monitor, namely "dimming the screen". On the one hand, in the offline setting, we're forbidden from playing on the new monitor ourselves. Instead we observe recordings of the expert, played on the brighter monitor. Again, as these are recordings, we see the states the expert visits but not their actions. On the other hand, in the online setting, we simply run transitions on the brighter monitor. Note that if the screen includes benign features which minimally impact the game (say the player's chosen name appears onscreen), it may be very difficult to learn the bijection between target and source monitor. Either way, through observations we guess a new policy to played on the bright monitor, which hopefully mimics the expert's behavior.

Summary of Contributions:
Our primary contribution in this work is a provably efficient algorithm for offline third-person imitation, with an polynomial upper bound for the sample complexity necessary to control the imitation loss. Our main technical novelty is a means of clipping the states of a Markov chain according to their stationary distribution, while preserving properties of a bijection between isomorphic chains. We also prove an algorithm-agnostic lower bound for online third-person imitation, through reduction to bandit lower bounds.
We also fix an ordering of the statesŜ so that π * may be written in matrix form Π * as a permutation matrix. In particular, we will overload notation to use π * as a permutation on [|S|], such that π * (i) = j denotes that π * (ŝ i ) = s j . Let P denote the space ofŜ → S permutation matrices.
A policy φ maps states to distributions on actions, but for our purposes it will be convenient to consider the policy as a matrix Φ : S → S × A. To relate the two notions, Φ is a block of diagonal matrices Φ a : The dynamics matrix is denoted P : S × A → S. It can also be decomposed into blocks P a : S → S where (P a ) ij = p(s j |s i , a), and P = [P a 1 | . . . |P a |A| ].
Using this notation, Φ T P T forms the Markov chain on S induced by following policy φ. Explicitly, Note that under this notation, the dynamics and initial distribution inM can be written aŝ P = Π T * P (I ⊗ Π * ) andp 0 = Π T * p 0 respectively. The occupancy measure ρ φ is defined with regard to a policy, as well as the underlying dynamics and initial distribution. Specifically, ρ φ (s, a) = (1 − γ)E s 0 ∼p 0 ,τ ∼Φ ∞ i=0 γ i φ(a|s)P (s i = s) , where the dependence on the dynamics P is through the sampling of a trajectory τ .
Similarly, we introduce the state-only occupancy measure µ φ (s) := a ρ φ (s, a). We will make use of the identity ρ φ (s, a) = φ(a|s)µ φ (s), as well as the fact that µ φ is the stationary distribution of the Markov chain Φ T ((1 − γ)p 0 1 T + γP ) T , which both follow from the constraint-based characterization of occupancy (Puterman, 1994).
The value function for a given policy φ and reward function R is defined as We note the very useful identity Lastly, we use the notation σ i (A) to denote the ith largest singular value of A.

Observation Settings
To begin, we're given full knowledge of the source domain M, as well as Φ : S × A → S and ρ Φ ∈ R S×A , the policy and corresponding occupancy measure we want to imitate. We consider two settings through which we can interact with the target domain, in order to learn how to adapt Φ into this new domain.
Offline: In the offline setting, we only observe the policy Φ * := (I ⊗ Π T * )ΦΠ * being played inM. We can consider Φ * as an oracle for third-person imitation, as this policy exactly maps fromM to M, calls Φ, and maps back. To guarantee the trajectories don't get trapped in a terminal state, we assume this agent has a 1 − γ reset probability. Through these observations, we must output a policyΦ to be played inM. We provide upper bounds for this setting in Section 4.
Crucially, in this setting we assume access to the states but not actions from observed trajectories, in the imitation from observation setting . This assumption is well-motivated. In practice, observed trajectories from an expert often come from video, where actions are difficult to infer (Liu et al., 2018). Additionally, the problem becomes trivial with observed actions, as one may mimic the oracle's actions at each state inŜ without trying to understand Π * at all.
Online: In the online setting, we define our own policyΦ t to play inM at each timestep t, with full observation of the trajectories. After T total transitions we output our final policyΦ. Intuitively, this setting allows for more varied observations in the target domain. But without an expert oracle to demonstrate the correct state distribution, an agent in this setting may be deceived by near-symmetry in the dynamics and predict the wrong alignment. We further highlight this difficulty in Section 5.

Imitation Objective
In either setting, through observations from the target domain we output a policyΦ. The corresponding occupancy measure we denote as ρΦ ,Π * ∈ RŜ ×A , where the subscript Π * reflects the dependence on the dynamics and initial distribution inM, namely Π T * P (I ⊗ Π * ) and Π T * p 0 . We measure imitation by comparing the correctly transferred policy Φ * against the guessed policyΦ. Explicitly, our objective is As a sanity check, we confirm that if we playΦ = Φ * = (I ⊗ Π T * )ΦΠ * , then indeedρΦ ,Π * = (I ⊗ Π T * )ρ Φ and the occupancies are equal. A form of this objective with a general IPM as the distributional distance was introduced in (Ho and Ermon, 2016). To justify using this loss, note the objective can be equivalently written In other words, minimizing imitation objective guarantees Φ * andΦ perform nearly as well for any reward function with a bound on maximum magnitude.

Related Work
The theory of imitation learning depends crucially on what interaction is available to the agent. Behavior cloning (Bain, 1995) learns a policy offline from supervised expert data. With online data, imitation learning can be cast as a measure matching problem on occupancy measures (Ho and Ermon, 2016). With an expert oracle, imitation learning has no-regret guarantees (Ross et al., 2011). Numerous of these algorithms for imitation learning can be adapted to the observation setting (Torabi et al., 2018a,b;Yang et al., 2019).
General domain adaptation for imitation learning has a rich applied literature (Ammar et al., 2015;Pastor et al., 2009;Tobin et al., 2017). Third-person imitation specifically was formalized in Stadie et al. (2017), extending the method of Ho and Ermon (2016) by learning domain-agnostic features. Other deep algorithms explicitly learn an alignment between the state spaces, based on multiple tasks in the same environments (Kim et al., 2019) or unsupervised image alignment (Gamrian and Goldberg, 2019).
The closest work to ours is , which shares the focus on imitation learning without access to actions, but differs in studying the first-person setting primarily with online feedback. This work also takes inspiration from literature on friendly graphs (Aflalo et al., 2015), which characterize robustly asymmetric structure.

Markov Chain Alignment
Because the offline setting only runs policy Φ * , and reveals no actions, it is equivalent to observing a trajectory of the state-only Markov chain induced by Φ * inM. Let us elaborate on this fact.
Define the Markov chain M := Φ T ((1 − γ)p 0 1 T + γP ) T , which is ergodic when restricted to the strongly connected components that intersect the initial distribution. InM, the dynamics are Π T * P (I ⊗ Π * ), the oracle policy is (I ⊗ Π * ) T ΦΠ * , and the initial distribution is Π T * p 0 . We also assume the oracle agent following Φ * has a 1 − γ reset probability.
All together, this implies our observations in the offline setting are drawn from a trajectory of Π T * M Π * . In summary, given full knowledge of M and a trajectory sampled from Π T * M Π * , our algorithm will seek to learn the alignment Π * in order to approximate Φ * , hopefully leading to low imitation loss.

Symmetry without approximation
As a warmup, we consider the setting with no approximation where we observe Π T * M Π * exactly. To relate this chain to M , we can try to find symmetries, i.e. the minimizers of arg min We can equivalently consider finding automorphisms of M , which may be posed as a minimization over permutation matrices Π : S → S: Clearly both these objectives are minimized at 0. Intuitively, to recover Π * we'd like Π * to be the unique minimizer of (4), or equivalently I to be the unique minimizer of (5). Hence, in order to make third-person imitation tractable, we will seek to bound (5) away from 0 when Π = I, or in other words focus on Markov chains which are robustly asymmetric.
We introduce notation: Definition 4.2 (Friendly matrix). A matrix A is friendly if, given the singular value decomposition A = U ΣV T , Σ has distinct diagonal elements and V T 1 has all non-zero elements.
elementwise. An ergodic Markov chain M is friendly if its rescaled transition matrix L is friendly.
The significance of friendliness in graphs was studied in Aflalo et al. (2015), to characterize relaxations of the graph isomorphism problem. We first confirm several friendliness properties for Markov chains still hold.
So by uniqueness of the stationary distribution in an ergodic chain, µ = Π T µ and therefore D = Π T DΠ. Then clearly D 1/2 = Π T D 1/2 Π and therefore L = Π T LΠ.
For the reverse implication, Proposition 4.4. If M is friendly, then it has a trivial automorphism group.
In what follows, for any SVD, we will always choose to orient V such that V T 1 ≥ 0 elementwise.

Exact Symmetry Algorithm
By Proposition 4.3, the automorphism group of M is contained in the automorphism group of the rescaled transition matrix L. Interpreting L as a weighted graph, determining its automorphisms is at least as computationally hard as the graph isomorphism problem (Aflalo et al., 2015).
In general, algorithms for graph isomorphisms optimize time complexity, whereas we are more interested in controlling sample complexity. Nevertheless, we have the following result: This result is a simple extension of the main result in Umeyama (1988), applying the friendliness property to Markov chains rather than adjacency matrices. But the characterization of automorphisms will be used again later to control sample complexity, when we only observe Π T * M Π * through sampled trajectories.
Commuting with a diagonal matrix with distinct elements implies V T 2 Π T * V 1 is diagonal. As this product is also unitary and real, it must be that V T 2 Π T * V 1 = S where S is diagonal and S 2 = I. Again rearranging, this implies 1 T V 1 = 1 T Π T * V 1 = 1 T V 2 S. By the assumption on the SVD orientation, S must preserve signs, therefore S = I, and V 2 = Π T * V 1 . Now, suppose V 2 = Π T V 1 . Then L T 2 L 2 = Π T L T 1 L 1 Π, so Π T * Π is an automorphism of L T 2 L 2 and therefore Π = Π * .
Proof of Theorem 4.5. Let L 1 and L 2 be the rescaled transition matrices of M and Π T * M Π * respectively. Reusing the same SVD notation, by Proposition 4.3 and 4.6, V 2 = Π T * V 1 . Consider the linear assignment problem min Π∈P V 2 − Π T V 1 F , which may be solved in O(|S| 3 ) time using the Hungarian algorithm (Kuhn, 1955). Again by Proposition 4.6, this linear program is minimized at 0 and recovers Π * as the unique minimizer.

Symmetry with approximation
With finite sample complexity, we still know the base chain M exactly, but we get empirical estimates of the permuted chain Π T * M Π * by running trajectories. Specifically, m samples (X 1 , . . . , X m ) are drawn from Π T * M Π * , with X 1 ∼ Π T * p 0 . Call the empirical estimateM , i.e.M ij = N ij N i where N ij counts the number of observed i → j transitions and N i = j N ij . And the empirical stationary distribution isμ whereμ i = N i j N j and D = diag(μ). We can characterize the approximation error of the chain and stationary distribution as E := Π * M Π T * − M and ∆ = Π * D Π T * − D respectively. Note these error terms are defined in the original state space S.
Our goal is to useM to produce a good policy in the target space. Say we predict the bijection is Π, and play the policyΦ = (I ⊗ Π T )ΦΠ, whereas the correct policy in the target space is Φ * = (I ⊗ Π T * )ΦΠ * . We'd like to be able to control the imitation distance between these two policies when Π ≈ Π * .
For that purpose, define I t (M ) = {i ∈ S : µ i ≥ t, µ T = µ T M }, where µ is the stationary distribution of M , so these states will be visited "sufficiently" often. We first show correctness of the bijection on these states suffices for good imitation.
] is the average advantage function.

Approximate Symmetry Algorithm
Algorithm 1: Permuted Policy Learning Input: P , Φ, γ, p 0 , t, (X 1 , . . . , X m ) Output: Choose any Π ∈ P such that ∀i ∈Î t , π(i) = π ′ (i) return (I ⊗ Π) T ΦΠ In light of Theorem 4.8, an algorithm could either seek to recover Π * exactly, or find a Π which agrees with Π * on high occupancy states. We consider a learning algorithm for both objectives, and bound its sample complexity. The trick will be carefully setting the threshold t that defines what constitutes high occupancy.
To state the theorem, we introduce the subscript t notation to denote the principle submatrix defined by the indices of I t , and g := min i |µ i − t| is the gap between the threshold and stationary values. Lastly, we define: Definition 4.9 (Pseudospectral gap). The pseudospectral gap of an ergodic Markov chain M is γ ps (M ) = max k≥1 , where λ 2 denotes the second largest eigenvalue.
If M is not ergodic, we will take γ ps (M ) to mean the pseudospectral gap of M restricted to the strongly connected components that intersect p 0 .
Theorem 4.10. The policy learning algorithm in Algorithm 1 satisfies the following: The most important feature of this bound is the dependence on |S|. In the sample complexity it only appears through a log term, and all other terms can be independent of |S| depending on the choice of t and the structural properties of M . The error is still linear in |S|, but this term appears necessary. If some occupancy mass leaves the well-supported states π −1 * (I t ), it could cover all the negligible states, and either incur error linear in |S|, or require exploration of every state and therefore sample complexity linear in |S|.
Proof sketch. Here we give the main ideas of the proof, full details are provided in the Appendix.
GivenM andD, the immediate choice for an estimator of the rescaled transition matrix would beD 1/2MD−1/2 . However, this will not be well-defined if our samples don't visit every state of S. Furthermore, if M is only ergodic when restricted to a subset of S, thenD −1 won't be defined even with infinite sample complexity. Similarly, if µ * := min i µ i is vanishingly small, m will become prohibitively large in order to guarantee thatD −1 is well-defined.
Our primary technical novelty addresses both these issues by setting a threshold t on stationary mass, and discarding states below the threshold. Define I t = {i ∈ [|S|] : µ i ≥ t} andÎ t = {i ∈ [|S|] :μ i ≥ t}. We restate the notation that a subscript t denotes taking the principle submatrix corresponding to I t orÎ t depending on the matrix's domain. So for example, M t is M restricted to rows and columns given by I t , and likewiseM t isM restricted toÎ t .
Several concentration results for empirical Markov chain transitions and stationary distributions control the convergence of our estimators (Wolfer and Kontorovich, 2019a,b). Our main assumption is that the gap g = min i |µ i −t| is non-negligible. Then with high probability and sample complexity depending on g but not min i µ i , µ i ≥ t iffμ i ≥ t. In other words, no empirical stationary estimates will "cross" the threshold, or put another way π −1 * (I t ) =Î t . We can then restrict our attention to the states above the threshold, such that the sample complexity necessary for concentratioñ M ≈ M depends on t but not min i µ i (and only logarithmically on |S|).
For t > 0, the restricted rescaled transition matrix And with high probability we can define our estimatorL t =D 1/2 tM tD −1/2 t . Appealing to a strong friendliness assumption on L t , singular value perturbation inequalities imply thatL t is also friendly.
x 1ŷ1 x 2 x 3ŷ2ŷ3 1 1 1 x 1ŷ1 x 2 x 3ŷ2ŷ3 Finally, the asymmetric properties of friendly matrices given in Proposition 4.6 enable exact recovery of the submatrix of Π * restricted to the indices I t andÎ t . And by Theorem 4.8, determining the alignment on all high-occupancy states still yields a bound on the imitation loss.

MDP Alignment
In the online setting, we're still seeking to imitate Φ, or equivalently ρ Φ . However, we no longer observe trajectories of the correct policy (I ⊗ Π * ) T ΦΠ * played inM.
Instead, we are in a setting similar to a bandit, but without reward. At time t, we play a policŷ Φ t defined onM and observe a transition. We allow resets to the initial distribution. After T plays, where T may be a random variable, we choose a final policyΦ and receive instantaneous regret given by g(Φ, Π * ,Φ).
One simple algorithm might treat each possible bijection as an arm, where pulling Π is akin to running a trajectory using the policy Π T ΦΠ, and then infer which alignment best matches the behavior policy. Or one could consider algorithms which don't play policies of the form Π T ΦΠ but simply explore the target space in a principled way.
Nevertheless, we derive a lower bound on the imitation loss of any algorithm in the online setting, demonstrating even complete knowledge of the source domain doesn't trivialize thirdperson imitation.

Lower Bound Counterexample
Consider a small bandit-like MDP (Figure 2a). Red corresponds to action r, blue corresponds to action b, and purple corresponds to both. The numbers on the edges give transition probabilities when taking the associated action. Let the initial distribution be p 0 (x 0 ) = p 0 (y 0 ) = 1/2. In other words, the initial state is either x 0 or y 0 . Starting at x 0 , the initial action is deterministic: playing r leads to x 1 , playing b leads to y 1 . Starting at y the actions lead to the opposite states. Then the choice of action is irrelevant, and the transition to a terminal state is determined by α at x 1 and β at y 1 .
This characterizes M. To introduceM, let's consider two possible bijections Π 1 and Π 2 , which correspond to the possible target MDPs in Figure 2b and Figure 2c (note the values of α and β are swapped given Π 2 ). These correspond to two possible dynamics on our target space. Π 1 is essentially the identity map, preserving states up to hats. Whereas Π 2 (x i ) = y i and Π 2 (ŷ i ) = x i .
Finally, suppose the behavior policy we want to imitate in M is defined by φ(r|x 0 ) = 1 and φ(b|y 0 ) = 1. In other words, the agent always travels in the first step to x 1 . That means, under Π 1 we want to travel tox 1 , and under Π 2 we want to travel toŷ 1 . Intuitively, because ρ Φ is highly asymmetric, but the MDP is nearly symmetric, one cannot choose a policy that performs well in multiple permutations of the MDP. We formalize this intuition below.
Proof. Fix a policyφ, and we will write ρφ ,Π as simply ρ Π . Again use the variational form of total variation to say T V (ρ 1 , ρ 2 ) = sup c ∞≤1 ρ 1 − ρ 2 , c . Choose c so that c(x i , a) = 1 for i ∈ {1, 2, 3} and a ∈ A, and 0 elsewhere. Then a direct calculation gives g +φ(b|ŷ 0 ))/2. Now we proceed by a reduction to multi-armed bandits with known biases. Consider a twoarmed bandit with Bernoulli rewards, where the hypotheses for arm biases are H 1 = {α, β} and H 2 = {β, α}. We define the following algorithm B for the two-armed bandit. First run algorithm A on our MDP, where we couple pulls from arm 1 with transitions fromx 1 and pulls from arm 2 with transitions fromŷ 1 . Callφ the policy output by A. Then output arm 1 ifφ(r|x 0 ) > 1/2, otherwise arm 2.
This bound illustrates why imitation is substantially more challenging than seeking high reward. In a regular RL problem with reward at the terminal states, if α ≈ β then the expected reward changes very slightly depending on the policy. But in the imitation setting, the value of α and β are essentially features of the states, which the agent must (very inefficiently) distinguish in order to achieve error lower than γ/4. Likewise, this counterexample captures why the online setting is the more challenging one studied in this work. In the offline regime, an oracle would only visit states on one half of the MDP and easily break the symmetry.
One may attribute this pessimistic bound to the choice of total variation distance. Indeed, among IPMs, total variation has very poor generalization properties . However, an alternative choice of IPM corresponds to a non-uniform prior over reward functions that the behavior policy is truly optimizing. If the prior strongly favored reward functions that smoothly depend on the local dynamics, then c(x i , a) ≈ c(ŷ i , a) and this counterexample would no longer hold. But this is a somewhat unnatural assumption, precluding for example a 2D gridworld with positive reward only at one state (since the gridworld would have many symmetries).

Conclusion and Future Work
In this paper, we introduced a theoretical analysis of third-person imitation, as an initial step in more fully understanding generalization in RL. We demonstrated upper bounds for imitation learning across isomorphic domains under offline and state-only assumptions, and a lower bound for the online setting. These bounds depend heavily on the structural properties of the dynamics and behavior policy, as well as the setting of third-person imitation where the domain adaptation is across isomorphic environments.
The upper bound dependence on structural and spectral properties is likely not optimal, although the dependence on |S| in the error likely cannot be improved. The lower bound is somewhat more robust, and any MDP with symmetry such that this bandit-like MDP can be embedded will suffer a similar lower bound on sample complexity.
The isomorphism assumption is certainly too strict in general. However, weakening the assumption requires a characterization of MDP similarity, in order to decide when one should expect policy transfer through imitation to be feasible. MDPs with features (Krishnamurthy et al., 2016) could better characterize similarity, where the spectral features studied in this work could be combined with observed state features for more effective alignment through linear assignment. Future work may include studying third-person imitation in the online setting for upper bounds, or exploiting MDP asymmetry in deep imitation.

A Proof of Theorem 4.10
We define D p 0 = i (p 0 ) 2 i /µ i , where we interpret 0/0 = 0. Note that p 0 is absolutely continuous with respect to µ, so this term is well-defined.
We now state the necessary concentration results. Note the theorems are slightly altered from their statements in the literature, but follow immediately from their original proofs. The first has a better dependence on |S| by considering L 2 norm rather than L 1 , and with slightly loose sample complexity. The second is exactly an intermediate statement made in the theorem's original proof. Proof. Choosing k = 1 in the definition of γ ps gives the product D −1 M T DM = D −1/2 L T LD 1/2 . The first term itself is a Markov chain called the multiplicative reversiblization (Paulin et al., 2015). Because the chain has maximum eigenvalue 1 and the eigenvalues of L T L are the squares of the singular values, it follows σ 1 (L) = 1 and γ ps ≥ 1 − σ 2 (L) 2 .
Lemma A.5. If L t is (α, β)-friendly for sufficiently large α and β, the matrixL t is friendly if it is well-defined.
We need the following bounds, utilizing the inequality √ a + b − √ a ≤ |b|: