Let Z RD and T R d be two random variables that have moments. We first prove the direction Z T SI(Z;T) = 0, which is equivalent to prove I(Z;T) = 0 SI(Z;T) = 0. We prove the contrapositive, i.e. rather than show LHS = RHS, we show that RHS = LHS. This is because for any h,gthat satisfy ρ(h,g) 0, we can always flip the sign of ρ(h,g)by replacing h by h or g by g, so that the value of ρ(h,g)is higher. Z i = [σ(θ i Z)k]Kk=1, T j = [σ(ϕ j T)k]Kk=1, with σ() defined as in the main text l.103. Now assume that supwi,vj ρ(w i Z i,v j T j) > ϵ for some i,j.

When e 6 WΦ, we have E = Rd and WΦ,E = WΦ. By Theorem 1 in [10], we know that the projected Bellman equation (3.4) has a unique fixed point θ . Thus, L= {θ }. 2. When e WΦ, θe is a unique solution to Φθ = eas Φ is full column rank. We first show that the set of solutions to the projected Bellman equation (3.4) takes the form { θ+ cθe|c R}, where θis any solution to (3.4). On the other hand, suppose that θis not of the form θ+ cθe.

The focus of this paper is on sample complexity guarantees of average-reward reinforcement learning algorithms, which are known to be more challenging to study than their discounted-reward counterparts. To the best of our knowledge, we provide the first known finite sample guarantees using both constant and diminishing step sizes of (i) average-reward TD(λ) with linear function approximation for policy evaluation and (ii) average-reward Q-learning in the tabular setting to find the optimal policy. A major challenge is that since the value functions are agnostic to an additive constant, the corresponding Bellman operators are no longer contraction mappings under any norm. We obtain the results for TD(λ) by working in an appropriately defined subspace that ensures uniqueness of the solution. For Q-learning, we exploit the span seminorm contractive property of the Bellman operator, and construct a novel Lyapunov function obtained by infimal convolution of a generalized Moreau envelope and the indicator function of a set.

A.1 Proof of Monotonicity and Submodularity In Equation (3a), we stated the objective of the knapsack cover to be Remark 1. f+M is monotonically increasing. A.2 Knapsack Cover To find a solution to problem 3, we use the greedy algorithm proposed by Badanidiyuru and Vondrák [2], which deals with submodular maximization subject to a system of lknapsack constraints and with pmatroid constraints. We present an adapted version of the algorithm in Algorithm 2 where l = 1. Theparameter allows us to 16 trade-off solution time and solution quality. In this work, we set = 0.2.