summaries: The authors provide a theoretical analysis of deep Q-learning based on the neural fitted Q-iteration (FQI) algorithm [1]. Their analysis justifies the techniques of experience replay and target network, both of which are critical to the empirical success of DQN. Moreover, the authors establish the algorithmic and statistical errors of the neural FQI algorithm. This paper provides an analysis of fitted Q-iteration in the off-policy reinforcement learning setting, for the setup where the value function class of interest is a class of neural networks. The provide bounds on the rate at which fitted Q iteration converges to a near-optimal policy under the assumption that the transition dynamics satisfy a certain notion of Holder smoothness. This result is motivated by the problem of understanding why deep Q-learning works, which the authors relate to the problem above via certain simplifying assumptions. The authors also extend this result to give similar guarantees for two-player zero-sum stochastic games.
abstractText: Despite the great empirical success of deep reinforcement learning, its theoretical foundation is less well understood. In this work, we make the first attempt to theoretically understand the deep Q-network (DQN) algorithm (Mnih et al., 2015) from both algorithmic and statistical perspectives. In specific, we focus on the fitted Q iteration (FQI) algorithm with deep neural networks, which is a slight simplification of DQN that captures the tricks of experience replay and target network used in DQN. Under mild assumptions, we establish the algorithmic and statistical rates of convergence for the action-value functions of the iterative policy sequence obtained by FQI. In particular, the statistical error characterizes the bias and variance that arise from approximating the action-value function using deep neural network, while the algorithmic error converges to zero at a geometric rate. As a byproduct, our analysis provides justifications for the techniques of experience replay and target network, which are crucial to the empirical success of DQN. Furthermore, as a simple extension of DQN, we propose the Minimax-DQN algorithm for zero-sum Markov game with two players, which is deferred to the appendix due to space limitations.
authors.name: DEEP Q-LEARNING
references.authors: Zeyuan Allen-Zhu Yuanzhi Li Yingyu Liang
references.title: Learning and generalization in overparameterized neural networks, going beyond two layers
references.venue: arXiv preprint arXiv:1811.04918,
references.authors: Zeyuan Allen-Zhu Yuanzhi Li Zhao Song
references.title: A convergence theory for deep learning via overparameterization
references.venue: arXiv preprint arXiv:1811.03962,
references.authors: Martin Anthony Peter L Bartlett
references.title: Neural network learning: Theoretical foundations
references.authors: András Antos Csaba Szepesvári Rémi Munos
references.title: Value-iteration based fitted policy iteration: learning with a single trajectory
references.venue: In IEEE International Symposium on Approximate Dynamic Programming and Reinforcement Learning,
references.authors: András Antos Csaba Szepesvári Rémi Munos
references.title: Fitted Q-iteration in continuous action-space mdps
references.venue: In Advances in neural information processing systems,
references.authors: András Antos Csaba Szepesvári Rémi Munos
references.title: Learning near-optimal policies with Bellmanresidual minimization based fitted policy iteration and a single sample path
references.venue: Machine Learning,
references.authors: Sanjeev Arora Simon S Du Wei Hu Zhiyuan Li Ruosong Wang
references.title: Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks
references.authors: Kai Arulkumaran Marc Peter Deisenroth Miles Brundage Anil Anthony Bharath
references.title: A brief survey of deep reinforcement learning
references.venue: arXiv preprint arXiv:1708.05866,
references.authors: Leemon Baird
references.title: Residual algorithms: Reinforcement learning with function approximation
references.venue: In Machine Learning Proceedings
references.authors: Peter L Bartlett
references.title: The sample complexity of pattern classification with neural networks: the size of the weights is more important than the size of the network
references.venue: IEEE transactions on Information Theory,
references.authors: Peter L Bartlett Vitaly Maiorov Ron Meir
references.title: Almost linear VC dimension bounds for piecewise polynomial networks
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Peter L Bartlett Dylan J Foster Matus J Telgarsky
references.title: Spectrally-normalized margin bounds for neural networks
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Peter L Bartlett Nick Harvey Chris Liaw Abbas Mehrabian
references.title: Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks
references.venue: arXiv preprint arXiv:1703.02930,
references.authors: Benedikt Bauer Michael Kohler
references.title: On deep learning as a remedy for the curse of dimensionality in nonparametric regression
references.venue: The Annals of Statistics,
references.authors: Marc G Bellemare Yavar Naddaf Joel Veness Michael Bowling
references.title: The Arcade learning environment: An evaluation platform for general agents
references.venue: Journal of Artificial Intelligence Research,
references.authors: Michael Bowling
references.title: Rational and convergent learning in stochastic games
references.venue: In International Conference on Artificial Intelligence,
references.authors: Justin A Boyan
references.title: Technical update: Least-squares temporal difference learning
references.venue: Machine Learning,
references.authors: Steven J Bradtke Andrew G Barto
references.title: Linear least-squares algorithms for temporal difference learning
references.venue: Machine learning,
references.authors: Yuan Cao Quanquan Gu
references.title: A generalization theory of gradient descent for learning overparameterized deep relu networks
references.venue: arXiv preprint arXiv:1902.01384,
references.authors: Hongshen Chen Xiaorui Liu Dawei Yin Jiliang Tang
references.title: A survey on dialogue systems: Recent advances and new frontiers
references.venue: arXiv preprint arXiv:1711.01731,
references.authors: Lenaic Chizat Francis Bach
references.title: A note on lazy training in supervised differentiable programming
references.venue: arXiv preprint arXiv:1812.07956,
references.authors: Vincent Conitzer Tuomas Sandholm
references.title: AWESOME: A general multiagent learning algorithm that converges in self-play and learns a best response against stationary opponents
references.venue: Machine Learning,
references.authors: Simon S Du Jason D Lee Haochuan Li Liwei Wang Xiyu Zhai
references.title: Gradient descent finds global minima of deep neural networks
references.venue: arXiv preprint arXiv:1811.03804,
references.authors: Simon S Du Xiyu Zhai Barnabas Poczos Aarti Singh
references.title: Gradient descent provably optimizes over-parameterized neural networks
references.venue: arXiv preprint arXiv:1810.02054,
references.authors: Gintare Karolina Dziugaite Daniel M Roy
references.title: Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data
references.venue: arXiv preprint arXiv:1703.11008,
references.authors: Damien Ernst Pierre Geurts Louis Wehenkel
references.title: Tree-based batch mode reinforcement learning
references.venue: Journal of Machine Learning Research,
references.authors: Jianqing Fan Cong Ma Yiqiao Zhong
references.title: A selective overview of deep learning
references.venue: arXiv preprint arXiv:1904.05526,
references.authors: Amir-massoud Farahmand Mohammad Ghavamzadeh Csaba Szepesvári Shie Mannor
references.title: Regularized fitted Q-iteration for planning in continuous-space Markovian decision problems
references.venue: In American Control Conference,
references.authors: Amir-massoud Farahmand Csaba Szepesvári Rémi Munos
references.title: Error propagation for approximate policy and value iteration
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Amir-massoud Farahmand Mohammad Ghavamzadeh Csaba Szepesvári Shie Mannor
references.title: Regularized policy iteration with nonparametric function spaces
references.venue: The Journal of Machine Learning Research,
references.authors: Matthieu Geist Bruno Scherrer Olivier Pietquin
references.title: A theory of regularized markov decision processes
references.venue: arXiv preprint arXiv:1901.11275,
references.authors: Noah Golowich Alexander Rakhlin Ohad Shamir
references.title: Size-independent sample complexity of neural networks
references.venue: arXiv preprint arXiv:1712.06541,
references.authors: Song Han Huizi Mao William J Dally
references.title: Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding
references.venue: arXiv preprint arXiv:1510.00149,
references.authors: Matthew Hausknecht Peter Stone
references.title: Deep recurrent Q-learning for partially observable mdps
references.venue: In 2015 AAAI Fall Symposium Series,
references.authors: Arthur Jacot Franck Gabriel Clément Hongler
references.title: Neural tangent kernel: Convergence and generalization in neural networks
references.venue: In Advances in neural information processing systems,
references.authors: Kenji Kawaguchi Leslie Pack Kaelbling Yoshua Bengio
references.title: Generalization in deep learning
references.venue: arXiv preprint arXiv:1710.05468,
references.authors: Jason M Klusowski Andrew R Barron
references.title: Risk bounds for high-dimensional ridge function combinations including neural networks
references.venue: arXiv preprint arXiv:1607.01434,
references.authors: Jens Kober Jan Peters
references.title: Reinforcement learning in robotics: A survey
references.venue: In Reinforcement Learning,
references.authors: Michail G Lagoudakis Ronald Parr
references.title: Value function approximation in zero-sum markov games
references.venue: In Uncertainty in Artificial Intelligence, pp
references.authors: Michail G Lagoudakis Ronald Parr
references.title: Least-squares policy iteration
references.venue: Journal of machine learning research,
references.authors: Sascha Lange Thomas Gabel Martin Riedmiller
references.title: Batch reinforcement learning
references.venue: In Reinforcement learning,
references.authors: Alessandro Lazaric Mohammad Ghavamzadeh Rémi Munos
references.title: Finite-sample analysis of leastsquares policy iteration
references.venue: Journal of Machine Learning Research,
references.authors: Alessandro Lazaric Mohammad Ghavamzadeh Rémi Munos
references.title: Analysis of classification-based policy iteration algorithms
references.venue: The Journal of Machine Learning Research,
references.authors: Yuanzhi Li Yingyu Liang
references.title: Learning overparameterized neural networks via stochastic gradient descent on structured data
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Tengyuan Liang Tomaso Poggio Alexander Rakhlin James Stokes
references.title: Fisher-Rao metric, geometry, and complexity of neural networks
references.venue: arXiv preprint arXiv:1711.01530,
references.authors: Long-Ji Lin
references.title: Self-improving reactive agents based on reinforcement learning, planning and teaching
references.venue: Machine learning,
references.authors: Michael L Littman
references.title: Markov games as a framework for multi-agent reinforcement learning
references.venue: In Machine Learning Proceedings
references.authors: Baoyuan Liu Min Wang Hassan Foroosh Marshall Tappen Marianna Pensky
references.title: Sparse convolutional neural networks
references.venue: In Conference on Computer Vision and Pattern Recognition,
references.authors: Ruishan Liu James Zou
references.title: The effects of memory replay in reinforcement learning
references.venue: arXiv preprint arXiv:1710.06574,
references.authors: Chao Ma Lei Wu
references.title: A comparative analysis of the optimization and generalization property of two-layer neural network and random feature models under gradient descent dynamics
references.authors: Wolfgang Maass
references.title: Neural nets with superlinear VC-dimension
references.venue: Neural Computation,
references.authors: Song Mei Theodor Misiakiewicz Andrea Montanari
references.title: Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit
references.authors: Volodymyr Mnih Koray Kavukcuoglu David Silver Andrei A Rusu Joel Veness Marc G Bellemare Alex Graves Martin Riedmiller Andreas K Fidjeland Georg Ostrovski
references.title: Human-level control through deep reinforcement learning
references.venue: Nature, 518(7540):529–533,
references.authors: Volodymyr Mnih Adria Puigdomenech Badia Mehdi Mirza Alex Graves Timothy Lillicrap Tim Harley David Silver Koray Kavukcuoglu
references.title: Asynchronous methods for deep reinforcement learning
references.venue: In International Conference on Machine Learning,
references.authors: Mehryar Mohri Afshin Rostamizadeh Ameet Talwalkar
references.title: Foundations of machine learning
references.authors: Rémi Munos Csaba Szepesvári
references.title: Finite-time bounds for fitted value iteration
references.venue: Journal of Machine Learning Research,
references.authors: Vinod Nair Geoffrey E Hinton
references.title: Rectified linear units improve restricted boltzmann machines
references.venue: In International conference on machine learning,
references.authors: Behnam Neyshabur Ruslan R Salakhutdinov Nati Srebro
references.title: Path-SGD: Path-normalized optimization in deep neural networks
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Behnam Neyshabur Ryota Tomioka Nathan Srebro
references.title: Norm-based capacity control in neural networks
references.venue: In Conference on Learning Theory, pp
references.authors: Behnam Neyshabur Srinadh Bhojanapalli David McAllester Nathan Srebro
references.title: A PACBayesian approach to spectrally-normalized margin bounds for neural networks
references.venue: arXiv preprint arXiv:1707.09564,
references.authors: Behnam Neyshabur Srinadh Bhojanapalli David McAllester Nati Srebro
references.title: Exploring generalization in deep learning
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Stephen David Patek
references.title: Stochastic and shortest path games: theory and algorithms
references.venue: PhD thesis, Massachusetts Institute of Technology,
references.authors: Julien Perolat Bruno Scherrer Bilal Piot Olivier Pietquin
references.title: Approximate dynamic programming for two-player zero-sum markov games
references.venue: In International Conference on Machine Learning
references.authors: Julien Pérolat Bilal Piot Matthieu Geist Bruno Scherrer Olivier Pietquin
references.title: Softened approximate policy iteration for markov games
references.venue: In International Conference on Machine Learning,
references.authors: Julien Pérolat Bilal Piot Bruno Scherrer Olivier Pietquin
references.title: On the use of non-stationary strategies for solving two-player zero-sum markov games
references.venue: In International Conference on Artificial Intelligence and Statistics,
references.authors: Julien Pérolat Bilal Piot Olivier Pietquin
references.title: Actor-critic fictitious play in simultaneous move multistage games
references.venue: In International Conference on Artificial Intelligence and Statistics,
references.authors: HL Prasad Prashanth LA Shalabh Bhatnagar
references.title: Two-timescale algorithms for learning Nash equilibria in general-sum stochastic games
references.venue: In International Conference on Autonomous Agents and Multiagent Systems, pp. 1371–1379. International Foundation for Autonomous Agents and Multiagent Systems,
references.authors: Ali Rahimi Benjamin Recht
references.title: Random features for large-scale kernel machines
references.venue: In Advances in neural information processing systems,
references.authors: Martin Riedmiller
references.title: Neural fitted Q iteration–first experiences with a data efficient neural reinforcement learning method
references.venue: In European Conference on Machine Learning,
references.authors: Tom Schaul John Quan Ioannis Antonoglou David Silver
references.title: Prioritized experience replay
references.venue: International Conference on Learning Representations,
references.authors: Bruno Scherrer Mohammad Ghavamzadeh Victor Gabillon Boris Lesner Matthieu Geist
references.title: Approximate modified policy iteration and its application to the game of tetris
references.venue: Journal of Machine Learning Research,
references.authors: Johannes Schmidt-Hieber
references.title: Nonparametric regression using deep neural networks with ReLU activation function
references.venue: arXiv preprint arXiv:1708.06633,
references.authors: David Silver Aja Huang Chris J Maddison Arthur Guez Laurent Sifre George Van Den Driessche Julian Schrittwieser Ioannis Antonoglou Veda Panneershelvam Marc Lanctot
references.title: Mastering the game of Go with deep neural networks and tree
references.venue: search. Nature,
references.authors: David Silver Julian Schrittwieser Karen Simonyan Ioannis Antonoglou Aja Huang Arthur Guez Thomas Hubert Lucas Baker Matthew Lai Adrian Bolton
references.title: Mastering the game of Go without human knowledge
references.authors: Sriram Srinivasan Marc Lanctot Vinicius Zambaldi Julien Pérolat Karl Tuyls Rémi Munos Michael Bowling
references.title: Actor-critic policy optimization in partially observable multiagent environments
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Charles J Stone
references.title: Optimal global rates of convergence for nonparametric regression
references.venue: The Annals of Statistics,
references.authors: Richard S Sutton Andrew G Barto
references.title: Reinforcement learning: An introduction
references.authors: Richard S Sutton David A McAllester Satinder P Singh Yishay Mansour
references.title: Policy gradient methods for reinforcement learning with function approximation
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Taiji Suzuki
references.title: Adaptivity of deep relu network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality
references.venue: arXiv preprint arXiv:1810.08033,
references.authors: Manel Tagorti Bruno Scherrer
references.title: On the rate of convergence and error bounds for LSTD (λ)
references.venue: In International Conference on Machine Learning,
references.authors: Samuele Tosatto Matteo Pirotta Carlo D’Eramo Marcello Restelli
references.title: Boosted fitted Q-iteration
references.venue: In International Conference on Machine Learning,
references.authors: Hado van Hasselt Arthur Guez David Silver
references.title: Deep reinforcement learning with double Qlearning
references.venue: In AAAI Conference on Artificial Intelligence,
references.authors: John Von Neumann Oskar Morgenstern
references.title: Theory of games and economic behavior
references.authors: Ziyu Wang Tom Schaul Matteo Hessel Hado Hasselt Marc Lanctot Nando Freitas
references.title: Dueling network architectures for deep reinforcement learning
references.venue: In International Conference on Machine Learning,
references.authors: Chen-Yu Wei Yi-Te Hong Chi-Jen Lu
references.title: Online reinforcement learning in stochastic games
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Gilad Yehudai Ohad Shamir
references.title: On the power and limitations of random features for understanding neural networks
references.venue: arXiv preprint arXiv:1904.00687,
references.authors: Kaiqing Zhang Zhuoran Yang Han Liu Tong Zhang Tamer Başar
references.title: Finite-sample analyses for fully decentralized multi-agent reinforcement learning
references.venue: arXiv preprint arXiv:1812.02783,
references.authors: Shangtong Zhang Richard S Sutton
references.title: A deeper look at experience replay
references.venue: arXiv preprint arXiv:1712.01275,
references.authors: Difan Zou Yuan Cao Dongruo Zhou Quanquan Gu
references.title: Stochastic gradient descent optimizes over-parameterized deep relu networks
references.venue: arXiv preprint arXiv:1811.08888,
references.authors: Du
references.title: overparametrized, (stochastic) gradient descent converges to the global minima of the empirical function. Moreover, the generalization error of the obtained neural network can also be established. The intuition behind these results is that, when the neural network is overparametrized, it behaves similar to the random feature model (Rahimi
references.venue: Allen-Zhu et al. (2018a;b); Jacot et al
references.authors: Cao Gu
references.title: Yehudai & Shamir (2019) and the references therein. Also see Fan et al. (2019) for a detailed survey. In the following, we make an initial attempt in providing a unified statistical and computational analysis of DQN. In the following, we consider the reinforcement learning problem with the state space S = [0, 1] and a finite action space A. To simplify the notation, we represent action a using one-hot embedding
references.authors: Du
references.title: 2019), when m is sufficiently large, the overall effect of the scaled indicators
references.authors: Mnih
references.title: Under review as a conference paper at ICLR 2020 C RELATED WORK There is a huge literature in deep reinforcement learning, where algorithms are based on Q-learning or policy gradient (Sutton et al., 2000). We refer the reader to Arulkumaran et al. (2017) for a survey of the recent developments of DRL
references.venue: In addition,
references.authors: Schaul
references.title: 2017) study the effect of experience replay and propose various modifications. In addition, our work is closely related to the literature on batch reinforcement learning
references.venue: (Lange et al.,
references.authors: Farahmand
references.title: 2016) study the performance of LSPI and BRM when the value function belongs to a reproducing kernel Hilbert space. However, we study the fitted Q-iteration algorithm, which is a batch RL counterpart of DQN. The fitted Q-iteration algorithm is proposed in Ernst et al
references.authors: Munos Szepesvári
references.title: regressors. However, their results are not applicable to ReLU networks due to the huge capacity of deep neural networks. Furthermore, various extensions of FQI are studied in Antos et al. (2008a); Farahmand et al
references.authors: Prasad
references.title: The Minimax-Q learning is proposed by Littman (1994), which is an online algorithm that is an extension Q-learning. Subsequently, for Markov games, various online algorithms are also proposed with theoretical guarantees. These work consider either the tabular case or linear function approximation
references.venue: Pérolat et al
references.authors: Zhang
references.title: Pérolat et al
references.venue: Perolat et al
references.authors: Bartlett
references.title: the networks parameters and establish capacity bounds based upon these norms
references.venue: Schmidt-Hieber
references.title: νQ(· | s) solves the zero-sum matrix game based on Q(s
sections.text: Despite the great empirical success of deep reinforcement learning, its theoretical foundation is less well understood. In this work, we make the first attempt to theoretically understand the deep Q-network (DQN) algorithm (Mnih et al., 2015) from both algorithmic and statistical perspectives. In specific, we focus on the fitted Q iteration (FQI) algorithm with deep neural networks, which is a slight simplification of DQN that captures the tricks of experience replay and target network used in DQN. Under mild assumptions, we establish the algorithmic and statistical rates of convergence for the action-value functions of the iterative policy sequence obtained by FQI. In particular, the statistical error characterizes the bias and variance that arise from approximating the action-value function using deep neural network, while the algorithmic error converges to zero at a geometric rate. As a byproduct, our analysis provides justifications for the techniques of experience replay and target network, which are crucial to the empirical success of DQN. Furthermore, as a simple extension of DQN, we propose the Minimax-DQN algorithm for zero-sum Markov game with two players, which is deferred to the appendix due to space limitations.
sections.heading: 1 INTRODUCTION
sections.text: Reinforcement learning (RL) attacks the multi-stage decision-making problems by interacting with the environment and learning from the experiences. With the breakthrough in deep learning, deep reinforcement learning (DRL) demonstrates tremendous success in solving highly challenging problems, such as the game of Go (Silver et al., 2016; 2017), robotics (Kober & Peters, 2012), and dialogue systems (Chen et al., 2017). In DRL, the value or policy functions are often represented as deep neural networks and the related deep learning techniques can be readily applied. For example, deep Q-network (DQN) (Mnih et al., 2015), asynchronous advantage actor-critic (A3C) and (Mnih et al., 2016) demonstrate superhuman performance in various applications and become standard algorithms for artificial intelligence.
  Despite its great empirical success, there exists a gap between the theory and practice of DRL. In particular, most existing theoretical work on reinforcement learning focuses on the tabular case where the state and action spaces are finite, or the case where the value function is linear. Under these restrictive settings, the algorithmic and statistical perspectives of reinforcement learning are well-understood via the tools developed for convex optimization and linear regression. However, in presence of nonlinear function approximators such as deep neural network, the theoretical analysis of reinforcement learning becomes intractable as it involves solving a highly nonconvex statistical optimization problem.
  To bridge such a gap in DRL, we make the first attempt to theoretically understand DQN, which can be cast as an extension of the classical Q-learning algorithm (Watkins & Dayan, 1992) that uses deep neural network to approximate the action-value function. Although the algorithmic and statistical properties of the classical Q-learning algorithm are well-studied, theoretical analysis of DQN is highly challenging due to its differences in the following two aspects.
  First, in online gradient-based temporal-difference reinforcement learning algorithms, approximating the action-value function often leads to instability. Baird (1995) proves that this is the case even with linear function approximation. The key technique to achieve stability in DQN is experience replay (Lin, 1992; Mnih et al., 2015). In specific, a replay memory is used to store the trajectory of the Markov decision process (MDP). At each iteration of DQN, a mini-batch of states, actions, rewards, and next states are sampled from the replay memory as observations to train the Q-network, which approximates the action-value function. The intuition behind experience replay is to achieve stability by breaking the temporal dependency among the observations used in the training of the deep neural network.
  Second, in addition to the aforementioned Q-network, DQN uses another neural network named target network to obtain an unbiased estimator of the mean-squared Bellman error used in training the Q-network. The target network is synchronized with the Q-network after each period of iterations, which leads to a coupling between the two networks. Moreover, even if we fix the target network and focus on updating the Q-network, the subproblem of training a neural network still remains less well-understood in theory.
  In this paper, we focus on a slight simplification of DQN, which is amenable to theoretical analysis while fully capturing the above two aspects. In specific, we simplify the technique of experience replay with an independence assumption, and focus on deep neural networks with rectified linear units (ReLU) (Nair & Hinton, 2010) and large batch size. Under this setting, DQN is reduced to the neural fitted Q-iteration (FQI) algorithm (Riedmiller, 2005) and the technique of target network can be cast as the value iteration. More importantly, by adapting the approximation results for ReLU networks to the analysis of Bellman operator, we establish the algorithmic and statistical rates of convergence for the iterative policy sequence obtained by DQN. As shown in the main results in §3, the statistical error characterizes the bias and variance that arise from approximating the action-value function using neural network, while the algorithmic error geometrically decays to zero as the number of iteration goes to infinity.
  Our contribution is two-fold. First, we establish the algorithmic and statistical errors of the neural FQI algorithm, which can be viewed as a slight simplification of DQN. Under mild assumptions, our results show that the proposed algorithm obtains a sequence of Q-networks that geometrically converges to the optimal action-value function up to an intrinsic statistical error induced by the approximation bias of ReLU network and finite sample size. Second, as a byproduct, our analysis justifies the techniques of experience replay and target network used in DQN, where the latter can be viewed as the value iteration. In addition, we also extend our algorithm to zero-sum Markov games. Due to space limit, we defer these results to the appendix.
  Notation. For a measurable space with domain S, we denote by B(S, V ) the set of measurable functions on S that are bounded by V in absolute value. Let P(S) be the set of all probability measures over S. For any ν ∈ P(S) and any measurable function f : S → R, we denote by ‖f‖p,ν the `p-norm of f with respect to measure ν for p ≥ 1. In addition, for simplicity, we write ‖f‖ν for ‖f‖2,ν . In addition, let {f(n), g(n)}n≥1 be two positive series. We write f(n) . g(n) if there exists a constant C such that f(n) ≤ C · g(n) for all n larger than some n0 ∈ N. In addition, we write f(n) g(n) if f(n) . g(n) and g(n) . f(n).
sections.heading: 2 BACKGROUND
sections.text: In this section, we introduce the background. We first lay out the formulation of the reinforcement learning problem, and then define the family of ReLU neural networks.
sections.heading: 2.1 REINFORCEMENT LEARNING
sections.text: A discounted Markov decision process is defined by a tuple (S,A, P,R, γ). Here S is the set of all states, which can be countable or uncountable, A is the set of all actions, P : S × A → P(S)
  is the Markov transition kernel, R : S × A → P(R) is the distribution of the immediate reward, and γ ∈ (0, 1) is the discount factor. In specific, upon taking any action a ∈ A at any state s ∈ S, P (· |s, a) defines the probability distribution of the next state and R(· |s, a) is the distribution of the immediate reward. Moreover, for regularity, we further assume that S is a compact subset of Rd which can be infinite, A = {a1, a2, . . . , aM} has finite cardinality M , and the rewards are uniformly bounded by Rmax, i.e., R(· |s, a) is supported on [−Rmax, Rmax] for any s ∈ S and a ∈ A.
  A policy π : S → P(A) for the MDP maps any state s ∈ S to a probability distribution π(· | s) over A. For policy π, the corresponding value function V π : S → R is defined as the cumulative discounted reward obtained by when the actions are executed according to π, that is,
  V π(s) = E [ ∞∑ t=0 γt ·Rt ∣∣∣∣S0 = s,At ∼ π(· |St), St+1 ∼ P (· |St, At)]. (2.1)
  Similarly, the action-value function Qπ : S ×A → R is defined as Qπ(s, a) = E [ ∞∑ t=0 γt ·Rt ∣∣∣∣S0 = s,A0 = a,At ∼ π(· |St), St+1 ∼ P (· |St, At)]. (2.2)
  For any given action-value function Q : S × A → R, define the one-step greedy policy πQ as any policy that selects the action with the largest Q-value, that is, for any s ∈ S, πQ(· |s) satisfies
  πQ(a | s) = 0 if Q(s, a) 6= max a′∈A
  Q(s, a′). (2.3)
  Moreover, we define operator Pπ by (PπQ)(s, a) = E [ Q(S′, A′) ∣∣S′ ∼ P (· | s, a), A′ ∼ π(· |S′)], (2.4) and define the Bellman operator Tπ by (TπQ)(s, a) = r(s, a) + γ · (PπQ)(s, a), where r(s, a) =∫ rR(dr | s, a) is the expected reward obtained at state s when taking action a. Then it can be verified that Qπ is the unique fixed point of Tπ .
  The goal of reinforcement learning is to find the optimal policy, which achieves the largest cumulative reward. To characterize optimality, we define optimal action-value function Q∗ as
  Q∗(s, a) = sup π Qπ(s, a), (2.5)
  where the supremum is taken over all policies. Based on Q∗, we define the optimal policy π∗ as any policy that is greedy with respect to Q∗. It can be shown that Q∗ = Qπ ∗ . Finally, we define the Bellman optimality operator T via
  (TQ)(s, a) = r(s, a) + γ · E [ max a′∈A Q(S′, a′) ∣∣S′ ∼ P (· | s, a)]. (2.6)
  Then we have Bellman optimality equation TQ∗ = Q∗.
sections.heading: 2.2 DEEP NEURAL NETWORK
sections.text: We study the performance of DQN with rectified linear unit (ReLU) activation function σ(u) = max(u, 0). For any positive integer L and {dj}L+1j=0 ⊆ N, a ReLU network f : Rd0 → RdL+1 with L hidden layers and width {dj}L+1j=0 is of form
  f(x) = WL+1σ(WLσ(WL−1 . . . σ(W2σ(W1x+ v1) + v2) . . . vL−1) + vL), (2.7)
  where W` ∈ Rd`×d`−1 and v` ∈ Rd` are the weight matrix and the shift vector in the `-th layer, respectively. Here we apply σ to to each entry of its argument in (2.7). In deep learning, the network structure is fixed, and the goal is to learn the network parameters (weights) {W`, v`}`∈[L+1] with the convention that vL+1 = 0. For deep neural networks, the number of parameters greatly exceeds the input dimension d0. To restrict the model class, we focus on the class of ReLU networks where most parameters are zero.
  Definition 2.1 (Sparse ReLU Network). For any L, s ∈ N, {dj}L+1j=0 ⊆ N , and V > 0, the family of sparse ReLU networks bounded by V with L hidden layers, network width d, and weight sparsity s is defined as
  F(L, {dj}L+1i=0 , s, V ) = { f : max
  `∈[L+1] ‖W̃`‖∞ ≤ 1, L+1∑ `=1 ‖W̃`‖0 ≤ s, max j∈[dL+1] ‖fj‖∞ ≤ V } , (2.8)
  where we denote (W`, v`) by W̃`. Moreover, f in (2.8) is expressed as in (2.7), and fj is the j-th component of f .
  Here we focus on functions that are uniformly bounded because the value functions in (2.1) and (2.2) are always bounded by Vmax = Rmax/(1− γ). In the sequel, we write F(L, {dj}L+1j=0 , s, Vmax) as F(L, {dj}L+1j=0 , s) to simplify the notation. In addition, we restrict the networks weights to be sparse, i.e., s is much smaller compared with the total number of parameters. Such an assumption implies that the network has sparse connections, which are useful for applying deep learning in memory-constrained situations such as mobile devices (Han et al., 2015; Liu et al., 2015).
  Moreover, we introduce the notion of Hölder smoothness as follows, which is a generalization of Lipschitz continuity, and is widely used to characterize the regularity of functions.
  Definition 2.2 (Hölder Smooth Function). Let D be a compact subset of Rr, where r ∈ N. We define the set of Hölder smooth functions on D as
  Cr(D, β,H) = { f : D → R : ∑ α : |α|<β ‖∂αf‖∞ + ∑ α : ‖α‖1=bβc sup x,y∈D,x 6=y |∂αf(x)− ∂α(y)| ‖x− y‖β−bβc∞ ≤ H } ,
  where β > 0 and H > 0 are parameters and bβc is the largest integer no greater than β. In addition, here we use the multi-index notation by letting α = (α1, . . . , αr)> ∈ Nr, and ∂α = ∂α1 . . . ∂αr .
  Finally, we conclude this section by defining functions that can be written as a composition of multiple Hölder functions, which captures complex mappings in real-world applications such as multi-level feature extraction.
  Definition 2.3 (Composition of Hölder Functions). Let q ∈ N and {pj}j∈[q] ⊆ N be integers, and let {aj , bj}j∈[q] ⊆ R such that aj < bj j ∈ [q]. Moreover, let gj : [aj , bj ]pj → [aj+1, bj+1]pj+1 be a function, ∀j ∈ [q]. Let (gjk)k∈[pj+1] be the components of gj , and we assume that each gjk is Hölder smooth, and depends on at most tj of its input variables, where tj could be much smaller than pj , i.e., gjk ∈ Ctj ([aj , bj ]tj , βj , Hj). Finally, we denote by G({pj , tj , βj , Hj}j∈[q]) the family of functions that can be written as compositions of {gj}j∈[q], with the convention that pq+1 = 1. That is, for any f ∈ G({pj , tj , βj , Hj}j∈[q]), we can write
  f = gq ◦ gq−1 ◦ . . . ◦ g2 ◦ g1,
  with gjk ∈ Ctj ([aj , bj ]tj , βj , Hj) for each k ∈ [pj+1] and j ∈ [q].
sections.heading: 3 UNDERSTANDING DEEP Q-NETWORK
sections.text: In the DQN algorithm, a deep neural network Qθ : S × A → R is used to approximate Q∗, where θ is the parameter. For completeness, we state the DQN as Algorithm 2 in §A. As shown in the experiments in Mnih et al. (2015), two tricks are pivotal for the success of DQN.
  First, DQN use the trick of experience replay (Lin, 1992). Specifically, at each time t, we store the transition (St, At, Rt, St+1) into the replay memoryM, and then sample a minibatch of independent samples fromM to train the neural network via stochastic gradient descent. Since the trajectory of MDP has strong temporal correlation, the goal of experience replay is to obtain uncorrelated samples, which yields accurate gradient estimation for the stochastic optimization problem.
  Another trick is to use a target network Qθ? with parameter θ?. Specifically, with independent samples {(si, ai, ri, s′i)}i∈[n] from the replay memory, to update the parameter θ of the Q-network,
  we compute the target Yi = ri + γ ·maxa∈AQθ?(s′i, a), and update θ by the gradient of
  L(θ) = 1
  n n∑ i=1 [Yi −Qθ(si, ai)]2. (3.1)
  Whereas parameter θ? is updated once every Ttarget steps by letting θ? = θ. That is, the target network is hold fixed for Ttarget steps, and is thus updated in a slower pace.
  To demystify DQN, it is crucial to understand the role played by these two tricks. For experience replay, in practice, the replay memory size is usually very large. For example, the replay memory size is 106 in Mnih et al. (2015). Moreover, DQN use the -greedy policy, which enables exploration over S ×A. Thus, when the replay memory is large, experience replay is close to sampling independent transitions from an explorative policy. This reduces the variance of the ∇L(θ), which is used to update θ.
  Thus, experience replay stabilizes the training of DQN, which benefits the algorithm in terms of computation. To understand the statistical property of DQN, we replace the experience replay by sampling independent transitions from a fixed distribution σ ∈ P(S×A). That is, instead of sampling from the replay memory, we sample i.i.d. observations {(Si, Ai)}i∈[n] from σ. Moreover, for any i ∈ [n], let Ri and S′i be the immediate reward and the next state when taking action Ai at state Si. Under this setting, we have E(Yi |Si, Ai) = (TQθ?)(Si, Ai), where Qθ? is the target network, which, as we show as follows, is motivated from a statistical consideration.
  Let us first neglect the target network and set θ? = θ. Using bias-variance decomposition, the the expected value of L(θ) in (3.1) is
  E [ L(θ) ] = ‖Qθ − TQθ‖2σ + E {[ Y1 − (TQθ)(S1, A1) ]2} . (3.2)
  Here the first term in (3.2) is known as the mean-squared Bellman error (MSBE), and the second term is the variance of Y1. Whereas L(θ) can be viewed as the empirical version of the MSBE, which has bias E{[Y1 − (TQθ)(S1, A1)]2} that also depends on θ. Thus, without the target network, minimizing L(θ) can be drastically different from minimizing the MSBE.
  To resolve this problem, we use a target network in (3.1), which has expectation E [ L(θ) ] = ‖Qθ − TQθ∗‖2σ + E {[ Y1 − (TQθ∗)(S1, A1) ]2} ,
  where the variance of Y1 does not depend on θ. Thus, minimizing L(θ) is close to solving
  minimize θ∈Θ
  ‖Qθ − TQθ?‖2σ, (3.3)
  where Θ is the parameter space. Note that in DQN we hold θ? still and update θ for Ttarget steps. When Ttarget is sufficiently large and we neglect the fact that the objective in (3.3) is nonconvex, we would update θ by the minimizer of (3.3) for fixed θ?.
  Therefore, in the ideal case, DQN aims to solve the minimization problem (3.3) with θ? fixed, and then update θ? by the minimizer θ. Interestingly, this view of DQN offers a statistical interpretation of the target network. In specific, if {Qθ : θ ∈ Θ} is sufficiently large such that it contains TQθ? , then (3.3) has solution Qθ = TQθ? , which can be viewed as one-step of value iteration (Sutton & Barto, 2011) for neural networks. In addition, in the sample setting, Qθ? is used to construct {Yi}i∈[n], which serve as the response in the regression problem defined in (3.1), with (TQθ?) being the regression function.
  Furthermore, turning the discussion above into a realizable algorithm, we obtain the neural fitted Q-iteration (FQI) algorithm, which generates a sequence of value functions. Specifically, let F be a class of function defined on S × A. In the k-th iteration of FQI, let Q̃k be current estimate of Q∗. Similar to (3.1) and (3.3), we define Yi = Ri + γ ·maxa∈A Q̃k(S′i, a), and update Q̃k by
  Q̃k+1 = argmin f∈F
  1
  n n∑ i=1 [ Yi − f(Si, Ai) ]2 . (3.4)
  This gives the fitted-Q iteration algorithm, which is stated in Algorithm 1.
  When F is the family of neural networks, Algorithm 1 is known as the neural FQI, which is proposed in Riedmiller (2005). Thus, we can view neural FQI as an modification of DQN, where we replace experience replay by sampling from a fixed distribution σ, so as to understand its the statistical property. As a byproduct, such a modification naturally justifies the trick of target network in DQN. In addition, note that the optimization problem in (3.4) appears in each iteration of FQI, which is nonconvex when neural networks are used. However, since we focus solely on the statistical aspect, we make the assumption that the global optima of (3.4) can be reached, which is also contained F . Interestingly, a recent line of research on deep learning (Du et al., 2018b;a; Zou et al., 2018; Chizat & Bach, 2018; Allen-Zhu et al., 2018a;b; Jacot et al., 2018; Cao & Gu, 2019; Arora et al., 2019; Ma et al., 2019; Mei et al., 2019; Yehudai & Shamir, 2019) has established global convergence of gradientbased algorithms for empirical risk minimization when the neural networks are overparametrized. We provide more discussions on the computation aspect in §B. Moreover, we make the i.i.d. assumption in Algorithm 1 to simplify the analysis. Antos et al. (2008b) study the performance of fitted value iteration with fixed data used in the regression sub-problems repeatedly, where the data is sampled from a single trajectory based on a fixed policy such that the induced Markov chain satisfies certain conditions on the mixing time. Using similar analysis as in Antos et al. (2008b), our algorithm can also be extended to handled fixed data that is collected beforehand.
  Algorithm 1 Fitted Q-Iteration Algorithm Input: MDP (S,A, P,R, γ), function class F , sampling distribution σ, number of iterations K, number of samples n, the initial estimator Q̃0. for k = 0, 1, 2, . . . ,K − 1 do
  Sample i.i.d. observations {(Si, Ai), i ∈ [n]} from σ, obtain Ri ∼ R(· |Si, Ai) and S′i ∼ P (· |Si, Ai). Compute Yi = Ri + γ ·maxa∈A Q̃k(S′i, a). Update the action-value function:
  Q̃k+1 ← argmin f∈F
  1
  n n∑ i=1 [ Yi − f(Si, Ai) ]2 .
  end for Define policy πK as the greedy policy with respect to Q̃K . Output: An estimator Q̃K of Q∗ and policy πK .
sections.heading: 4 THEORETICAL RESULTS
sections.text: We establish statistical guarantees for DQN with ReLU networks. Specifically, let QπK be the action-value function corresponding to πK , which is returned by Algorithm 1. In the following, we obtain an upper bound for ‖QπK −Q∗‖1,µ, where µ ∈ P(S ×A) is allowed to be different from ν. In addition, we assume that the state space S is a compact subset in Rr and the action space A is finite. Without loss of generality, we let S = [0, 1]r hereafter, where r is a fixed integer. To begin with, we first specify the function class F in Algorithm 1.
  Definition 4.1 (Function Classes). Following Definition 2.1, let F(L, {dj}L+1j=0 , s) be the family of sparse ReLU networks defined on S with d0 = r and dL+1 = 1. Then we define F0 by
  F0 = { f : S ×A → R : f(·, a) ∈ F(L, {dj}L+1i=0 , s) for any a ∈ A } . (4.1)
  In addition, let G({pj , tj , βj , Hj}j∈[q]) be set of composition of Hölder smooth functions defined on S ⊆ Rr. Similar to F0, we define a function class G0 as
  G0 = { f : S ×A → R : f(·, a) ∈ G({pj , tj , βj , Hj}j∈[q]) for any a ∈ A } . (4.2)
  By this definition, for any function f ∈ F0 and any action a ∈ A, f(·, a) is a ReLU network defined on S, which is standard for Q-networks. Moreover, G0 contains a broad family of smooth functions on S ×A. In the following, we make a mild assumption on F0 and G0. Assumption 4.2. We assume that for any f ∈ F0, we have Tf ∈ G0, where T is the Bellman optimality operator defined in (2.6). That is, for any f ∈ F and any a ∈ A, (Tf)(s, a) can be written as compositions of Hölder smooth functions as a function of s ∈ S.
  We remark that this assumption holds when the MDP satisfies some smoothness conditions. For any state-action pair (s, a) ∈ S ×A, let P (· | s, a) be the density of the next state. By the definition of the Bellman optimality operator in (2.6), we have
  (Tf)(s, a) = r(s, a) + γ · ∫ S [ max a′∈A f(s′, a′) ] · P (s′ | s, a)ds′. (4.3)
  For any s′ ∈ S and a ∈ A, we define functions g1, g2 by letting g1(s) = r(s, a) and g2(s) = P (s′ | s, a). Suppose both g1 and g2 are Hölder smooth functions on S = [0, 1]r with parameters β and H . Since ‖f‖∞ ≤ Vmax, by changing the order of integration and differentiation with respect to s in (4.3), we obtain that function s→ (Tf)(s, a) belongs to the Hölder class Cr(S, β,H ′) with H ′ = H(1 + Vmax). Furthermore, in the more general case, suppose for any fixed a ∈ A, we can write P (s′ | s, a) as h1[h2(s, a), h3(s′)], where h2 : S → Rr1 , and h3 : S → Rr2 can be viewed as feature mappings, and h1 : Rr1+r2 → R is a bivariate function. We define function h4 : Rr1 → R by
  h4(u) = ∫ S [ max a′∈A f(s′, a′) ] h1[u, h3(s ′)]ds′.
  Then by (4.3) we have (Tf)(s, a) = g1(s) + h4 ◦ h2(s, a). Then Assumption 4.2 holds if h4 is Hölder smooth and both g1 and h2 can be represented as compositions of Hölder functions. Thus, Assumption 4.2 holds if both the reward function and the transition density of the MDP are sufficiently smooth.
  Moreover, even when the transition density is not smooth, we could also expect Assumption 4.2 to hold. Consider the extreme case where the MDP has deterministic transitions, that is, the next state s′ is a function of s and a, which is denoted by s′ = h(s, a). In this case, for any ReLU network f , we have (Tf)(s, a) = r(s, a) + γ ·maxa′∈A f [h(s, a), a′]. Since∣∣∣max
  a′∈A f(s1, a ′)−max a′∈A
  f(s2, a ′) ∣∣∣ ≤ max
  a′∈A ∣∣f(s1, a′)− f(s2, a′)∣∣ for any s1, s2 ∈ S, and network f(·, a) is Lipschitz continuous for any fixed a ∈ A, function m1(s) = maxa′ f(s, a
  ′) is Lipschitz on S. Thus, for any fixed a ∈ A, if both g1(s) = r(s, a) and m2(s) = h(s, a) are compositions of Hölder functions, so is (Tf)(s, a) = g1(s) + m1 ◦ m2(s). Therefore, even if the MDP has deterministic dynamics, if both the reward function r(s, a) and the transition function h(s, a) are sufficiently nice, Assumption 4.2 still holds true.
  In the following, we define the concentration coefficients, which measures the similarity between two probability distributions under the MDP. Assumption 4.3 (Concentration Coefficients). Let ν1, ν2 ∈ P(S ×A) be two probability measures that are absolutely continuous with respect to the Lebesgue measure on S × A. Let {πt}t≥1 be a sequence of policies. Suppose the initial state-action pair (S0, A0) of the MDP has distribution ν1, and we take actionAt according to policy πt. For any integerm, we denote by PπmPπm−1 · · ·Pπ1ν1 the distribution of (Sm, Am). Then we define the m-th concentration coefficient as
  κ(m; ν1, ν2) = sup π1,...,πm
  [ Eν2 ∣∣∣∣d(PπmPπm−1 · · ·Pπ1ν1)dν2 ∣∣∣∣2]1/2, (4.4)
  where the supremum is taken over all possible policies.
  Furthermore, let σ be the sampling distribution in Algorithm 1 and let µ be a fixed distribution on S ×A. We assume that there exists a constant φµ,σ <∞ such that
  (1− γ)2 · ∑ m≥1 γm−1 ·m · κ(m;µ, σ) ≤ φµ,σ, (4.5)
  where (1− γ)2 in (4.5) is a normalization term, since ∑ m≥1 γ m−1 ·m = (1− γ)−2.
  By definition, concentration coefficients in (4.4) quantifies the similarity between ν2 and the distribution of the future states of the MDP when starting from ν1. Moreover, (4.5) is a standard assumption in the literature. See, e.g., Munos & Szepesvári (2008); Lazaric et al. (2016); Scherrer et al. (2015); Farahmand et al. (2010; 2016). This assumption holds for large class of systems MDPs and specifically for MDPs whose top-Lyapunov exponent is finite. See Munos & Szepesvári (2008); Antos et al. (2007) for more detailed discussions on this assumption.
  Now we are ready to present the main theorem.
  Theorem 4.4. Under Assumptions 4.2 and 4.3, letF0 be defined in (4.1) based on the family of sparse ReLU networks F(L∗, {d∗j} L∗+1 j=0 , s
  ∗) and let G0 be given in (4.2). Moreover, for any j ∈ [q− 1], we define β∗j = βj · ∏ `=j+1 min(β`, 1); let β ∗ q = 1. In addition, let α ∗ = maxj∈[q] tj/(2β ∗ j + tj). For the parameters of G0, we assume that there exists a constant ξ > 0 such that
  max j∈[q] tj ≤ ξ, ∑ j∈[q] log tj . (log n) ξ and max j∈[q] pj . (log n) ξ. (4.6)
  For the hyperparameters L∗, {d∗j} L∗+1 j=0 , and s ∗ of the ReLU network, we set d∗0 = 0 and d ∗ L∗+1 = 1. Moreover, we set L∗ . (log n)ξ ′ ,
  max j∈[q] {pj+1 · tj} · nα ∗ . min i∈[L∗] d∗j ≤ max j∈[L∗] d∗j . n ξ′ , and s∗ nα ∗ · (log n)ξ ′ (4.7)
  for some constant ξ′ > 0. For any K ∈ N, let QπK be the action-value function corresponding to policy πK , which is returned by Algorithm 1 based on function class F0. Then there exists constants ξ∗ and C such that
  ‖Q∗ −QπK‖1,µ ≤ C · φµ,σ · γ (1− γ)2 · |A| · (log n)ξ ∗ · n(α ∗−1)/2 + 4γK+1 (1− γ)2 ·Rmax. (4.8)
  This theorem implies that the statistical rate of convergence is the sum of a statistical error and an algorithmic error. The algorithmic error converges to zero in linear rate as the algorithm proceeds, whereas the statistical error reflects the fundamental difficulty of the problem. Thus, when the number of iterations satisfy
  K ≥ C ′ · [ log |A|+ (1− α∗) · log n ] / log(1/γ)
  iterations, whereC ′ is a sufficiently large constant, the algorithmic error is dominated by the statistical error. In this case, if we view both γ and φµ,σ as constants and ignore the polylogarithmic term, Algorithm 1 achieves error rate
  |A| · n(α ∗−1)/2 = |A| ·max j∈[q] n−β ∗ j /(2β ∗ j+tj), (4.9)
  which scales linearly with the capacity of the action space, and decays to zero when the n goes to infinity. Furthermore, the rates {n−β ∗ j /(2β ∗ j+tj)}j∈[q] in (4.9) recovers the statistical rate of nonparametric regression in `2-norm, whereas our statistical rate n(α ∗−1)/2 in (4.9) is the fastest among these nonparametric rates, which illustrates the benefit of compositional structure of G0.
  Furthermore, as a concrete example, we assume that both the reward function and the Markov transition kernel are Hölder smooth with smoothness parameter β. As stated below Assumption 4.2, for any f ∈ F0, we have (Tf)(·, a) ∈ Cr(S, β,H ′). Then Theorem 4.4 implies that Algorithm 1 achieves error rate |A| ·n−β/(2β+r) when K is sufficiently large. Since |A| is finite, this rate achieves the minimax-optimal statistical rate of convergence within the class of Hölder smooth functions defined on [0, 1]d (Stone, 1982) and thus cannot be further improved.
  In addition, as a simple extension of DQN, we propose the Minimax-DQN algorithm for zero-sum Markov game with two players. Specifically, in this setting, there are two players with action spaces A and B. The action-value function Q∗(s, a, b) : S ×A× B → R can be similarly defined, which correspond to the value obtained by a pair of policies that constitute the Nash equilibrium. MinimaxDQN differs from the original DQN mainly in the computation of target, which is obtained by solving
  a zero-sum matrix game via linear programming. Using similar proof technique, we establish both the algorithmic and statistical convergence rates of the action-value functions associated with the sequence of policies returned by the Minimax-DQN algorithm. Due to space limit, we defer the algorithm and its theory to §E.1 in the appendix.
sections.heading: A DEEP Q-NETWORK
sections.text: We are present the DQN algorithm for MDP in details, which is proposed by Mnih et al. (2015) and adapted here to discounted MDP. As shown in Algorithm 2 below, DQN features two key tricks that lead to its empirical success, namely, experience replay and target network.
  Algorithm 2 Deep Q-Network (DQN) Input: MDP (S,A, P,R, γ), replay memory M, number of iterations T , minibatch size n, exploration probability ∈ (0, 1), a family of deep Q-networks Qθ : S ×A → R, an integer Ttarget for updating the target network, and a sequence of stepsizes {αt}t≥0. Initialize the replay memoryM to be empty. Initialize the Q-network with random weights θ. Initialize the weights of the target network with θ? = θ. Initialize the initial state S0. for t = 0, 1, . . . , T do
  With probability , choose At uniformly at random from A, and with probability 1− , choose At such that Qθ(St, At) = maxa∈AQθ(St, a). Execute At and observe reward Rt and the next state St+1. Store transition (St, At, Rt, St+1) inM. Experience replay: Sample random minibatch of transitions {(si, ai, ri, s′i)}i∈[n] fromM. For each i ∈ [n], compute the target Yi = ri + γ ·maxa∈AQθ?(s′i, a). Update the Q-network: Perform a gradient descent step
  θ ← θ − αt · 1
  n ∑ i∈[n] [ Yi −Qθ(si, ai) ] · ∇θQθ(si, ai).
  Update the target network: Update θ? ← θ every Ttarget steps. end for Define policy π as the greedy policy with respect to Qθ. Output: Action-value function Qθ and policy π.
sections.heading: B COMPUTATIONAL ASPECT OF DQN
sections.text: Recall that in Algorithm 1 we assume that the global optima of the nonlinear least-squares problem in (3.1) is be obtained in each iteration. We make such assumption as our focus is on the statistical analysis. In terms of optimization, it has been shown recently that, when the neural network is overparametrized, (stochastic) gradient descent converges to the global minima of the empirical function. Moreover, the generalization error of the obtained neural network can also be established. The intuition behind these results is that, when the neural network is overparametrized, it behaves similar to the random feature model (Rahimi & Recht, 2008). See, e.g., Li & Liang (2018); Du et al. (2018b;a); Zou et al. (2018); Chizat & Bach (2018); Allen-Zhu et al. (2018a;b); Jacot et al. (2018); Cao & Gu (2019); Arora et al. (2019); Ma et al. (2019); Mei et al. (2019); Yehudai & Shamir (2019) and the references therein. Also see Fan et al. (2019) for a detailed survey. In the following, we make an initial attempt in providing a unified statistical and computational analysis of DQN.
  In the following, we consider the reinforcement learning problem with the state space S = [0, 1]r and a finite action space A. To simplify the notation, we represent action a using one-hot embedding and thus identify it as an element in {0, 1}|A|. Thus, we can pack the state s and the action a together and obtain a vector (s, a) in Rd, where we denote r + |A| by d.
  We represent the Q-network by the family of two-layer neural networks
  Q ( s, a; b,W ) =
  1√ m m∑ j=1 bj · σ[W>j (s, a)], ∀(s, a) ∈ S ×A. (B.1)
  Here m is the number of neurons, bj ∈ R and Wj ∈ Rd for all j ∈ [m], and σ(u) = max{u, 0} is the ReLU activation function. Here b = (b1, . . . , bm)> ∈ Rm and W = (W1, . . . ,Wm) ∈ Rd×m are the weights of the neural network. Then, in the k-th iteration of Algorithm 1, the optimization problem in (3.1) becomes
  minimize b,W
  1
  2n n∑ i=1 [ Yi −Q(Si, Ai; b,W ) ]2 , (B.2)
  where Yi = Ri+γ ·maxa∈A Q̃k(S′i, a) is the target and Q̃k is the Q-network computed in the previous iteration. Notice that this problem is the least-squares regression with two-layer neural networks in the overparametrized setting. We solve the optimization in (B.2) via gradient descent. Specifically, we initialize. the parameters via bj i.i.d.∼ Unif({−1, 1}) and Wj i.i.d.∼ N(0, Id/d), where Id is the identity matrix in Rd. Moreover, for ease of presentation, during training we keeping {b1, . . . , bm} fixed as the random initialization and only optimize over W . Moreover, let W (0) ∈ Rd×m be the initialization ofW . We restrict the weightW to a Frobenius ball centered atW (0) with radiusB > 0, i.e., we define
  BB = { W ∈ Rd×m : ‖W −W (0)‖fro ≤ B } , (B.3)
  where B is a sufficiently large constant. Thus, the problem in (B.2) is transformed into
  minimize W∈BB
  Ln(W ) = 1
  2n n∑ i=1 [ Yi −Q(Si, Ai; b,W ) ]2 , (B.4)
  where b is fixed to the initial value. We solve this optimization problem via projected gradient descent, which generates a sequence of weights {W (t)}t≥0 ⊆ BB satisfying
  W (t+ 1) = ΠBB
  [ W (t)− η
  n n∑ i=1 [ Yi −Q ( Si, Ai; b,W (t) )] · ∇WQ ( Si, Ai; b,W (t) )] , (B.5)
  where ΠBB is the projection operator onto BB and η > 0 is the step size.
  To understand the convergence of the updates in (B.4), we utilize the fact that overparametrized two-layer neural networks behave similar to the random feature model. Specifically, notice that we have
  Q(s, a; b,W ) = 1√ m m∑ j=1 bj · 1{W>j (s, a) > 0} ·W>j (s, a), (B.6)
  ∇WjQ(s, a; b,W ) = 1√ m bj · 1{W>j (s, a) > 0}, ∀j ∈ [m]. (B.7)
  We define function class F (t)B,m = { Q(s, a) =
  1√ m m∑ j=1 bj · 1{Wj(t)>(s, a) > 0} ·W>j (s, a) : W ∈ BB } . (B.8)
  By (B.6) and (B.7), every Q ∈ F (t)B,m can be written as
  Q(s, a) = Q ( s, a; b,W (t) ) +
  1√ m m∑ j=1 bj · 1{Wj(t)>(s, a) > 0} · [Wj −Wj(t)]>(s, a)
  = Q ( s, a; b,W (t) ) + 〈 ∇WQ ( s, a; b,W (t) ) ,W −W (t) 〉 .
  Thus, F (t)B,m contains first-order approximations of Q ( s, a; b,W (t) ) . Furthermore, as shown in Du et al. (2018b;a); Arora et al. (2019), when m is sufficiently large, the overall effect of the scaled indicators {1/ √ m · 1{Wj(t)>(s, a) > 0} are well approximated by the indicators produced by the initial weights. That is, when m approaches infinity, for each fixed t, F (t)B,m in (B.8) is close to
  FB,m = { nQ(s, a) =
  1√ m m∑ j=1 bj · 1{Wj(0)>(s, a) > 0} ·W>j (s, a) : W ∈ BB } . (B.9)
  Notice that {φj(s, a) = 1/ √ m ·bj ·1{Wj(0)>(s, a) > 0} are i.i.d. random variables. Thus, function class FB,m is family of functions that can be written as combinations of random features, i.e.,
  FB,m = { Q(s, a) = Q ( s, a; b,W (0) ) + m∑ j=1 φj(s, a) >Wj : ‖W‖fro ≤ B } , (B.10)
  where we utilize the definition of BB . More importantly, when m goes to infinity, the empirical distribution of the random features {φj(s, a)}j∈[m] converges to its population distribution. We denote φ(·, ·;β,w) as the random feature, where β ∈ Unif({−1, 1}) and w ∼ N(Id/d). We denote µ as the joint distribution of β and w. Then, FB,m in (B.10) converges to a set F∗B given by
  F∗B = { Q(s, a) = Q0(s, a) + ∫ φ(s, a;β,w)>α(β,w) dµ(β,w), : ∫ ‖α(β,w)‖22 dµ(β,w) ≤ B2 } ,
  (B.11) where α is a function over {−1, 1} × Rd and Q0(s, a) = limm→∞Q ( s, a; b,W (0) ) .
  Furthermore, it can be shown that F∗B is a subset of a reproducing kernel Hilbert space (Rahimi & Recht, 2008)H generated by kernel
  K ( (s, a), (s′, a′) ) = EN(Id/d) [ 1{w>(s, a) > 0} · 1{w>(s′, a′) > 0}〈(s, a), (s′, a′)〉 ] . (B.12)
  Besides, the inner product induced by the RKHS norm between two functions
  f1 = ∫ φ(·, ·;β,w)>α1(β,w) dµ(β,w) and f2 = ∫ φ(·, ·;β,w)>α1(β,w) dµ(β,w)
  is given by 〈f1, f2〉H = ∫ 〈α1(β,w), α1(β,w)〉 dµ(β,w). Thus, F∗B given in (B.11) can be written a RKHS-norm ball
  F∗B = {Q = Q0 + f : ‖f‖H ≤ B}
  with radius B. As a result, when both m and n go to infinity, the population problem correspond to (B.2) becomes minimizeQ∈F∗B ‖Q − TQ̃k‖ 2 σ, whose solution is denoted by Q ? k+1. Therefore, utilizing the recent result in optimization for two-layer neural networks Arora et al. (2019), the Q-networks obtained by the projected gradient descent in (B.5) satisfy
  ‖Q(·, ·,W (t) ) −Q?k+1‖2σ . 1/ √ n (B.13)
  when both m and t are sufficiently large. That is, when the network is overparametrized, projected gradient descent produces a solution Q̃t+1 with O(1/ √ n) generalization error. Moreover, using inequality (a+ b)2 ≤ 2a2 + 2b2, we have
  ‖Q̃t+1 − TQ̃k‖2σ ≤ 2 · ‖Q̃t+1 −Q?k+1‖σ2 + 2‖Q?k+1 − TQ̃k‖2σ . 1/ √ n+ dist(F∗B , σ, T ),
  (B.14)
  where dist(F∗B , σ, T ) is defined as
  dist(F∗B , σ, T ) = inf f∈F∗B sup g∈F∗B ‖f − Tg‖2σ,
  which measures the approximation error of functions in the RKHS ball F∗B with respect the Bellman operator and the sampling distribution σ. Finally, combining (B.14) with the error propagation result in Theorem D.1, we obtain the error of neural-FQI with overparametrized two-layer neural networks.
sections.heading: C RELATED WORK
sections.text: There is a huge literature in deep reinforcement learning, where algorithms are based on Q-learning or policy gradient (Sutton et al., 2000). We refer the reader to Arulkumaran et al. (2017) for a survey of the recent developments of DRL. In addition, the DQN algorithm is first proposed in Mnih et al. (2015), which applies DQN to Artari 2600 games (Bellemare et al., 2013). The extensions of DQN include double DQN (van Hasselt et al., 2016), dueling DQN (Wang et al., 2016), deep recurrent Q-network (Hausknecht & Stone, 2015), and asynchronous DQN (Mnih et al., 2016). All of these algorithms are corroborated only by numerical experiments, without theoretical guarantees. Moreover, these algorithms not only inherit the tricks of experience replay and the target network proposed in the original DQN, but develop even more tricks to enhance the performance. Furthermore, recent work such as Schaul et al. (2016); Liu & Zou (2017); Zhang & Sutton (2017) study the effect of experience replay and propose various modifications.
  In addition, our work is closely related to the literature on batch reinforcement learning (Lange et al., 2012), where the goal is to estimate the value function given transition data. These problems are usually formulated into least-squares regression, for which various algorithms are proposed with finite-sample analysis. However, most existing work focus on the settings where the value function are approximated by linear functions. See Bradtke & Barto (1996); Boyan (2002); Lagoudakis & Parr (2003); Lazaric et al. (2016); Farahmand et al. (2010); Lazaric et al. (2012); Tagorti & Scherrer (2015) and the references therein for results of the least-squares policy iteration (LSPI) and Bellman residue minimization (BRM) algorithms. Beyond linear function approximation, a recent work Farahmand et al. (2016) study the performance of LSPI and BRM when the value function belongs to a reproducing kernel Hilbert space. However, we study the fitted Q-iteration algorithm, which is a batch RL counterpart of DQN. The fitted Q-iteration algorithm is proposed in Ernst et al. (2005), and Riedmiller (2005) propose the neural FQI algorithm. A finite-sample bound for FQI is established in Munos & Szepesvári (2008) for a large class of regressors. However, their results are not applicable to ReLU networks due to the huge capacity of deep neural networks. Furthermore, various extensions of FQI are studied in Antos et al. (2008a); Farahmand et al. (2009); Tosatto et al. (2017); Geist et al. (2019) to handle continuous actions space, ensemble learning, and entropy regularization.
  Furthermore, our work is also related to works that apply reinforcement learning to zero-sum Markov games. The Minimax-Q learning is proposed by Littman (1994), which is an online algorithm that is an extension Q-learning. Subsequently, for Markov games, various online algorithms are also proposed with theoretical guarantees. These work consider either the tabular case or linear function approximation. See, e.g., Bowling (2001); Conitzer & Sandholm (2007); Prasad et al. (2015); Wei et al. (2017); Pérolat et al. (2018); Srinivasan et al. (2018); Wei et al. (2017) and the references therein. In addition, batch reinforcement learning is also applied to zero-sum Markov games by Lagoudakis & Parr (2002); Perolat et al. (2015); Pérolat et al. (2016a;b); Zhang et al. (2018), which are closely related to our work. All of these works consider either linear function approximation or a general function class with bounded pseudo-dimension (Anthony & Bartlett, 2009). However, there results cannot directly imply finite-sample bounds for Minimax-DQN due to the huge capacity of deep neural networks.
  Finally, our work is also related a line of research on the model capacity of ReLU deep neural networks, which leads to understanding the generalization property of deep learning (Mohri et al., 2012; Kawaguchi et al., 2017). Specifically, Bartlett (1998); Neyshabur et al. (2015b;a); Bartlett et al. (2017a); Golowich et al. (2017); Liang et al. (2017) propose various norms computed from the networks parameters and establish capacity bounds based upon these norms. In addition, Maass (1994); Bartlett et al. (1999); Schmidt-Hieber (2017); Bartlett et al. (2017b); Klusowski & Barron (2016); Suzuki (2018); Bauer et al. (2019) study the Vapnik-Chervonenkis (VC) dimension of neural networks and Dziugaite & Roy (2017); Neyshabur et al. (2017a) establish the PAC-Bayes bounds for neural networks. Among these work, our work is more related to Schmidt-Hieber (2017); Suzuki (2018), which relate the VC dimension of the ReLU networks to a set of hyperparameters used to define the networks. Based on the VC dimension, they study the statistical error of nonparametric
  regression using ReLU networks. In sum, theoretical understanding of deep learning is pertinent to the study of DRL algorithms. See Kawaguchi et al. (2017); Neyshabur et al. (2017b); Fan et al. (2019) and the references therein for recent developments on theoretical analysis of the generalization property of deep learning.
sections.heading: D PROOF OF THE MAIN THEOREM
sections.text: In this section, we present a detailed proof of Theorem 4.4.
  Proof. The proof requires two key ingredients. First in Theorem D.1 we quantify how the error of action-value function approximation propagates through each iteration of Algorithm 1. Then in Theorem D.2 we analyze such one-step approximation error for ReLU networks.
  Theorem D.1 (Error Propagation). Recall that {Q̃k}0≤k≤K are the iterates of Algorithm 1. Let πK be the one-step greedy policy with respect to Q̃K , and let QπK be the action-value function corresponding to πK . Under Assumption 4.3, we have
  ‖Q∗ −QπK‖1,µ ≤ 2φµ,σγ
  (1− γ)2 · εmax +
  4γK+1
  (1− γ)2 ·Rmax, (D.1)
  where we define the maximum one-step approximation error εmax = maxk∈[K] ‖TQ̃k−1 − Q̃k‖σ. Here φµ,σ is a constant that only depends on the probability distributions µ and σ.
  Proof. See §F.1 for a detailed proof.
  In the sequel, we establish an upper bound for the one-step approximation error ‖TQ̃k−1 − Q̃k‖σ for each k ∈ [K]. Theorem D.2 (One-step Approximation Error). Let F ⊆ B(S ×A, Vmax) be a class of measurable functions on S×A that are bounded by Vmax = Rmax/(1−γ), and let σ be a probability distribution on S × A. Also, let {(Si, Ai)}i∈[n] be n i.i.d. random variables in S × A following σ. For each i ∈ [n], let Ri and S′i be the reward and the next state corresponding to (Si, Ai). In addition, for any fixed Q ∈ F , we define Yi = Ri + γ ·maxa∈AQ(S′i, a). Based on {(Xi, Ai, Yi)}i∈[n], we define Q̂ as the solution to the least-squares problem
  minimize f∈F
  1
  n n∑ i=1 [ f(Si, Ai)− Yi ]2 . (D.2)
  Meanwhile, for any δ > 0, let N (δ,F , ‖ · ‖∞) be the minimal δ-covering of F with respect to `∞-norm, and we denote by Nδ its cardinality. Then for any ∈ (0, 1] and any δ > 0, we have
  ‖Q̂− TQ‖2σ ≤ (1 + )2 · ω(F) + C · V 2max/(n · ) · logNδ + C ′ · Vmax · δ, (D.3)
  where C and C ′ are two positive absolute constants and ω(F) is defined as
  ω(F) = sup g∈F inf f∈F ‖f − Tg‖2σ. (D.4)
  Proof. See §F.2 for a detailed proof.
  To obtain an upper bound for ‖TQ̃k−1 − Q̃k‖σ as required in Theorem D.1, we set Q = Q̃k−1 in Theorem D.2. Then according to Algorithm 1, Q̂ defined in (D.2) becomes Q̃k. We set the function class F in Theorem D.2 to be the family of ReLU Q-networks F0 defined in (4.1). By setting = 1 and δ = 1/n in Theorem D.2, we obtain
  ‖Q̃k+1 − TQ̃k‖2σ ≤ 4 · ω(F0) + C · V 2max/n · logN0, (D.5)
  where C is a positive absolute constant and N0 = ∣∣N (1/n,F0, ‖ · ‖∞)∣∣ (D.6)
  is the 1/n-covering number of F0. In the subsequent proof, we establish upper bounds for ω(F0) defined in (D.4) and logN0, respectively. Recall that the family of composite Hölder smooth functions G0 is defined in (4.2). By Assumption 4.2, we have Tg ∈ G0 for any g ∈ F0. Hence, we have
  ω(F0) = sup f ′∈G0 inf f∈F0 ‖f − f ′‖2σ ≤ sup f ′∈G0 inf f∈F0 ‖f − f ′‖2∞, (D.7)
  where the right-hand side is the `∞-error of approximating the functions in G0 using the family of ReLU networks F0.
  By the definition of G0 in (4.2), for any f ∈ G0 and any a ∈ A, f(·, a) ∈ G({(pj , tj , βj , Hj)}j∈[q]) is a composition of Hölder smooth functions, that is, f(·, a) = gq ◦ · · · ◦ g1. Recall that, as defined in Definition 2.3, gjk is the k-th entry of the vector-valued function gj . Here gjk ∈ Ctj ([aj , bj ]tj , βj , Hj) for each k ∈ [pj+1] and j ∈ [q]. In the sequel, we construct a ReLU network to approximate f(·, a) and establish an upper bound of the approximation error on the right-hand side of (D.7). We first show that f(·, a) can be reformulated as a composition of Hölder functions defined on a hypercube. We define h1 = g1/(2H1) + 1/2,
  hj(u) = gj(2Hj−1u−Hj−1)/(2Hj) + 1/2, for all j ∈ {2, . . . , q − 1},
  and hq(u) = gq(2Hq−1u−Hq−1). Then we immediately have
  f(·, a) = gq ◦ · · · ◦ g1 = hq ◦ · · · ◦ h1. (D.8)
  Furthermore, by the definition of Hölder smooth functions in Definition 2.2, for any k ∈ [p2], we have that h1k takes value in [0, 1] and h1k ∈ Ct1([0, 1]t1 , β1, 1). Similarly, for any j ∈ {2, . . . , q−1} and k ∈ [pj+1], hjk also takes value in [0, 1] and
  hjk ∈ Ctj ( [0, 1]tj , βj , (2Hj−1) βj ) .
  Finally, recall that we use the convention that pq+1 = 1, that is, hq is a scalar-valued function that satisfies
  hq ∈ Ctq ( [0, 1]tq , βq, Hq(2Hq−1) βq ) .
  Now we employ the following lemma of Schmidt-Hieber (2017) to construct a ReLU network that approximates each hjk, which combined with (D.8) yields a ReLU network that is close to f(·, a). Recall that, as defined in Definition 2.2, we denote by Cr(D, β,H) the family of Hölder smooth functions with parameters β and H on D ⊆ Rr. Lemma D.3 (Approximation of Hölder Smooth Function). For any integers m ≥ 1 and N ≥ max{(β+1)r, (H+1)}, letL = 8+(m+5)·(1+dlog2 re), d0 = r, dj = 12rN for each j ∈ [L], and dL+1 = 1. For any g ∈ Cr([0, 1]r, β,H), there exists a ReLU network f ∈ F(L, {dj}L+1j=0 , s, Vmax) as defined in Definition 2.1 such that
  ‖f − g‖∞ ≤ (2H + 1) · 3r+1 ·N · 2−m +H · 2β ·N−β/r,
  where the parameter s satisfies s ≤ 94 · r2 · (β + 1)2r ·N · (m+ 6) · (1 + dlog2 re).
  Proof. See Theorem 3 of Schmidt-Hieber (2017) for a detailed proof.
  We apply Lemma D.3 to hjk : [0, 1]tj → [0, 1] for any j ∈ [q] and k ∈ [pj+1]. We setm = η·dlog2 ne for a sufficiently large constant η > 1, and set N to be a sufficiently large integer depending on n, which will be specified later. In addition, we set
  Lj = 9 + (m+ 5) · (1 + dlog2 tje) (D.9)
  and define
  W = max {
  max 1≤j≤q−1
  (2Hj−1) βj , Hq(2Hq−1) βq } , (D.10)
  which is a constant. Without loss of generality, we assume W ≥ 1 hereafter. Then by Lemma D.3, there exists a ReLU network ĥjk such that
  ‖ĥjk − hjk‖∞ ≤ (2W + 1) · 3tj ·N · n−η +W · 2βj ·N−βj/tj . (D.11)
  Furthermore, we have ĥjk ∈ F(Lj , {tj , 12tjN, . . . , 12tjN, 1}, sj) with
  sj ≤ 94 · t2j · (βj + 1)2tj ·N · (m+ 6) · (1 + dlog2 tje). (D.12)
  Meanwhile, since hj+1 = (h(j+1)k)k∈[pj+2] takes input from [0, 1] tj+1 , we need to further transform ĥjk so that it takes value in [0, 1]. In particular, we define σ(u) = 1−(1−u)+ = min{max{u, 0}, 1} for any u ∈ R. Note that σ can be represented by a two-layer ReLU network with four nonzero weights. Then we define h̃jk = σ ◦ ĥjk and h̃j = (h̃jk)k∈[pj+1]. Note that by the definition of h̃jk, we have h̃jk ∈ F(Lj + 2, {tj , 12tjN, . . . , 12tjN, 1}, sj + 4), which yields
  h̃j ∈ F ( Lj + 2, {tj , 12tjN · pj+1, . . . , 12tjN · pj+1, pj+1}, (sj + 4) · pj+1 ) .
  Moreover, since both h̃jk and hjk take value in [0, 1], by (D.11) we have
  ‖h̃jk − hjk‖∞ = ‖σ ◦ ĥjk − σ ◦ hjk‖∞ ≤ ‖ĥjk − hjk‖∞ ≤ (2W + 1) · 3tj ·N · n−η +W · 2βj ·N−βj/tj , (D.13)
  where the constant W is defined in (D.10). Now we define f̃ : S → R by f̃ = h̃q ◦ · · · ◦ h̃1, which falls in the function class
  F(L̃, {r, d̃, . . . , d̃, 1}, s̃), (D.14)
  where we define L̃ = ∑q j=1(Lj + 2), d̃ = maxj∈[q] 12tj · pj+1 ·N , and s̃ = ∑q j=1(sj + 4) · pj+1. Recall that, as defined in (D.9), we have Lj = 9 + (m + 5) · (1 + dlog2 tje). Then when n is sufficiently large, we have
  L̃ ≤ q∑ i=1 [ 11 + (log2 n+ 5) · (1 + dlog2 tje) ] ≤ q∑ i=1 4 log2 ti · log2 n . (log n)1+ξ, (D.15)
  where ξ > 0 is an absolute constant. Here the last inequality follows from (4.6). Moreover, for d̃ in (D.14), by (4.6) we have
  N ·max j∈[q] {pj+1 · tj} . d̃ ≤ 12 ·N · ( max j∈[q] pj ) · (max j∈[q] tj) . N · (log n)ξ. (D.16)
  In addition, combining (D.12), (4.6), and the fact that tj ≤ pj , we obtain
  s̃ . N · log n · ( max j∈[q] pj ) · ( q∑ j=1 log tj ) . N · (log n)1+2ξ. (D.17)
  Now we show that the function class in (D.14) can be embedded in F(L∗, {d∗j} L∗+1 j=1 , s ∗), where L∗, {d∗j} L∗+1 j=1 , and s ∗ are specified in (4.7). To this end, we set
  N = ⌈
  max 1≤j≤q
  C · ntj/(2β ∗ j+tj) ⌉ , (D.18)
  where the absolute constant C > 0 is sufficiently large. Note that we define α∗ = maxj∈[q] tj/(2β∗j + tj). Then (D.18) implies that N nα ∗ . When ξ′ in (4.7) satisfies ξ′ ≥ 1 + 2ξ, by (D.15) we have
  L̃ ≤ L∗ . (log n)ξ ′ .
  In addition, (D.16) and (4.7) implies that we can set d∗j ≥ d̃ for all j ∈ [L∗]. Finally, by (D.17) and (D.18), we have s̃ . nα ∗ · (log n)ξ′ , which implies s̃ + (L∗ − L̃) · r ≤ s∗. For an L̃-layer ReLU
  network in (D.14), we can make it an L∗-layer ReLU network by inserting L∗ − L̃ identity layers, since the inputs of each layer are nonnegative. Thus, ReLU networks in (D.14) can be embedded in
  F [ L∗, {r, r, . . . , r, d̃, . . . , d̃, 1}, s̃+ (L∗ − L̃)r ] ,
  which is a subset of F(L∗, {d∗j} L+1 j=1 , s ∗) by (4.7).
  To obtain the approximation error ‖f̃−f(·, a)‖∞, we defineGj = hj ◦· · ·◦h1 and G̃j = h̃j ◦· · ·◦h̃1 for any j ∈ [q]. By triangle inequality, for any j > 1 we have
  ‖Gj − G̃j‖∞ ≤ ‖hj ◦ G̃j−1 − hj ◦Gj−1‖∞ + ‖h̃j ◦ G̃j−1 − hj ◦ G̃j−1‖∞ ≤W · ‖Gj−1 − G̃j−1‖βj∧1∞ + ‖hj − h̃j‖∞, (D.19)
  where the second inequality holds since hj is Hölder smooth. To simplify the notation, we define λj = ∏q `=j+1(β` ∧ 1) for any j ∈ [q − 1], and set λq = 1. By applying recursion to (D.19), we obtain
  ‖f(·, a)− f̃‖∞ = ‖Gq − G̃q‖∞ ≤W q∑ j=1 ‖h̃j − hj‖λj∞ , (D.20)
  where the constant W is defined in (D.10). Here in (D.20) we use the fact that (a+ b)α ≤ aα + bα for all α ∈ [0, 1] and a, b > 0.
  In the sequel, we combine (D.7), (D.13), (D.20), and (D.18) to obtain the final bound on ω(F0). Since we can set the constant η in (D.13) to be sufficiently large, the second term on the right-hand side of (D.13) is the leading term asymptotically, that is,
  ‖h̃jk − hjk‖∞ . N−βj/tj . (D.21) Also note that β∗j = βj · ∏q `=j+1(β` ∧ 1) = βj · λj for all j ∈ [q − 1]. Thus we have β∗j = βj · λj for all j ∈ [q]. Combining (D.20) and (D.21), we have
  ‖f(·, a)− f̃‖∞ . q∑ j=1 ( N−βj/tj )λj = q∑ j=1 N−β ∗ j /tj . max j∈[q] N−β ∗ j /tj . (D.22)
  Thus, we combine (D.7), (D.18), and (D.22) to obtain ω(F0) ≤ ( max j∈[q] N−β ∗ j /tj )2 max j∈[q] n−2β ∗ j /(2β ∗ j+tj) = nα ∗−1. (D.23)
  As the final step of the proof, it remains to control the covering number of F0 defined in (4.1). By definition, for any f ∈ F0, we have f(·, a) ∈ F(L∗, {d∗j} L∗+1 j=1 , s
  ∗) for any a ∈ A. For notational simplicity, we denote by Nδ the δ-covering of F(L∗, {d∗j} L∗+1 j=1 , s ∗), that is, we define
  Nδ = N [ δ,F(L∗, {d∗j}L ∗+1 j=1 , s ∗), ‖ · ‖∞ ] .
  By the definition of covering, for any f ∈ F0 and any a ∈ A, there exists ga ∈ Nδ such that ‖f(·, a) − ga‖∞ ≤ δ. Then we define a function g : S × A → R by g(s, a) = ga(s) for any (s, a) ∈ S × A. By the definition of g, it holds that ‖f − g‖∞ ≤ δ. Therefore, the cardinality of N (δ,F0, ‖ · ‖∞) satisfies ∣∣N (δ,F0, ‖ · ‖∞)∣∣ ≤ |Nδ||A|. (D.24) Now we utilize the following lemma in Anthony & Bartlett (2009) to obtain an upper bound of the cardinality of Nδ . Lemma D.4 (Covering Number of ReLU Network). Recall that the family of ReLU networks F(L, {dj}L+1j=0 , s, Vmax) is given in Definition 2.1. Let D = ∏L+1 `=1 (d` + 1). For any δ > 0, we have
  log ∣∣∣N [δ,F(L, {dj}L+1j=0 , s, Vmax), ‖ · ‖∞]∣∣∣ ≤ (s+ 1) · log[2δ−1 · (L+ 1) ·D2].
  Proof. See Theorem 14.5 of Anthony & Bartlett (2009) for a detailed proof.
  Recall that we denote N (1/n,F0, ‖ · ‖∞) by N0 in (D.6). By combining (D.24) with Lemma D.4 and setting δ = 1/n, we obtain that
  logN0 ≤ |A| · log |Nδ| ≤ |A| · (s∗ + 1) · log [ 2n · (L∗ + 1) ·D2 ] ,
  where D = ∏L∗+1 `=1 (d ∗ ` + 1). By the choice of L ∗, s∗, and {d∗j} L∗+1 j=0 in (4.7), we conclude that
  logN0 . |A| · s∗ · L∗ max j∈[L∗] log(d∗j ) . n α∗ · (log n)1+2ξ ′ . (D.25)
  Finally, combining (D.1), (D.5), (D.23), and (D.25), we conclude the proof of Theorem 4.4.
sections.heading: E EXTENSION TO TWO-PLAYER ZERO-SUM MARKOV GAMES
sections.text: In this section, we propose the Minimax-DQN algorithm, which combines DQN and the Minimax-Q learning for two-player zero-sum Markov games. We first present the background of zero-sum Markov games and introduce the the Minimax-DQN algorithm in §E.1. Borrowing the analysis for DQN in the previous section, we provide theoretical guarantees for the proposed algorithm in §E.2.
  E.1 MINIMAX-DQN ALGORITHM
  As one of the simplistic extension of MDP to the multi-agent setting, two-player zero-sum Markov game is denoted by (S,A,B, P,R, γ), where S is state space, A and B are the action spaces of the first and second player, respectively. In addition, P : S ×A× B → P(S) is the Markov transition kernel, and R : S × A × B → P(R) is the distribution of immediate reward received by the first player. At any time t, the two players simultaneously take actions At ∈ A and Bt ∈ B at state St ∈ S , then the first player receives reward Rt ∼ R(St, At, Bt) and the second player obtains −Rt. The goal of each agent is to maximize its own cumulative discounted return.
  Furthermore, let π : S → P(A) and ν : S → P(B) be policies of the first and second players, respectively. Then, we similarly define the action-value function Qπ,ν : S ×A× B → R as
  Qπ,ν(s, a, b) = E [ ∞∑ t=0 γt ·Rt ∣∣∣∣ (S0, A0, B0) = (s, a, b), At ∼ π(· |St), Bt ∼ ν(· |St)], (E.1)
  and define the state-value function V π,ν : S → R as V π,ν(s) = E [ Qπ,ν(s,A,B) ∣∣A ∼ π(· | s), B ∼ ν(· | s)]. (E.2) Note that these two value functions are defined by the rewards of the first player. Thus, at any state-action tuple (s, a, b), the two players aim to solve maxπ minν Qπ,ν(s, a, b) and minν maxπ Q
  π,ν(s, a, b), respectively. By the von Neumann’s minimax theorem (Von Neumann & Morgenstern, 1947; Patek, 1997), there exists a minimax function of the game, Q∗ : S ×A×B → R, such that
  Q∗(s, a, b) = max π min ν Qπ,ν(s, a, b) = min ν max π Qπ,ν(s, a, b). (E.3)
  Moreover, for joint policy (π, ν) of two players, we define the Bellman operators Tπ,ν and T by
  (Tπ,νQ)(s, a, b) = r(s, a, b) + γ · (Pπ,νQ)(s, a, b), (E.4) (TQ)(s, a, b) = r(s, a, b) + γ · (P ∗Q)(s, a, b), (E.5)
  where r(s, a, b) = ∫ rR(dr | s, a, b), and we define operators Pπ,ν and P ∗ by
  (Pπ,νQ)(s, a, b) = Es′∼P (· | s,a,b),a′∼π(· | s′),b′∼ν(· | s′) [ Q(s′, a′, b′) ] ,
  (P ∗Q)(s, a, b) = Es′∼P (· | s,a,b) {
  max π′∈P(A) min ν′∈P(B)
  Ea′∼π′,b′∼ν′ [ Q(s′, a′, b′) ]} .
  Note that P ∗ is defined by solving a zero-sum matrix game based on Q(s′, ·, ·) ∈ R|A|×|B|, which could be achieved via linear programming. It can be shown that both Tπ,ν and T are γ-contractive, with Qπ,ν defined in (E.1) and Q∗ defined in (E.3) being the unique fixed points, respectively. Furthermore, similar to (2.3), in zero-sum Markov games, for any action-value function Q, the equilibrium joint policy with respect to Q is defined as[
  πQ(· | s), νQ(· | s) ]
  = argmax π′∈P(A) argmin ν′∈P(B)
  Ea∼π′,b∼ν′ [ Q(s, a, b) ] , ∀s ∈ S. (E.6)
  That is, πQ(· | s) and νQ(· | s) solves the zero-sum matrix game based on Q(s, ·, ·) for all s ∈ S. By this definition, we obtain that the equilibrium joint policy with respect to the minimax function Q∗ defined in (E.3) achieves the Nash equilibrium of the Markov game.
  Therefore, to learn the Nash equilibrium, it suffices to estimate Q∗, which is the unique fixed point of the Bellman operator T . Similar to the standard Q-learning for MDP, Littman (1994) proposes the Minimax-Q learning algorithm, which constructs a sequence of action-value functions that converges to Q∗. Specifically, in each iteration, based on a transition (s, a, b, s′), Minimax-Q learning updates the current estimator of Q∗, denoted by Q, via
  Q(s, a, b)← (1− α) ·Q(s, a, b) + α · { r(s, a, b) + γ · max
  π′∈P(A) min ν′∈P(B) Ea′∼π′,b′∼ν′
  [ Q(s′, a′, b′) ]} ,
  where α ∈ (0, 1) is the stepsize.
  Motivated by this algorithm, we propose the Minimax-DQN algorithm which extend DQN to twoplayer zero-sum Markov games. Specifically, we parametrize the action-value function using a deep neural network Qθ : S ×A× B → R and store the transition (St, At, Bt, Rt, St+1) into the replay memoryM at each time-step. Parameter θ of the Q-network is updated as follows. Let Qθ∗ be the target network. With n independent samples {(si, ai, bi, ri, s′i)}i∈[n] fromM, for all i ∈ [n], we compute the target
  Yi = ri + γ · max π′∈P(A) min ν′∈P(B)
  Ea∼π′,b∼ν′ [ Qθ∗(s ′ i, a, b) ] , (E.7)
  which can be attained via linear programming. Then we update θ in the direction of ∇θL(θ), where L(θ) = n−1 ∑ i∈[n][Yi − Qθ(si, ai, bi)]2. Finally, the target network Qθ∗ is updated every Ttarget steps by letting θ∗ = θ.
  To understand the theoretical aspects of this algorithm, we similarly utilize the framework of batch reinforcement learning for statistical analysis. With the insights gained in §3, we consider a modification of Minimax-DQN based on neural fitted Q-iteration, whose details are stated in Algorithm 4. As in the MDP setting, we replace sampling from the replay memory by sampling i.i.d. state-action tuples from a fixed distribution σ ∈ P(S ×A× B), and estimate Q∗ in (E.3) by solving a sequence of least-squares regression problems.
  E.2 THEORETICAL RESULTS FOR MINIMAX-FQI
  Following the theoretical results established in §4, in this subsection, we provide statistical guarantees for the Minimax-FQI algorithm with F being a family of deep neural networks with ReLU activation. Hereafter, without loss of generality, we assume S = [0, 1]r with r being a fixed integer, and the action spacesA and B are both finite. To evaluate the performance of the algorithm, we first introduce the best-response policy as follows.
  Definition E.1. For any policy π : S → P(A) of player one, the best-response policy against π, denoted by ν∗π, is defined as the optimal policy of second player when the first player follows π. In other words, for all s ∈ S, we have ν∗π(· | s) = argminν V π,ν(s), where V π,ν is defined in (E.2).
  Note that when the first player adopt a fixed policy π, from the perspective of the second player, the Markov game becomes a MDP. Thus, ν∗π is the optimal policy of the MDP induced by π. Moreover, it can be shown that, for any policy π, Q∗(s, a, b) ≥ Qπ,ν∗π (s, a, b) holds for every state-action tuple
  Algorithm 3 Minimax Deep Q-Network (Minimax-DQN) for the second player Input: Zero-Sum Markov game (S,A,B, P,R, γ), replay memoryM, number of iterations T , minibatch size n, exploration probability ∈ (0, 1), a family of deep Q-networksQθ : S×A×B → R, an integer Ttarget for updating the target network, and a sequence of stepsizes {αt}t≥0. Initialize the replay memoryM to be empty. Initialize the Q-network with random weights θ. Initialize the weights of the target network by letting θ? = θ. Initialize the initial state S0. for t = 0, 1, . . . , T do
  With probability , choose Bt uniformly at random from B, and with probability 1− , sample Bt according to the equilibrium policy ν̃Qθ (· |St) defined in (??). Execute Bt and observe the first player’s action At, reward Rt satisfying −Rt ∼ R(St, At, Bt), and the next state St+1 ∼ P (· |St, At, Bt). Store transition (St, At, Bt, Rt, St+1) inM. Experience replay: Sample random minibatch of transitions {(si, ai, bi, ri, s′i)}i∈[n] fromM. For each i ∈ [n], compute the target
  Yi = ri + γ · max ν′∈P(B) min π′∈P(A)
  Ea∼π′,b∼ν′ [ Qθ∗(s ′ i, a, b) ] .
  Update the Q-network: Perform a gradient descent step
  θ ← θ − αt · 1
  n ∑ i∈[n] [ Yi −Qθ(si, ai, bi) ] · ∇θQθ(si, ai, bi).
  Update the target network: Update θ? ← θ every Ttarget steps. end for Output: Q-network Qθ and equilibrium joint policy with respect to Qθ.
  Algorithm 4 Fitted Q-Iteration Algorithm for Zero-Sum Markov Games (Minimax-FQI) Input: Two-player zero-sum Markov game (S,A,B, P,R, γ), function class F , distribution σ ∈ P(S ×A× B), number of iterations K, number of samples n, the initial estimator Q̃0 ∈ F . for k = 0, 1, 2, . . . ,K − 1 do
  Sample n i.i.d. observations {(Si, Ai, Bi)}i∈[n] from σ, obtain Ri ∼ R(· |Si, Ai, Bi) and S′i ∼ P (· |Si, Ai, Bi). Compute Yi = Ri + γ ·maxπ′∈P(A) minν′∈P(B) Ea∼π′,b∼ν′ [ Q̃k(s ′ i, a, b) ] .. Update the action-value function:
  Q̃k+1 ← argmin f∈F
  1
  n n∑ i=1 [ Yi − f(Si, Ai, Bi) ]2 .
  end for Let (πK , νK) be the equilibrium joint policy with respect to Q̃K , which is defined in (E.6). Output: An estimator Q̃K of Q∗ and joint policy (πK , νK).
  (s, a, b). Thus, by considering the adversarial case where the opponent always plays the best-response policy, the difference between Qπ.ν ∗ π and Q∗ servers as a characterization of the suboptimality of π. Hence, to quantify the performance of Algorithm 4, we consider the closeness between Q∗ and QπK ,ν ∗ πK , which will be denoted by Q∗K hereafter for simplicity. Specifically, in the following we establish an upper bound for ‖Q∗ −Q∗K‖1,µ for some distribution µ ∈ P(S ×A× B).
  We first specify the function class F in Algorithm 4 as follows.
  Assumption E.2 (Function Classes). Following Definition 4.1, let F(L, {dj}L+1j=0 , s) and G({pj , tj , βj , Hj}j∈[q]) be the family of sparse ReLU networks and the set of composition of Hölder smooth functions defined on S, respectively. Similar to (4.1), we define F1 by
  F1 = { f : S ×A → R : f(·, a, b) ∈ F(L, {dj}L+1i=0 , s) for any (a, b) ∈ A× B } . (E.8)
  For the Bellman operator T defined in (E.5), we assume that for any f ∈ F1 and any state-action tuple (s, a, b), we have (Tf)(·, a, b) ∈ G({pj , tj , βj , Hj}j∈[q]).
  We remark that this Assumption is in the same flavor as Assumption 4.2. As discussed in §4, this assumption holds if both the reward function and the transition density of the Markov game are sufficiently smooth.
  In the following, we define the concentration coefficients for Markov games.
  Assumption E.3 (Concentration Coefficient for Zero-Sum Markov Games). Let {τt : S → P(A× B)} be a sequence of joint policies for the two players in the zero-sum Markov game. Let ν1, ν2 ∈ P(S × A × B) be two absolutely continuous probability measures. Suppose the initial stateaction pair (S0, A0, B0) has distribution ν1, the future states are sampled according to the Markov transition kernel, and the action (At, Bt) is sampled from policy τt. For any integer m, we denote by P τmP τm−1 · · ·P τ1ν1 the distribution of (Sm, Am, Bm). Then, the m-th concentration coefficient is defined as
  κ(m; ν1, ν2) = sup τ1,...,τm
  [ Eν2 ∣∣∣∣d(P τmP τm−1 · · ·P τ1ν1)dν2 ∣∣∣∣2]1/2, (E.9)
  where the supremum is taken over all possible joint policy sequences {τt}t∈[m].
  Furthermore, for some µ ∈ P(S×A×B), we assume that there exists a finite constant φµ,σ such that (1− γ)2 · ∑ m≥1 γ
  m−1 ·m · κ(m;µ, σ) ≤ φµ,σ, where σ is the sampling distribution in Algorithm 4 and κ(m;µ, σ) is the m-th concentration coefficient defined in (E.9).
  We remark that the definition of them-th concentration coefficient is the same as in (4.4) if we replace the action space A of the MDP by A×B of the Markov game. Thus, Assumptions 4.3 and E.3 are of the same nature, which are standard in the literature.
  Now we are ready to present the main theorem.
  Theorem E.4. Under Assumptions E.2 and E.3, consider the Minimax-FQI algorithm with the function class F being F1 defined in (E.8) based on the family of sparse ReLU networks F(L∗, {d∗j} L∗+1 j=0 , s ∗). We make the same assumptions on F(L∗, {d∗j} L∗+1 j=0 , s
  ∗) and G({pj , tj , βj , Hj}j∈[q]) as in (4.6) and (4.7). Then for any K ∈ N, let (πK , νK) be the policy returned by the algorithm and let Q∗K be the action-value function corresponding to (πK , ν ∗ πK ). Then there exists constants ξ∗ and C such that
  ‖Q∗ −Q∗K‖1,µ ≤ C · φµ,σ · γ (1− γ)2 · |A| · |B| · (log n)ξ ∗ · n(α ∗−1)/2 + 4γK+1 (1− γ)2 ·Rmax, (E.10)
  where α∗ = maxj∈[q] tj/(2β∗j + tj) and φµ,σ is specified in Assumption E.3.
  Similar to Theorem 4.4, the bound in (E.10) shows that closeness between (πK , νK) returned by Algorithm 4 and the Nash equilibrium policy (πQ∗ , νQ∗), measured by ‖Q∗ −Q∗K‖1,µ, is bounded by the sum of statistical error and an algorithmic error. Specifically, the statistical error balances the bias and variance of estimating the value functions using the family of deep ReLU neural networks, which exhibits the fundamental difficulty of the problem. Whereas the algorithmic error decay to zero geometrically as K increases. Thus, when K is sufficiently large, both γ and φµ,σ are constants, and the polylogarithmic term is ignored, Algorithm 4 achieves error rate
  |A| · |B| · nα ∗−1 = |A| · |B| ·max j∈[q] n−β ∗ j /(2β ∗ j+tj), (E.11)
  which scales linearly with the capacity of joint action space. Besides, if |B| = 1, The Minimax-FQI algorithm reduces to Algorithm 1. In this case, (E.11) also recovers the error rate of Algorithm 1. Furthermore, the statistical rate n(α
  ∗−1)/2 achieves the optimal `2-norm error of regression for nonparametric regression with a compositional structure, which indicates that the statistical error in (E.10) can not be further improved.
  Proof. See §G for a detailed proof.
sections.heading: F PROOFS OF AUXILIARY RESULTS
sections.text: In this section, we present the proofs for Theorems D.1 and D.2, which are used in the §D to establish our main theorem.
  F.1 PROOF OF THEOREM D.1
  Proof. Before we present the proof, we introduce some notation. For any k ∈ {0, . . . ,K − 1}, we denote TQ̃k by Qk+1 and define
  %k = Qk − Q̃k. (F.1)
  Also, we denote by πk the greedy policy with respect to Q̃k. In addition, throughout the proof, for two functions Q1, Q2 : S × A → R, we use the notation Q1 ≥ Q2 if Q1(s, a) ≥ Q2(s, a) for any s ∈ S and any a ∈ A, and define Q1 ≤ Q2 similarly. Furthermore, for any policy π, recall that in (2.4) we define the operator Pπ by
  (PπQ)(s, a) = E [ Q(S′, A′) ∣∣S′ ∼ P (· | s, a), A′ ∼ π(· |S′)]. (F.2) In addition, we define the operator Tπ by
  (TπQ)(s, a) = r(s, a) + γ · (PπQ)(s, a).
  Finally, we denote Rmax/(1− γ) by Vmax. Now we are ready to present the proof, which consists of three key steps.
  Step (i): In the first step, we establish a recursion that relates Q∗ − Q̃k+1 with Q∗ − Q̃k to measure the sub-optimality of the value function Q̃k. In the following, we first establish an upper bound for Q∗ − Q̃k+1 as follows. For each k ∈ {0, . . . ,K − 1}, by the definition of %k+1 in (F.1), we have
  Q∗ − Q̃k+1 = Q∗ − (Qk+1 − %k+1) = Q∗ −Qk+1 + %k+1 = Q∗ − TQ̃k + %k+1 = Q∗ − Tπ ∗ Q̃k + (T π∗Q̃k − TQ̃k) + %k+1, (F.3)
  where π∗ is the greedy policy with respect to Q∗. Now we leverage the following lemma to show Tπ ∗ Q̃k ≤ TQ̃k.
  Lemma F.1. For any action-value function Q : S ×A → R and any policy π, it holds that
  TπQQ = TQ ≥ TπQ.
  Proof. Note that we have maxa′ Q(s′, a′) ≥ Q(s′, a′) for any s′ ∈ S and a′ ∈ A. Thus, it holds that (TQ)(s, a) = r(s, a) + γ · E [ max a′ Q(S′, a′) ∣∣S′ ∼ P (· | s, a)]
  ≥ r(s, a) + γ · E [ Q(S′, A′) ∣∣S′ ∼ P (· | s, a), A′ ∼ π(· |S′)] = (TπQ)(s, a). Recall that πQ is the greedy policy with respect to Q such that
  P [ A ∈ argmax
  a Q(s, a)
  ∣∣A ∼ πQ(· | s)] = 1,
  which implies
  E [ Q(s′, A′) ∣∣A′ ∼ πQ(· | s′)] = max a′ Q(s′, a′).
  Consequently, we have (TπQQ)(s, a) = r(s, a) + γ · E [ Q(S′, A′) ∣∣S′ ∼ P (· | s, a), A′ ∼ πQ(· |S′)] = r(s, a) + γ · E [ max a′ Q(S′, a′) ∣∣S′ ∼ P (· | s, a)] = (TQ)(s, a),
  which concludes the proof of Lemma F.1.
  By Lemma F.1, we have TQ̃k ≥ Tπ ∗ Q̃k. Also note that Q∗ is the unique fixed point of Tπ ∗ . Thus, by (F.3) we have
  Q∗ − Q̃k+1 = (Tπ ∗ Q∗ − Tπ ∗ Q̃k) + (T π∗Q̃k − TQ̃k) + %k+1 ≤ (Tπ ∗ Q∗ − Tπ ∗ Q̃k) + %k+1,
  (F.4)
  In the following, we establish a lower bound for Q∗− Q̃k+1 based on Q̃∗− Q̃k. Note that, by Lemma F.1, we have TπkQ̃k = TQ̃k and TQ∗ ≥ TπkQ∗. Similar to (F.3), since Q∗ is the unique fixed point of T , it holds that
  Q∗ − Q̃k+1 = Q∗ − TQ̃k + %k+1 = Q∗ − TπkQ̃k + %k+1 = Q∗ − TπkQ∗ + (TπkQ∗ − TπkQ̃k) + %k+1 = (TQ∗ − TπkQ∗) + (TπkQ∗ − TπkQ̃k) + %k+1 ≥ (TπkQ∗ − TπkQ̃k) + %k+1.
  (F.5)
  Thus, combining (F.4) and (F.5) we obtain that, for any k ∈ {0, . . . ,K − 1},
  TπkQ∗ − TπkQ̃k + %k+1 ≤ Q∗ − Q̃k+1 ≤ Tπ ∗ Q∗ − Tπ ∗ Q̃k + %k+1. (F.6)
  The inequalities in (F.6) show that the error Q∗ − Q̃k+1 can be sandwiched by the summation of a term involving Q∗ − Q̃k and the error %k+1, which is defined in (F.1) and induced by approximating the action-value function. Using Pπ defined in (F.2), we can write (F.6) in a more compact form,
  γ · Pπ ∗ (Q∗ − Q̃k) + %k+1 ≥ Q∗ − Q̃k+1 ≥ γ · Pπk(Q∗ − Q̃k) + %k+1. (F.7)
  Meanwhile, note that Pπ defined in (F.2) is a linear operator. In fact, Pπ is the Markov transition operator for the Markov chain on S ×A with transition dynamics
  St+1 ∼ P (· |St, At), At+1 ∼ π(· |St+1).
  By the linearity of the operator Pπ and the one-step error bound in (F.6), we have the following characterization of the multi-step error.
  Lemma F.2 (Error Propagation). For any k, ` ∈ {0, 1, . . . ,K − 1} with k < `, we have Q∗ − Q̃` ≤ `−1∑ i=k γ`−1−i · (Pπ ∗ )`−1−i%i+1 + γ `−k · (Pπ ∗ )`−k(Q∗ − Q̃k), (F.8)
  Q∗ − Q̃` ≥ `−1∑ i=k γ`−1−i · (Pπ`−1Pπ`−2 · · ·Pπi+1)%i+1 + γ`−k · (Pπ`−1Pπ`−2 · · ·Pπk)(Q∗ − Q̃k).
  (F.9)
  Here %i+1 is defined in (F.1) and we use PπPπ ′ and (Pπ)k to denote the composition of operators.
  Proof. Note that Pπ is a linear operator for any policy π. We obtain (F.8) and (F.9) by iteratively applying the inequalities in (F.7).
  Lemma F.2 gives the upper and lower bounds for the propagation of error through multiple iterations of Algorithm 1, which concludes the first step of our proof.
  Step (ii): The results in the first step only concern the propagation of error Q∗ − Q̃k. In contrast, the output of Algorithm 1 is the greedy policy πk with respect to Q̃k. In the second step, our goal is to quantify the suboptimality of Qπk , which is the action-value function corresponding to πk. In the following, we establish an upper bound for Q∗ −Qπk .
  To begin with, we have Q∗ ≥ Qπk by the definition of Q∗ in (2.5). Note that we have Q∗ = Tπ∗Q∗ and Qπk = TπkQπk . Hence, it holds that
  Q∗ −Qπk = Tπ ∗ Q∗ − TπkQπk = Tπ ∗ Q∗ + (−Tπ ∗ Q̃k + T π∗Q̃k) + (−TπkQ̃k + TπkQ̃k)− TπkQπk
  = (Tπ ∗ Q̃k − TπkQ̃k) + (Tπ ∗ Q∗ − Tπ ∗ Q̃k) + (T πkQ̃k − TπkQπk). (F.10)
  Now we quantify the three terms on the right-hand side of (F.10) respectively. First, by Lemma F.1, we have
  Tπ ∗ Q̃k − TπkQ̃k = Tπ ∗ Q̃k − TQ̃k ≤ 0. (F.11)
  Meanwhile, by the definition of the operator Pπ in (F.2), we have
  Tπ ∗ Q∗ − Tπ ∗ Q̃k = γ · Pπ ∗ (Q∗ − Q̃k), TπkQ̃k − TπkQπk = γ · Pπk(Q̃k −Qπk). (F.12)
  Plugging (F.11) and (F.12) into (F.10), we obtain
  Q∗ −Qπk ≤ γ · Pπ ∗ (Q∗ − Q̃k) + γ · Pπk(Q̃k −Qπk)
  = γ · (Pπ ∗ − Pπk)(Q∗ − Q̃k) + γ · Pπk(Q∗ −Qπk),
  which further implies that
  (I − γ · Pπk)(Q∗ −Qπk) ≤ γ · (Pπ ∗ − Pπk)(Q∗ − Q̃k).
  Here I is the identity operator. Since Tπ is a γ-contractive operator for any policy π, I − γ · Pπ is invertible. Thus, we obtain
  0 ≤ Q∗ −Qπk ≤ γ · (I − γ · Pπk)−1 [ Pπ ∗ (Q∗ − Q̃k)− Pπk(Q∗ − Q̃k) ] , (F.13)
  which relates Q∗−Qπk with Q∗− Q̃k. In the following, we plug Lemma F.2 into (F.13) to obtain the multiple-step error bounds for Qπk . First note that, by the definition of Pπ in (F.2), for any functions f1, f2 : S ×A → R satisfying f1 ≥ f2, we have Pπf1 ≥ Pπf2. Combining this inequality with the upper bound in (F.8) and the lower bound in (F.9), we have that, for any k < `,
  Pπ ∗ (Q∗ − Q̃`) ≤ `−1∑ i=k γ`−1−i · (Pπ ∗ )`−i%i+1 + γ `−k · (Pπ ∗ )`−k+1(Q∗ − Q̃k), (F.14)
  Pπ`(Q∗ − Q̃`) ≥ `−1∑ i=k γ`−1−i · (Pπ`Pπ`−1 · · ·Pπi+1)%i+1
  + γ`−k · (Pπ`Pπ`−1 · · ·Pπk)(Q∗ − Q̃k). (F.15)
  Then we plug (F.14) and (F.15) into (F.13) and obtain 0 ≤ Q∗ −Qπ` ≤ (I − γ · Pπ`)−1 { `−1∑ i=k γ`−i · [ (Pπ ∗ )`−i − (Pπ`Pπ`−1 · · ·Pπi+1) ] %i+1
  + γ`+1−k · [ (Pπ ∗ )`−k+1 − (Pπ`Pπ`−1 · · ·Pπk) ] (Q∗ − Q̃k) } (F.16)
  for any k < `. To quantify the error of QπK , we set ` = K and k = 0 in (F.16) to obtain
  0 ≤ Q∗ −QπK ≤ (I − γPπK )−1 {K−1∑
  i=0
  γK−i · [ (Pπ ∗ )K−i − (PπKPπK−1 · · ·Pπi+1) ] %i+1
  + γK+1 · [ (Pπ ∗ )K+1 − (PπKPπK−1 · · ·Pπ0) ] (Q∗ − Q̃0) } .
  (F.17)
  For notational simplicity, we define
  αi = (1− γ)γK−i−1
  1− γK+1 , for 0 ≤ i ≤ K − 1, and αK =
  (1− γ)γK 1− γK+1 . (F.18)
  One can show that ∑K i=0 αi = 1. Meanwhile, we define K + 1 linear operators {Ok}Kk=0 by
  Oi = (1− γ)/2 · (I − γPπK )−1 [ (Pπ ∗ )K−i + (PπKPπK−1 · · ·Pπi+1) ] , for 0 ≤ i ≤ K − 1,
  OK = (1− γ)/2 · (I − γPπK )−1 [ (Pπ ∗ )K+1 + (PπKPπK−1 · · ·Pπ0) ] .
  Using this notation, for any (s, a) ∈ S ×A, by (F.17) we have∣∣Q∗(s, a)−QπK (s, a)∣∣ ≤ 2γ(1− γ K+1)
  (1− γ)2 · [K−1∑ i=0 αi · ( Oi|%i+1| ) (s, a) + αK · ( OK |Q∗ − Q̃0| ) (s, a) ] , (F.19)
  where both Oi|%i+1| and OK |Q∗ − Q̃0| are functions defined on S ×A. Here (F.19) gives a uniform upper bound for Q∗ −QπK , which concludes the second step.
  Step (iii): In this step, we conclude the proof by establishing an upper bound for ‖Q∗ −QπK‖1,µ based on (F.19). Here µ ∈ P(S ×A) is a fixed probability distribution. To simplify the notation, for any measurable function f : S ×A → R, we denote µ(f) to be the expectation of f under µ, that is, µ(f) = ∫ S×A f(s, a)dµ(s, a). Using this notation, by (F.19) we bound ‖Q ∗ −Qπ`‖1,µ by
  ‖Q∗ −QπK‖1,µ = µ ( |Q∗ −QπK | ) ≤ 2γ(1− γ K+1)
  (1− γ)2 · µ [K−1∑ i=0 αi · ( Oi|%i+1| ) + αK · ( OK |Q∗ − Q̃0| )] . (F.20)
  By the linearity of expectation, (F.20) implies
  ‖Q∗ −QπK‖1,µ ≤ 2γ(1− γK+1) (1− γ)2 · [K−1∑ i=0 αi · µ ( Oi|%i+1| ) + αK · µ ( OK |Q∗ − Q̃0| )] . (F.21)
  Furthermore, since both Q∗ and Q̃0 are bounded by Vmax = Rmax/(1− γ) in `∞-norm, we have µ ( OK |Q∗ − Q̃0| ) ≤ 2 ·Rmax/(1− γ). (F.22)
  Moreover, for any i ∈ {0, . . . ,K − 1}, by expanding (1− γPπK )−1 into a infinite series, we have
  µ ( Oi|%i+1| ) = µ
  { 1− γ
  2 · (1− γPπK )−1
  [ (Pπ ∗ )K−i + (PπKPπK−1 · · ·Pπi+1) ] |%i+1| } =
  1− γ 2 · µ { ∞∑ j=0 γj · [ (PπK )j(Pπ ∗ )K−i + (PπK )j+1(PπK−1 · · ·Pπi+1) ] |%i+1| } .
  (F.23)
  To upper bound the right-hand side of (F.23), we consider the following quantity
  µ [ (PπK )j(P τmP τm−1 · · ·P τ1)f ] = ∫ S×A [ (PπK )j(P τmP τm−1 · · ·P τ1)f ] (s, a)dµ(s, a). (F.24)
  Here τ1, . . . , τm are m policies. Recall that Pπ is the transition operator of a Markov process defined on S × A for any policy π. Then the integral on the right-hand side of (F.24) corresponds to the expectation of the function f(Xt), where {Xt}t≥0 is a Markov process defined on S × A. Such a Markov process has initial distribution X0 ∼ µ. The first m transition operators are {P τj}j∈[m], followed by j identical transition operators PπK . Hence, (PπK )j(P τmP τm−1 · · ·P τ1)µ is the marginal distribution of Xj+m, which we denote by µ̃j for notational simplicity. Hence, (F.24) takes the form
  µ [ (PπK )j(P τmP τm−1 · · ·P τ1)f ] = E [ f(Xj+m) ] = µ̃j(f) = ∫ S×A f(s, a)dµ̃j(s, a) (F.25)
  for any measurable function f on S ×A. By Cauchy-Schwarz inequality, we have µ̃j(f) ≤ [∫ S×A ∣∣∣dµ̃j dσ (s, a) ∣∣∣2dσ(s, a)]1/2[∫ S×A |f(s, a)|2dσ(s, a) ]1/2 , (F.26)
  in which dµ̃j/dσ : S ×A → R is the Radon-Nikodym derivative. Recall that the (m+ j)-th order concentration coefficient κ(m+ j;µ, σ) is defined in (4.4). Combining (F.25) and (F.26), we obtain
  µ̃j(f) ≤ κ(m+ j;µ, σ) · ‖f‖σ.
  Thus, by (F.23) we have µ ( Oi|%i+1| ) = 1− γ 2 · ∞∑ j=0 γj · { µ [ (PπK )j(Pπ ∗ )K−i|%i+1| ] + µ [ (PπK )j+1(PπK−1 · · ·Pπi+1)|%i+1| ]} ≤ (1− γ) ·
  ∞∑ j=0 γj · κ(K − i+ j;µ, σ) · ‖%i+1‖σ. (F.27)
  Now we combine (F.21), (F.22), and (F.27) to obtain
  ‖Q∗ −QπK‖1,µ ≤ 2γ(1− γK+1) (1− γ)2 · [K−1∑ i=0 αi · µ ( Oi|%i+1| ) + αK · µ ( OK |Q∗ − Q̃0| )]
  ≤ 2γ(1− γ K+1) (1− γ) · [K−1∑ i=0 ∞∑ j=0 αi · γj · κ(K − i+ j;µ, σ) · ‖%i+1‖σ ] + 4γ(1− γK+1) (1− γ)3 · αK ·Rmax.
  Recall that in Theorem D.1 and (F.1) we define εmax = maxi∈[K] ‖%i‖σ. We have that ‖Q∗ − QπK‖1,µ is further upper bounded by
  ‖Q∗ −QπK‖1,µ (F.28)
  ≤ 2γ(1− γ K+1) (1− γ) · [K−1∑ i=0 ∞∑ j=0 αi · γj · κ(K − i+ j;µ, σ) ] · εmax + 4γ(1− γK+1) (1− γ)3 · αK ·Rmax
  = 2γ(1− γK+1) (1− γ) · [K−1∑ i=0 ∞∑ j=0 (1− γ)γK−i−1 1− γK+1 · γj · κ(K − i+ j;µ, σ) ] · εmax + 4γK+1 (1− γ)2 ·Rmax,
  where the last equality follows from the definition of {αi}0≤i≤K in (F.18). We simplify the summation on the right-hand side of (F.28) and use Assumption 4.3 to obtain
  K−1∑ i=0 ∞∑ j=0 (1− γ)γK−i−1 1− γK+1 · γj · κ(K − i+ j;µ, σ)
  = 1− γ 1− γK+1 ∞∑ j=0 K−1∑ i=0 γK−i+j−1 · κ(K − i+ j;µ, σ)
  ≤ 1− γ 1− γK+1 ∞∑ m=0 γm−1 ·m · κ(m;µ, σ) ≤ φµ,σ (1− γK+1)(1− γ) , (F.29)
  where the last inequality follows from (4.5) in Assumption 4.3. Finally, combining (F.28) and (F.29), we obtain
  ‖Q∗ −QπK‖1,µ ≤ 2γ · φµ,σ (1− γ)2 · εmax + 4γK+1 (1− γ)2 ·Rmax,
  which concludes the third step and hence the proof of Theorem D.1.
  F.2 PROOF OF THEOREM D.2
  Proof. Recall that in Algorithm 1 we define Yi = Ri + γ · maxa∈AQ(Si+1, a), where Q is any function in F . By definition, we have E(Yi |Si = s,Ai = a) = (TQ)(s, a) for any (s, a) ∈ S ×A. Thus, TQ can be viewed as the underlying truth of the regression problem defined in (D.2), where the covariates and responses are {(Si, Ai)}i∈[n] and {Yi}i∈[n], respectively. Moreover, note that TQ is not necessarily in function class F . We denote by Q∗ the best approximation of TQ in F , which is the solution to
  minimize f∈F
  ‖f − TQ‖2σ = E {[ f(Si, Ai)−Q(Si, Ai) ]2} . (F.30)
  For notational simplicity, in the sequel we denote (Si, Ai) by Xi for all i ∈ [n]. For any f ∈ F , we define ‖f‖2n = 1/n · ∑n i=1[f(Xi)]
  2. Since both Q̂ and TQ are bounded by Vmax = Rmax/(1− γ), we only need to consider the case where logNδ ≤ n. Here Nδ is the cardinality of N (δ,F , ‖ · ‖∞). Moreover, let f1, . . . , fNδ be the centers of the minimal δ-covering of F . Then by the definition of δ-covering, there exists k∗ ∈ [Nδ] such that ‖Q̂ − fk∗‖∞ ≤ δ. It is worth mentioning that k∗ is a random variable since Q̂ is obtained from data.
  In the following, we prove (D.3) in two steps, which are bridged by E[‖Q̂− TQ‖2n].
  Step (i): We relate E[‖Q̂− TQ‖2n] with its empirical counterpart ‖Q̂− TQ‖2n. Recall that we define Yi = Ri + γ ·maxa∈AQ(Si+1, a) for each i ∈ [n]. By the definition of Q̂, for any f ∈ F we have
  n∑ i=1 [ Yi − Q̂(Xi) ]2 ≤ n∑ i=1 [ Yi − f(Xi) ]2 . (F.31)
  For each i ∈ [n], we define ξi = Yi − (TQ)(Xi). Then (F.31) can be written as
  ‖Q̂− TQ‖2n ≤ ‖f − TQ‖2n + 2
  n n∑ i=1 ξi · [ Q̂(Xi)− f(Xi) ] . (F.32)
  Since both f and Q are deterministic, we have E(‖f − TQ‖2n) = ‖f − TQ‖2σ. Moreover, since E(ξi |Xi) = 0 by definition, we have E[ξi · g(Xi)] = 0 for any bounded and measurable function g. Thus, it holds that
  E { n∑ i=1 ξi · [ Q̂(Xi)− f(Xi) ]} = E { n∑ i=1 ξi · [ Q̂(Xi)− (TQ)(Xi) ]} . (F.33)
  In addition, by triangle inequality and (F.33), we have∣∣∣∣E{ n∑ i=1 ξi · [ Q̂(Xi)− (TQ)(Xi) ]}∣∣∣∣ ≤ ∣∣∣∣E{ n∑
  i=1
  ξi · [ Q̂(Xi)− fk∗(Xi) ]}∣∣∣∣+ ∣∣∣∣E{ n∑ i=1 ξi · [ fk∗(Xi)− (TQ)(Xi) ]}∣∣∣∣, (F.34) where fk∗ satisfies ‖fk∗ − Q̂‖∞ ≤ δ. In the following, we upper bound the two terms on the right-hand side of (F.34) respectively. For the first term, by applying Cauchy-Schwarz inequality
  twice, we have∣∣∣∣E{ n∑ i=1 ξi · [ Q̂(Xi)− fk∗(Xi) ]}∣∣∣∣ ≤ √n · ∣∣∣∣E[( n∑ i=1 ξ2i )1/2 · ‖Q̂− fk∗‖n ]∣∣∣∣ ≤ √ n · [ E ( n∑ i=1 ξ2i )]1/2 · [ E ( ‖Q̂− fk∗‖2n )]1/2 ≤ nδ · [ E(ξ2i ) ]1/2 , (F.35)
  where we use the fact that {ξi}i∈[n] have the same marginal distributions and ‖Q̂− fk∗‖n ≤ δ. Since both Yi and TQ are bounded by Vmax, ξi is a bounded random variable by its definition. Thus, there exists a constant Cξ > 0 depending on ξ such that E(ξ2i ) ≤ C2ξ · V 2max. Then (F.35) implies∣∣∣∣E{ n∑
  i=1
  ξi · [ Q̂(Xi)− fk∗(Xi) ]}∣∣∣∣ ≤ Cξ · Vmax · nδ. (F.36) It remains to upper bound the second term on the right-hand side of (F.34). We first define Nδ self-normalized random variables
  Zj = 1√ n n∑ i=1 ξi · [ fj(Xi)− (TQ)(Xi) ] · ‖fj − (TQ)‖−1n (F.37)
  for all j ∈ [Nδ]. Here recall that {fj}j∈[Nδ] are the centers of the minimal δ-covering of F . Then we have∣∣∣∣E{ n∑
  i=1
  ξi · [ fk∗(Xi)− (TQ)(Xi) ]}∣∣∣∣ = √n · E[‖fk∗ − TQ‖n · |Zk∗ |] ≤ √ n · E {[ ‖Q̂− TQ‖n + ‖Q̂− fk∗‖n ] · |Zk∗ | } ≤ √ n · E {[ ‖Q̂− TQ‖n + δ ] · |Zk∗ | } ,
  (F.38)
  where the first inequality follows from triangle inequality and the second inequality follows from the fact that ‖Q̂ − fk∗‖∞ ≤ δ. Then applying Cauchy-Schwarz inequality to the last term on the right-hand side of (F.38), we obtain
  E {[ ‖Q̂− TQ‖n + δ ] · |Zk∗ | } ≤ ( E {[ ‖Q̂− TQ‖n + δ ]2})1/2 · [E(Z2k∗)]1/2 ≤ ({ E [ ‖Q̂− TQ‖2n ]}1/2 + δ ) · [ E (
  max j∈[N ]
  Z2j )]1/2 , (F.39)
  where the last inequality follows from
  E [ ‖Q̂− TQ‖n ] ≤ { E [ ‖Q̂− TQ‖2n ]}1/2 .
  Moreover, since ξi is centered conditioning on {Xi}i∈[n] and is bounded by 2Vmax, ξi is a subGaussian random variable. In specific, there exists an absolute constant Hξ > 0 such that ‖ξi‖ψ2 ≤ Hξ · Vmax for each i ∈ [n]. Here the ψ2-norm of a random variable W ∈ R is defined as
  ‖W‖ψ2 = sup p≥1
  p−1/2 [ E(|W |p) ]1/p .
  By the definition of Zj in (F.37), conditioning on {Xi}i∈[n], ξi · [fj(Xi)− (TQ)(Xi)] is a centered and sub-Gaussian random variable with∥∥ξi · [fj(Xi)− (TQ)(Xi)]∥∥ψ2 ≤ Hξ · Vmax · ∣∣fj(Xi)− (TQ)(Xi)∣∣. Moreover, since Zj is a summation of independent sub-Gaussian random variables, by Lemma 5.9 of ?, the ψ2-norm of Zj satisfies
  ‖Zj‖ψ2 ≤ C ·Hξ · Vmax · ‖fj − TQ‖−1n · [ 1
  n n∑ i=1 ∣∣[fj(Xi)− (TQ)(Xi)]∣∣2]1/2 ≤ C ·Hξ · Vmax,
  where C > 0 is an absolute constant. Furthermore, by Lemmas 5.14 and 5.15 of ?, Z2j is a sub-exponential random variable, and its the moment-generating function is bounded by
  E [ exp(t · Z2j ) ] ≤ exp(C · t2 ·H4ξ · V 4max) (F.40)
  for any t satisfying C ′ · |t| ·H2ξ · V 2max ≤ 1, where C and C ′ are two positive absolute constants. Moreover, by Jensen’s inequality, we bound the moment-generating function of maxj∈[Nδ] Z 2 j by
  E [ exp ( t · max j∈[Nδ] Z2j )] ≤ ∑ j∈[Nδ] E [ exp(t · Z2j ) ] . (F.41)
  Combining (F.40) and (F.41), we have E (
  max j∈[N ]
  Z2j ) ≤ C2 ·H2ξ · V 2max · logNδ, (F.42)
  where C > 0 is an absolute constant. Hence, plugging (F.42) into (F.38) and (F.39), we upper bound the second term of the right-hand side of (F.33) by∣∣∣∣E{ n∑
  i=1
  ξi · [ fk∗(Xi)− (TQ)(Xi) ]}∣∣∣∣ ≤ ({ E [ ‖Q̂− TQ‖2n ]}1/2 + δ ) · C ·Hξ · Vmax · √ n · logNδ. (F.43)
  Finally, combining (F.32), (F.36) and (F.43), we obtain the following inequality E [ ‖Q̂− TQ‖2n ] ≤ inf f∈F E [ ‖f − TQ‖2n ] + Cξ · Vmax · δ (F.44)
  + ({ E [ ‖Q̂− (TQ)‖2n ]}1/2 + δ ) · C ·Hξ · Vmax · √ logNδ/n
  ≤ C · Vmax √ logNδ/n · { E [ ‖Q̂− (TQ)‖2n ]}1/2 + inf f∈F E [ ‖f − TQ‖2n ] + C ′ · Vmaxδ,
  where C and C ′ are two positive absolute constants. Here in the first inequality we take the infimum over F because (F.31) holds for any f ∈ F , and the second inequality holds because logNδ ≤ n.
  Now we invoke a simple fact to obtain the final bound for E[‖Q̂−TQ‖2n] from (F.44). Let a, b, and c be positive numbers satisfying a2 ≤ 2ab+c. For any ∈ (0, 1], since 2ab ≤ ·a2/(1+ )+(1+ )·b2/ , we have
  a2 ≤ (1 + )2 · b2/ + (1 + ) · c. (F.45)
  Therefore, applying (F.45) to (F.44) with a2 = E[‖Q̂ − TQ‖2n], b = C · Vmax · √
  logNδ/n, and c = inff∈F E[‖f − TQ‖2n] + C ′ · Vmax · δ, we obtain
  E [ ‖Q̂− TQ‖2n ] ≤ (1 + ) · inf f∈F E [ ‖f − TQ‖2n ] + C · V 2max · logNδ/(n ) + C ′ · Vmax · δ,
  (F.46)
  where C and C ′ are two positive absolute constants. Now we conclude the first step.
  Step (ii). In this step, we relate the population risk ‖Q̂ − TQ‖2σ with E[‖Q̂ − TQ‖2n], which is characterized in the first step. To begin with, we generate n i.i.d. random variables {X̃i = (S̃i, Ãi)}i∈[n] following σ, which are independent of {(Si, Ai, Ri, S′i)}i∈[n]. Since ‖Q̂−fk∗‖∞ ≤ δ, for any x ∈ S ×A, we have∣∣∣[Q̂(x)− (TQ)(x)]2 − [fk∗(x)− (TQ)(x)]2∣∣∣
  = ∣∣Q̂(x)− fk∗(x)∣∣ · ∣∣Q̂(x) + fk∗(x)− 2(TQ)(x)∣∣ ≤ 4Vmax · δ, (F.47)
  where the last inquality follows from the fact that ‖TQ‖∞ ≤ Vmax and ‖f‖∞ ≤ Vmax for any f ∈ F . Then by the definition of ‖Q̂− TQ‖2σ and (F.47), we have
  ‖Q̂− TQ‖2σ = E { 1
  n n∑ i=1 [ Q̂(X̃i)− (TQ)(X̃i) ]2}
  ≤ E { ‖Q̂− TQ‖2n + 1
  n n∑ i=1 [ fk∗(X̃i)− (TQ)(X̃i) ]2 − 1 n n∑ i=1 [ fk∗(Xi)− (TQ)(X̃i) ]2} + 8Vmax · δ
  = E ( ‖Q̂− TQ‖2n ) + E
  [ 1
  n n∑ i=1 hk∗(Xi, X̃i) ] + 8Vmax · δ, (F.48)
  where we apply (F.47) to obtain the first inequality, and in the last equality we define hj(x, y) = [ fj(y)− (TQ)(y) ]2 − [fj(x)− (TQ)(x)]2, (F.49) for any (x, y) ∈ S × A and any j ∈ [Nδ]. Note that hk∗ is a random function since k∗ is random. By the definition of hj in (F.49), we have |hj(x, y)| ≤ 4V 2max for any (x, y) ∈ S × A and E[hj(Xi, X̃i)] = 0 for any i ∈ [n]. Moreover, the variance of hj(Xi, X̃i) is upper bounded by
  Var [ hj(Xi, X̃i) ] = 2 Var {[ fj(Xi)− (TQ)(Xi) ]2} ≤ 2E {[ fj(Xi)− (TQ)(Xi)
  ]4} ≤ 8Υ2 · V 2max, where we define Υ by letting
  Υ2 = max (
  4V 2max · logNδ/n, max j∈[Nδ]
  E {[ fj(Xi)− (TQ)(Xi) ]2}) . (F.50)
  Furthermore, we define
  T = sup j∈[Nδ] ∣∣∣∣ n∑ i=1 hj(Xi, X̃i)/Υ ∣∣∣∣. (F.51) Combining (F.48) and (F.51), we obtain
  ‖Q̂− TQ‖2σ ≤ E [ ‖Q̂− TQ‖2n ] + Υ/n · E(T ) + 8Vmax · δ. (F.52)
  In the sequel, we utilize Bernstein’s inequality to establish an upper bound for E(T ), which is stated as follows for completeness.
  Lemma F.3 (Bernstein’s Inequality). Let U1, . . . Un be n independent random variables satisfying E(Ui) = 0 and |Ui| ≤M for all i ∈ [n]. Then for any t > 0, we have
  P (∣∣∣∣ n∑
  i=1
  Ui ∣∣∣∣ ≥ t) ≤ 2 exp( −t22M · t/3 + 2σ2 ) ,
  where σ2 = ∑n i=1 Var(Ui) is the variance of ∑n i=1 Ui.
  We first apply Bernstein’s inequality by setting Ui = hj(Xi, X̃i)/Υ for each i ∈ [n]. Then we take a union bound for all j ∈ [Nδ] to obtain
  P(T ≥ t) = P [
  sup j∈[Nδ]
  1
  n ∣∣∣∣ n∑ i=1 hj(Xi, X̃i)/Υ ∣∣∣∣ ≥ t] ≤ 2Nδ · exp{ −t28V 2max · [t/(3Υ) + n] } . (F.53)
  Since T is nonnegative, we have E(T ) = ∫∞
  0 P(T ≥ t)dt. Thus, for any u ∈ (0, 3Υ · n), by (F.53)
  it holds that E(T ) ≤ u+ ∫ ∞ u P(T ≥ t)dt ≤ u+ 2Nδ ∫ 3Υ·n u exp ( −t2 16V 2max · n ) dt+ 2Nδ ∫ ∞ 3Υ·n exp ( −3Υ · t 16V 2max ) dt
  ≤ u+ 32Nδ · V 2max · n/u · exp ( −u2
  16V 2max · n
  ) + 32Nδ · V 2max/(3Υ) · exp ( −9Υ2 · n 16V 2max ) ,
  (F.54)
  where in the second inequality we use the fact that ∫∞ s
  exp(−t2/2)dt ≤ 1/s · exp(−s2/2) for all s > 0. Now we set u = 4Vmax √ n · logNδ in (F.54) and plug in the definition of Υ in (F.50) to obtain
  E(T ) ≤ 4Vmax √ n · logNδ + 8Vmax √ n/ logNδ + 6Vmax √ n/ logNδ ≤ 8Vmax √ n · logNδ,
  (F.55)
  where the last inequality holds when logNδ ≥ 4. Moreover, the definition of Υ in (F.50) implies that Υ ≤ max[2Vmax √ logNδ/n, ‖Q̂− TQ‖σ + δ]. In the following, we only need to consider the case
  where Υ ≤ ‖Q̂− TQ‖σ + δ, since we already have (D.3) if ‖Q̂− TQ‖σ + δ ≤ 2Vmax √
  logNδ/n, which concludes the proof.
  Then, when Υ ≤ ‖Q̂− TQ‖σ + δ holds, combining (F.52) and (F.55) we obtain ‖Q̂− TQ‖2σ ≤ E [ ‖Q̂− TQ‖2n ] + 8Vmax √ log(N)/n · ‖Q̂− TQ‖σ + 8Vmax √ logNδ/n · δ + 8Vmax · δ
  ≤ E [ ‖Q̂− TQ‖2n ] + 8Vmax √ logNδ/n · ‖Q̂− TQ‖σ + 16Vmax · δ. (F.56)
  We apply the inequality in (F.45) to (F.56) with a = ‖Q̂ − TQ‖σ, b = 8Vmax √
  logNδ/n, and c = E[‖Q̂− TQ‖2n] + 16Vmax · δ. Hence we finally obtain that
  ‖Q̂− TQ‖2σ ≤ (1 + ) · E [ ‖Q̂− TQ‖2n ] + (1 + )2 · 64Vmax · log(N)/(n · ) + (1 + ) · 18Vmax · δ, (F.57)
  which concludes the second step of the proof.
  Finally, combining these two steps together, namely, (F.46) and (F.57), we conclude that
  ‖Q̂− TQ‖2σ ≤ (1 + )2 · inf f∈F
  E [ ‖f − TQ‖2n ] + C1 · V 2max · logNδ/(n · ) + C2 · Vmax · δ,
  where C1 and C2 are two absolute constants. Moreover, since Q ∈ F , we have
  inf f∈F
  E [ ‖f − TQ‖2n ] ≤ sup Q∈F { inf f∈F E [ ‖f − TQ‖2n ]} ,
  which concludes the proof of Theorem D.2.
sections.heading: G PROOF OF THEOREM E.4
sections.text: In this section, we present the proof of Theorem E.4. The proof is similar to that of Theorem 4.4, which is presented in §D in details. In the following, we follow the proof in §D and only highlight the differences for brevity.
  Proof. The proof requires two key ingredients, namely the error propagation and the statistical error incurred by a single step of Minimax-FQI. Theorem G.1 (Error Propagation). Recall that {Q̃k}0≤k≤K are the iterates of Algorithm 4 and (πK , νK) is the equilibrium policy with respect to Q̃K . Let Q∗K be the action-value function corresponding to (πK , ν∗πK ), where ν ∗ πK is the best-response policy of the second player against πK . Then under Assumption E.3, we have
  ‖Q∗ −Q∗K‖1,µ ≤ 2φµ,ρ · γ (1− γ)2 · εmax + 4γK+1 (1− γ)2 ·Rmax, (G.1)
  where we define the maximum one-step approximation error εmax = maxk∈[K] ‖TQ̃k−1 − Q̃k‖σ, and constant φµ,ν is specified in Assumption E.3.
  Proof. We note that the proof of Theorem D.1 cannot be directly applied to prove this theorem. The main reason is that here we also need to consider the role played by the opponent, namely player two. Different from the MDP setting, here Q∗K is a fixed point of a nonlinear operator due to the fact that player two adopts the optimal policy against πK . Thus, we need to conduct a more refined analysis. See §G.1 for a detailed proof.
  By this theorem, we need to derive an upper bound of εmax. We achieve such a goal by studying the one-step approximation error ‖TQ̃k−1 − Q̃k‖σ for each k ∈ [K]. Theorem G.2 (One-step Approximation Error). Let F ⊆ B(S × A × B, Vmax) be a family of measurable functions on S × A × B that are bounded by Vmax = Rmax/(1 − γ). Also, let {(Si, Ai, Bi)}i∈[n] be n i.i.d. random variables following distribution σ ∈ P(S × A × B). . For each i ∈ [n], let Ri and S′i be the reward obtained by the first player and the next state following (Si, Ai, Bi). In addition, for any fixed Q ∈ F , we define the response variable as
  Yi = Ri + γ · max π′∈P(A) min ν′∈P(B)
  Ea∼π′,b∼ν′ [ Q(S′i, a, b) ] . (G.2)
  Based on {(Xi, Ai, Yi)}i∈[n], we define Q̂ as the solution to the least-squares problem
  min f∈F
  1
  n n∑ i=1 [ f(Si, Ai)− Yi ]2 . (G.3)
  Then for any ∈ (0, 1] and any δ > 0, we have
  ‖Q̂− TQ‖2σ ≤ (1 + )2 · sup g∈F inf f∈F ‖f − Tg‖2σ + C · V 2max/(n · ) · logNδ + C ′ · Vmax · δ, (G.4)
  where C and C ′ are two positive absolute constants, T is the Bellman operator defined in (E.5), Nδ is the cardinality of the minimal δ-covering of F with respect to `∞-norm.
  Proof. By the definition of Yi in (G.2), for any (s, a, b) ∈ S ×A×minν′∈P(B), we have
  E(Yi |Si = s,Ai = a,Bi = b) = r(s, a) + γ · Es′∼P (· | s,a,b) {
  max π′∈P(A) min ν′∈P(B)
  Ea′∼π′,b′∼ν′ [ Q(s′, a, b) ]} = (TQ)(s, a, b).
  Thus, TQ can be viewed as the ground truth of the nonlinear least-squares regression problem in (G.3). Therefore, following the same proof of Theorem D.2, we obtain the desired result.
  Now we let F be the family of ReLU Q-networks F1 defined in (E.8) and set Q = Q̃k−1 in Theorem G.2. In addition, setting = 1 and δ = 1/n in (G.4), we obtain
  ‖Q̃k+1 − TQ̃k‖2σ ≤ 4 · sup g∈F1 inf f∈F1 ‖f − Tg‖2σ + C · V 2max/n · logN1
  ≤ 4 · sup f ′∈G1 inf f∈F1 ‖f − f ′‖2∞ + C · V 2max/n · logN1, (G.5)
  where C is a positive absolute constant, N1 is the 1/n-covering number of F1, and function class G1 is defined as
  G1 = { f : S ×A → R : f(·, a, b) ∈ G({pj , tj , βj , Hj}j∈[q]) for any (a, b) ∈ A× B } . (G.6)
  Here the second inequality follows from Assumption E.2.
  Thus, it remains to bound the `∞-error of approximating functions in G1 using ReLU Q-networks in F1 and the 1/n-covering number of F1. In the sequel, obtain upper bounds for these two terms.
  By the definition of G1 in (G.6), for any f ∈ G1 and any (a, b) ∈ A × B, we have f(·, a, b) ∈ G({(pj , tj , βj , Hj)}j∈[q]). Following the same construction as in §F.2, we can find a function f̃ in F(L∗, {d∗j} L∗+1 j=1 , s ∗) such that
  ‖f(·, a, b)− f̃‖∞ . max j∈[q]
  n−2β ∗ j /(2β ∗ j+tj) = nα ∗−1,
  which implies that
  sup f ′∈G1 inf f∈F1
  ‖f − f ′‖2∞ . nα ∗−1. (G.7)
  Moreover, for any f ∈ F1 and any (a, b) ∈ A × B, we have f(·, a, b) ∈ F(L∗, {d∗j} L∗+1 j=1 , s ∗). Let Nδ be the δ-covering of F(L∗, {d∗j} L∗+1 j=1 , s
  ∗) in the `∞-norm. Then for any f ∈ F1 and any (a, b) ∈ A × B, there exists gab ∈ Nδ such that ‖f(·, a, b) − ga,b‖∞ ≤ δ. Thus, the cardinality of the N (δ,F1, ‖ · ‖∞) satisfies ∣∣N (δ,F1, ‖ · ‖)∣∣ ≤ |Nδ||A|·|B|. (G.8) Combining (G.8) with Lemma D.4 and setting δ = 1/n, we obtain that
  logN1 ≤ |A| · |B| · log |Nδ| ≤ |A| · |B| · (s∗ + 1) · log [ 2n · (L∗ + 1) ·D2 ] ≤ |A| · |B| · s∗ · L∗ max
  j∈[L∗] log(d∗j ) . |A| · |B| · nα ∗ · (log n)1+2ξ ′ , (G.9)
  where D = ∏L∗+1 `=1 (d ∗ ` + 1) and the second inequality follows from (4.7).
  Finally, combining (G.1), (G.5), (G.7), and (G.9), we conclude the proof of Theorem E.4.
  G.1 PROOF OF THEOREM G.1
  Proof. The proof is similar to the that of Theorem G.1. Before presenting the proof, we first introduce the following notation for simplicity. For any k ∈ {0, . . . ,K − 1}, we denote TQ̃k by Qk+1 and define %k = Qk − Q̃k. In addition, throughout the proof, for two action-value functions Q1 and Q2, we write Q1 ≤ Q2 if Q1(s, a, b) ≥ Q2(s, a, b) for any (s, a, b) ∈ S ×A× B, and define Q1 ≥ Q2 similarly. Furthermore, we denote by (πk, νk) and (π∗, ν∗) the equilibrium policies with respect to Q̃k by Q∗, respectively. Besides, in addition to the Bellman operators Tπ,ν and T defined in (E.4) and (E.5), for any policy π of the first player, we define
  TπQ(s, a, b) = r(s, a, b) + γ · Es′∼P (· | s,a,b) {
  min ν′∈P(B)
  Ea′∼π,b′∼ν′ [ Q(s′, a′, b′) ]} , (G.10)
  corresponds to the case where the first player follows policy π and player 2 adopts the best policy in response to π. By this definition, it holds that Q∗ = Tπ ∗ Q∗. Unlike the MDP setting, here Tπ is a nonlinear operator due to the minimization in (G.10). Furthermore, for any fixed action-value function Q, we define the best-response policy against π with respect to Q, denote by ν(π,Q), as
  ν(π,Q)(· | s) = argmin ν′∈P(B)
  Ea∼π,b∼ν′ [ Q(s, a, b) ] . (G.11)
  Using this notation, we can write (G.10) equivalently as TπQ(s, a, b) = r(s, a, b) + γ · ( Pπ,ν(π,Q) ) (s, a, b).
  Notice that Pπ,ν(π,Q) is a linear operator and that νQ = ν(πQ, Q) by definition.
  Now we are ready to present the proof, which can be decomposed into three key steps.
  Step (i): In the first step, we establish recursive upper and lower bounds for {Q∗ − Q̃k}0≤k≤K . For each k ∈ {0, . . . ,K − 1}, similar to the decomposition in (F.3), we have
  Q∗ − Q̃k+1 = Q∗ − Tπ ∗ Q̃k + (T π∗Q̃k − TQ̃k) + %k+1, (G.12)
  where π∗ is part of the equilibrium policy with respect to Q∗ and Tπ ∗ is defined in (G.10).
  Similar to Lemma F.1, we utilize the following lemma to show Tπ ∗ Q̃k ≥ TQ̃k.
  Lemma G.3. For any action-value function Q : S ×A× B → R, let (πQ, νQ) be the equilibrium policy with respect to Q. Then for and any policy π of the first player, it holds that
  TπQQ = TQ ≥ TπQ.
  Furthermore, for any policy π : S → P(A) of player one and any action-value function Q, we have
  Tπ,ν(π,Q)Q = TπQ ≤ Tπ,νQ (G.13)
  for any policy ν : S → P(B), where ν(π,Q) is the best-response policy defined in (G.11).
  Proof. Note that for any s′ ∈ S, by the definition of equilibrium policy, we have
  max π′∈P(A) min ν′∈P(B)
  Ea′∼π′,b′∼ν′ [ Q(s′, a′, b′) ] = min ν′∈P(B) Ea′∼πQ,b′∼ν′ [ Q(s′, a′, b′) ] .
  Thus, for any state-action tuple (s, a, b), taking conditional expectations of s with respect to P (· | s, a, b) on both ends of this equation, we have
  (TπQQ)(s, a, b) = r(s, a, b) + γ · Es′∼P (· | s,a,b) {
  min ν′∈P(B)
  Ea′∼πQ,b′∼ν′ [ Q(s′, a′, b′) ]} = r(s, a, b) + γ · Es′∼P (· | s,a,b) { max
  π′∈P(A) min ν′∈P(B) Ea′∼π′,b′∼ν′
  [ Q(s′, a′, b′) ]} = (TQ)(s, a, b),
  which proves TπQQ = TQ. Moreover, for any policy π of the first player, it holds that
  max π′∈P(A) min ν′∈P(B)
  Ea′∼π′,b′∼ν′ [ Q(s′, a′, b′) ] ≥ min ν′∈P(B) Ea′∼π,b′∼ν′ [ Q(s′, a′, b′) ] .
  Taking expectations with respect to s′ ∼ P (· | s, a, b) on both ends, we establish TQ ≥ TπQ.
  It remains to show the second part of Lemma G.3. By the definition of ν(π,Q), we have Ea′∼π,b′∼ν(π,Q) [ Q(s′, a′, b′) ] = min ν′∈P(B) Ea′∼π,b′∼ν′ [ Q(s′, a′, b′) ] ,
  which, combined with the definition of Tπ in (G.10), implies that Tπ,ν(π,Q)Q = TπQ. Finally, for any policy ν of player two, we have
  min ν′∈P(B)
  Ea′∼π,b′∼ν′ [ Q(s′, a′, b′) ] ≥ Ea′∼π,b′∼ν [ Q(s′, a′, b′) ] ,
  which yields TπQ ≤ Tπ,νQ. Thus, we conclude the proof of this lemma.
  Hereafter, for notational simplicity, for each k, let (πk, νk) be the equilibrium joint policy with respect to Q̃k, and we denote ν(π∗, Q̃k) and ν(πk, Q∗) by ν̃k and ν̄k, respectively. Applying Lemma G.3 to (G.12) and utilizing the fact that Q∗ = Tπ ∗ Q∗, we have
  Q∗ − Q̃k+1 ≤ (Q∗ − Tπ ∗ Q̃k) + %k+1 = (T π∗Q∗ − Tπ ∗ Q̃k) + %k+1 ≤ ( Tπ ∗,ν̃kQ∗ − Tπ ∗,ν̃kQ̃k ) + %k+1 = γ · Pπ ∗,ν̃k(Q∗ − Q̃k) + %k+1, (G.14)
  where the last inequality follows from (G.13). Furthermore, for a lower bound of Q∗− Q̃k+1, similar to (F.5), we have
  Q∗ − Q̃k+1 = (TQ∗ − TπkQ∗) + (TπkQ∗ − TπkQ̃k) + %k+1 ≥ (TπkQ∗ − TπkQ̃k) + %k+1 ≥ γ · Pπk,ν̄k(Q∗ − Q̃k) + %k+1, (G.15)
  where the both inequalities follow from Lemma G.3. Thus, combining (G.14) and (G.15) we have
  γ · Pπ ∗,ν̃k(Q∗ − Q̃k) + %k+1 ≥ Q∗ − Q̃k+1 ≥ γ · Pπk,ν̄k(Q∗ − Q̃k) + %k+1. (G.16)
  for any k ∈ {0, . . . ,K − 1}. Similar to the proof of Lemma F.2 , by applying recursion to (G.16), we obtain the following upper and lower bounds for the error propagation of Algorithm 4.
  Lemma G.4 (Error Propagation). For any k, ` ∈ {0, 1, . . . ,K − 1} with k < `, we have
  Q∗ − Q̃` ≤ `−1∑ i=k γ`−1−j · ( Pπ ∗,ν̃`−1Pπ ∗,ν̃`−2 · · ·Pπ ∗,ν̃i+1 ) %i+1
  + γ`−k · (Pπ ∗,ν̃`−1Pπ ∗,ν̃`−2 · · ·Pπ ∗,ν̃k ) (Q∗ − Q̃k), (G.17)
  Q∗ − Q̃` ≥ `−1∑ i=k γ`−1−i · ( Pπ`−1,ν̄`−1Pπ`−2,ν̄`−2 · · ·Pπi+1,ν̄i+1 ) %i+1
  + γ`−k · ( Pπ`−1,ν̄`−1Pπ`−2,ν̄`−2 · · ·Pπi+1,ν̄k ) (Q∗ − Q̃k). (G.18)
  Proof. The desired results follows from applying the inequalities in (G.16) multiple times and the linearity of the operator Pπ,ν for any joint policy (π, ν).
  The above lemma establishes recursive upper and lower bounds for the error terms {Q∗ − Q̃k}0≤k≤K−1, which completes the first step of the proof.
  Step (ii): In the second step, we characterize the suboptimality of the equilibrium policies constructed by Algorithm 4. Specifically, for each πk, we denote by Q∗k the action-value function obtained when agent one follows πk while agent two adopt the best-response policy against πk. In other words, Q∗k is the fixed point of Bellman operator T
  πk defined in (G.10). In the following, we obtain an upper bound of Q∗ −Q∗k, which establishes the a notion of suboptimality of policy (πk, νk) from the perspective of the first player.
  To begin with, for any k, we first decompose Q∗ −Q∗k by
  Q∗ −Q∗k = ( Tπ ∗ Q∗ − Tπ ∗ Q̃k ) + ( Tπ ∗ Q̃k − TπkQ̃k ) + ( TπkQ̃k − TπkQ∗k ) . (G.19)
  Since πk is the equilibrium policy with respect to Q̃k, by Lemma G.3, we have Tπ ∗ Q̃k ≤ TπkQ̃k. Recall that (π∗, ν∗) is the joint equilibrium policy with respect to Q∗. The second argument of Lemma G.3 implies that
  Tπ ∗ Q∗ ≤ Tπ ∗,ν̃kQ∗, TπkQ̃k ≤ Tπk,ν̂kQ̃k, (G.20)
  where ν̃k = ν(π∗, Q̃k) and we define ν̂k = ν(πk, Q∗k). Thus, combining (G.19) and (G.20) yields that
  0 ≤ Q∗ −Q∗k ≤ γ · Pπ ∗,ν̃k ( Q∗ − Q̃k ) + γ · Pπk,ν̂k ( Q̃k −Q∗k ) = γ · ( Pπ ∗,ν̃k − Pπk,ν̂k )( Q∗ − Q̃k ) + γ · Pπk,ν̂k ( Q∗ −Q∗k ) . (G.21)
  Furthermore, since I − γ · Pπk,ν̂k is invertible, by (G.21) we have 0 ≤ Q∗ −Q∗k ≤ γ · ( I − γ · Pπk,ν̂k )−1 · [Pπ∗,ν̃k(Q∗ − Q̃k)− Pπk,ν̂k(Q∗ − Q̃k)]. (G.22) Now we apply Lemma G.4 to the right-hand side of (G.22). Then for any k ≤ `, we have
  Pπ ∗,ν̃` ( Q∗ − Q̃` ) ≤ `−1∑ i=k γ`−1−j · ( Pπ ∗,ν̃`Pπ ∗,ν̃`−1 · · ·Pπ ∗,ν̃i+1 ) %i+1
  + γ`−k · ( Pπ ∗,ν̃`Pπ ∗,ν̃`−1 · · ·Pπ ∗,ν̃k ) (Q∗ − Q̃k), (G.23)
  Pπ`,ν̂` ( Q∗ − Q̃` ) ≥ `−1∑ i=k γ`−1−i · ( Pπ`,ν̄`Pπ`,ν̄`−2 · · ·Pπi+1,ν̄i+1 ) %i+1
  + γ`−k · ( Pπ`,ν̄`Pπ`−1,ν̄`−1 · · ·Pπk,ν̄k ) (Q∗ − Q̃k). (G.24)
  Thus, setting ` = K and k = 0 in (G.23) and (G.24), we have Q∗ −Q∗K ≤ ( I − γ · PπK ,ν̂K )−1· (G.25){K−1∑ i=0 γK−1 · [( Pπ ∗,ν̃KPπ ∗,ν̃K−1 · · ·Pπ ∗,ν̃i+1 ) − ( PπK ,ν̄KPπK−1,ν̄K−1 · · ·Pπi+1,ν̄i+1 )] %i+1
  + γK+1 · [( Pπ ∗,ν̃KPπ ∗,ν̃K−1 · · ·Pπ ∗,ν̃0 ) − ( PπK ,ν̄KPπK−1,ν̄K−1 · · ·Pπ0,ν̄0 )] (Q∗ − Q̃0) } .
  To simplify the notation, we define {αi}Ki=0 as in (F.18). Note that we have ∑K i=0 αi = 1 by definition. Moreover, we define K + 1 linear operators {Ok}Kk=0 as follows. For any i ≤ K − 1, let
  Oi = 1− γ
  2 · (I − γ · PπK ,ν̂K
  )−1[( Pπ ∗,ν̃KPπ ∗,ν̃K−1 · · ·Pπ ∗,ν̃i+1 ) − ( PπK ,ν̄KPπK−1,ν̄K−1 · · ·Pπi+1,ν̄i+1 )] .
  Moreover, we define OK by
  OK = 1− γ
  2 · (I − γ · PπK ,ν̂K
  )−1[( Pπ ∗,ν̃KPπ ∗,ν̃K−1 · · ·Pπ ∗,ν̃0 ) − ( PπK ,ν̄KPπK−1,ν̄K−1 · · ·Pπ0,ν̄0 )] .
  Therefore, taking absolute values on both sides of (G.25), we obtain that∣∣Q∗(s, a, b)−Q∗K(s, a, b)∣∣ ≤ 2γ(1− γ K+1)
  (1− γ)2 · [K−1∑ i=0 αi · ( Oi|%i+1| ) (s, a, b) + αK · ( OK |Q∗ − Q̃0| ) (s, a, b) ] , (G.26)
  for any (s, a, b) ∈ S ×A× B, which concludes the second step of the proof.
  Step (iii): We note that (G.26) is nearly the same as (F.19) for the MDP setting. Thus, in the last step, we follow the same proof strategy as in Step (iii) in §F.1. For notational simplicity, for any function f : S ×A× B → R and any probability distribution µ ∈ P(S ×A× B), we denote the expectation of f under µ by µ(f). By taking expectation with respect to µ in (G.26), we have
  ‖Q∗ −Q∗K‖1,µ ≤ 2γ(1− γK+1) (1− γ)2 · [K−1∑ i=0 αi · µ ( Oi|%i+1| ) + αK · µ ( OK |Q∗ − Q̃0| )] . (G.27)
  By the definition of Oi, we can write µ(Oi|%i+1|) as µ ( Oi|%i+1| ) = 1− γ 2 · µ { ∞∑ j=0 γj · [( PπK ,ν̂K )j( Pπ ∗,ν̃KPπ ∗,ν̃K−1 · · ·Pπ ∗,ν̃i+1 ) (G.28)
  + ( PπK ,ν̂K )j( PπK ,ν̄KPπK−1,ν̄K−1 · · ·Pπi+1,ν̄i+1 )] |%i+1| } .
  To upper bound the right-hand side of (G.28), we consider the following quantity
  µ [ P τm · · ·P τ1)f ] = ∫ S×A×B [ (P τmP τm−1 · · ·P τ1)f ] (s, a, b)dµ(s, a, b),
  where {τt : S → P(A × B)}t∈[m] are m joint policies of the two-players. By Cauchy-Schwarz inequality, it holds that
  µ [ P τm · · ·P τ1)f ] ≤ [∫ S×A×B ∣∣∣∣d(P τmP τm−1 · · ·P τ1µ)dσ (s, a, b) ∣∣∣∣∣ 2 dσ(s, a, b) ]1/2 · [∫ S×A×B |f(s, a, b)|2dσ(s, a, b) ]1/2 ≤ κ(m;µ, σ) · ‖f‖σ,
  where κ(m;µ, σ) is the m-th concentration parameter defined in (E.9). Thus, by (G.28)we have
  µ ( Oi|%i+1| ) ≤ (1− γ) · ∞∑ j=0 γj · κ(K − i+ j;µ, ν) · ‖%i+1‖σ. (G.29)
  Besides, since both Q∗ and Q̃0 are bounded by Rmax/(1− γ) in `∞-norm, we have µ ( OK |Q∗ − Q̃0| ) ≤ 2 ·Rmax/(1− γ). (G.30)
  Finally, combining (G.27), (G.29), and (G.30), we obtain that
  ‖Q∗ −QπK‖1,µ
  ≤ 2γ(1− γ K+1) (1− γ) · [K−1∑ i=0 ∞∑ j=0 αi · γj · κ(K − i+ j;µ, ν) · ‖%i+1‖σ ] + 4γ(1− γK+1) (1− γ)3 · αK ·Rmax
  ≤ 2γ(1− γ K+1) (1− γ) · [K−1∑ i=0 ∞∑ j=0 (1− γ)γK−i−1 1− γK+1 · γj · κ(K − i+ j;µ, ν) ] · εmax + 4γK+1 (1− γ)2 ·Rmax,
  where the last inequality follows from the fact that εmax = maxi∈[K] ‖%i‖σ. Note that in (F.29) we show that it holds under Assumption E.3 that
  K−1∑ i=0 ∞∑ j=0 (1− γ)γK−i−1 1− γK+1 · γj · κ(K − i+ j;µ, ν) ≤ φµ,ν (1− γK+1)(1− γ) .
  Hence, we obtain (G.1) and thus conclude the proof of Theorem G.1.