Absolute Constant C, failure probability δ. 2: Initialization: Set bVH+1() 0. 3: for time h= H,H 1,...,1 do 4: Set bQh(,) brh(,) + ( bPh bVh+1)(,) 5: sh,ah, set Γh(sh,ah) = The upper bound of OPE comes from Yin and Wang [2020], Duan et al. [2020] and the Cramer-Rao lower bound comes from Jiang and Li [2016]. Table A shows the statistical optimality for offline policy learning and offline policy evaluation (OPE) in the non-stationary tabular MDPs. By Cauchy-Schwartz inequality, it can be checked that the rate between the two bounds (roughly) deviate by a factor of H (in terms of sample complexity), and this reveals that offline learning is inherently harder than OPE from the statistical aspect. Our analysis of the intrinsic learning bound in Section 4 leverage the key design feature of APVI that bVh+1 only depends on the transition data from time h+ 1 to H while bPh only uses transition pairs at time h. This enables concentration inequalities due the conditional independence.7 Especially, to recover the q VarP(V?h+1) structure to we Next, we use (3) as the intermediate step to crude bounding ||bVh+1 V?h+1|| . Lastly, we can combine this with the extended value difference lemma in Cai et al. [2020] to bound V?1 bV1 and leverage the pessimistic design for bounding bV1 Vbπ1 .

To gain intuition for how p-locality functions, we will introduce another notion of locality, called Markov locality, which will use the language of Markov blankets. We will prove that under relatively relaxed conditions p-locality and Markov locality are equivalent. This will allow us to relate the notion of locality to various graph structures commonly used to represent probability distributions, and will be a key step in proving Properties 2.1 and 2.2. We start by defining the Markov boundary, M(X,S), of a random variable X contained in a set of random variables S, as a minimal set such that p(X|S) = p(X|M(X,S)). The Markov boundary defines a minimal set of variables such that, conditioned on these variables, conditioning on no additional random variables in S changes the probability of X [39]. Similarly, we define the Markov blanket, M(X,S) for X in S as any set of variables such that conditioning on M(X,S), makes X conditionally independent from all other variables [39]. In this way, the Markov boundary is a Markov blanket but not all blankets are boundaries. Markov locality: Given probability distribution p(Z) and function f: RNX+NΘ RNΘ, the update function f(Z) is Markov-local with respect to the distribution p over Z if and only if k: Z Ωs.t. AMarkov boundary can be thought of as the set of variables that'locally' communicate with the parameter Θk, thus providing a natural measure of locality. Importantly, for Markov-locality to be of use, we would like the Markov boundaries of random variables in the model of interest to be unique.

Out-of-distribution (OOD) detection and lossless compression constitute two problems that can be solved by the training of probabilistic models on a first dataset with subsequent likelihood evaluation on a second dataset, where data distributions differ. By defining the generalization of probabilistic models in terms of likelihood we show that, in the case of image models, the OOD generalization ability is dominated by local features.