summaries: This paper proposes a method for video prediction that relies on a newly proposed Motion-Aware Unit (MAU). MAU acts as a temporal receptive field based on an attention mechanism that is used to aggregate features from previous frames in order to predict future frames. The aggregate features are combined with “content” features extracted from the last observed frame and the decoder is connected to the encoder via an “Information recalling scheme” that directly passes the last observed frame features from each layer of the encoder to each layer of the decoder. In experiments, the authors show superior performance against the baselines pixel based metrics and a perceptual metric.

summaries: The paper proposes the Motion-Aware Unit (MAU) for video prediction. This module attempts to model the temporal information in videos by enlarging the temporal receptive field and aggregating it through an attention mechanism. The proposed module is employed in the bottleneck part of an autoencoder where the spatial and temporal information are combined at different MAU layers. The proposed method is compared to previous works on several benchmarks for next frames prediction and early action recognition showing state-of-the-art results.

summaries: In this work, the authors introduce a Motion-Aware Unit (MAU) for video prediction. Basically, they discover the previous motion and aggregate it via attention module and fusion module. In the attention module, they compute correlation between spatial states and use it as attention for aggregation the previous temporal states. In the fusion module, they design spatial and temporal update gates for fusing attentive temporal state and current spatial state.

summaries: This paper proposes a Motion-Aware Unit (MAU) for video prediction tasks. The MAU includes two modules, the attention module and the fusion module. The attention module aims to learn the correlation between the current spatial state and previous spatial states. The learnt attention map can be used for augmenting the motion information (AMI). The fusion module is used for aggregating the augmented motion information (AMI) and current spatial state. The authors have demonstrated superior performance compared to state-of-the-arts.

abstractText: Accurately predicting inter-frame motion information plays a key role in video prediction tasks. In this paper, we propose a Motion-Aware Unit (MAU) to capture reliable inter-frame motion information by broadening the temporal receptive field of the predictive units. The MAU consists of two modules, the attention module and the fusion module. The attention module aims to learn an attention map based on the correlations between the current spatial state and the historical spatial states. Based on the learned attention map, the historical temporal states are aggregated to an augmented motion information (AMI). In this way, the predictive unit can perceive more temporal dynamics from a wider receptive field. Then, the fusion module is utilized to further aggregate the augmented motion information (AMI) and current appearance information (current spatial state) to the final predicted frame. The computation load of MAU is relatively low, and the proposed unit can be easily applied to other predictive models. Moreover, an information recalling scheme is employed into the encoders and decoders to help preserve the visual details of the predictions. We evaluate the MAU on both video prediction and early action recognition tasks. Experimental results show that the MAU outperforms the state-of-the-art methods on both tasks. ∗Corresponding author: Shanshe Wang. 35th Conference on Neural Information Processing Systems (NeurIPS 2021).

authors:
Chelsea Finn
Ian Goodfellow
Sergey Levine

title: Unsupervised learning for physical interaction through video prediction

venue: In International Conference on Neural Information Processing Systems,

authors:
Ziwei Liu
Raymond A Yeh
Xiaoou Tang
Yiming Liu
Aseem Agarwala

title: Video frame synthesis using deep voxel flow

venue: In International Conference on Computer Vision,

authors:
Apratim Bhattacharyya
Mario Fritz
Bernt Schiele

title: Long-term on-board prediction of people in traffic scenes under uncertainty

venue: In IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Hema S Koppula
Ashutosh Saxena

title: Anticipating human activities using object affordances for reactive robotic response

venue: IEEE transactions on pattern analysis and machine intelligence,

authors:
MarcAurelio Ranzato
Arthur Szlam
Joan Bruna
Michael Mathieu
Ronan Collobert
Sumit Chopra

title: Video (language) modeling: a baseline for generative models of natural videos

venue: arXiv preprint arXiv:1412.6604,

authors:
Sepp Hochreiter
Jürgen Schmidhuber

title: Long short-term memory

venue: Neural computation,

authors:
Kyunghyun Cho
Bart van Merrienboer
Çaglar Gülçehre
Dzmitry Bahdanau
Fethi Bougares
Holger Schwenk
Yoshua Bengio

title: Learning phrase representations using rnn encoder-decoder for statistical machine translation

venue: In Conference on Empirical Methods in Natural Language Processing,

authors:
Nitish Srivastava
Elman Mansimov
Ruslan Salakhudinov

title: Unsupervised learning of video representations using lstms

venue: In International conference on machine learning,

authors:
Xingjian Shi
Zhourong Chen
Hao Wang
Dit Yan Yeung
Wai Kin Wong
Wangchun Woo

title: Convolutional lstm network: A machine learning approach for precipitation nowcasting

venue: Advances in Neural Information Processing Systems,

authors:
Nicolas Ballas
Li Yao
Chris Pal
Aaron C Courville

title: Delving deeper into convolutional networks for learning video representations

venue: In International Conference on Learning Representations,

authors:
Xingjian Shi
Zhihan Gao
Leonard Lausen
Hao Wang
Dit-Yan Yeung
Wai-Kin Wong
Wang-chun Woo

title: Deep learning for precipitation nowcasting: A benchmark and a new model

authors:
Marc Oliu
Javier Selva
Sergio Escalera

title: Folded recurrent neural networks for future video prediction

venue: In European Conference on Computer Vision,

authors:
Yunbo Wang
Mingsheng Long
Jianmin Wang
Zhifeng Gao
Philip S Yu

title: Predrnn: Recurrent neural networks for predictive learning using spatiotemporal lstms

venue: In Advances in Neural Information Processing Systems,

authors:
Yunbo Wang
Zhifeng Gao
Mingsheng Long
Jianmin Wang
S Yu Philip

title: Predrnn++: Towards a resolution of the deep-in-time dilemma in spatiotemporal predictive learning

venue: In International Conference on Machine Learning,

authors:
Yunbo Wang
Jianjin Zhang
Hongyu Zhu
Mingsheng Long
Jianmin Wang
Philip S Yu

title: Memory in memory: A predictive neural network for learning higher-order non-stationarity from spatiotemporal dynamics

authors:
Yunbo Wang
Lu Jiang
Ming-Hsuan Yang
Li-Jia Li
Mingsheng Long
Li Fei-Fei

title: Eidetic 3d lstm: A model for video prediction and beyond

venue: In International conference on learning representations,

authors:
Wei Yu
Yichao Lu
Steve Easterbrook
Sanja Fidler

title: Efficient and information-preserving future frame prediction and beyond

authors:
Mohammad Babaeizadeh
Chelsea Finn
Dumitru Erhan
Roy H Campbell
Sergey Levine

title: Stochastic variational video prediction

authors:
Emily Denton
Rob Fergus

title: Stochastic video generation with a learned prior

authors:
Ruben Villegas
Arkanath Pathak
Harini Kannan
Dumitru Erhan
Quoc V Le
Honglak Lee

title: High fidelity video prediction with large stochastic recurrent neural networks

authors:
Jean-Yves Franceschi
Edouard Delasalles
Mickaël Chen
Sylvain Lamprier
Patrick Gallinari

title: Stochastic latent residual video prediction

authors:
Alex X Lee
Richard Zhang
Frederik Ebert
Pieter Abbeel
Chelsea Finn
Sergey Levine

title: Stochastic adversarial video prediction

venue: arXiv preprint arXiv:1804.01523,

authors:
Zhihang Hu
Jason Wang

title: A novel adversarial inference framework for video prediction with action control

venue: In IEEE International Conference on Computer Vision Workshops,

authors:
Yong-Hoon Kwon
Min-Gyu Park

title: Predicting future frames using retrospective cycle gan

authors:
Xinyuan Chen
Chang Xu
Xiaokang Yang
Dacheng Tao

title: Long-term video prediction via criticization and retrospection

venue: IEEE Transactions on Image Processing,

authors:
Michael Mathieu
Camille Couprie
Yann LeCun

title: Deep multi-scale video prediction beyond mean square error

authors:
Beibei Jin
Yu Hu
Qiankun Tang
Jingyu Niu
Zhiping Shi
Yinhe Han
Xiaowei Li

title: Exploring spatial-temporal multi-frequency analysis for high-fidelity and temporal-consistency video prediction

authors:
Haixu Wu
Zhiyu Yao
Mingsheng Long
Jianmin Wan

title: Motionrnn: A flexible model for video prediction with spacetime-varying motions

venue: arXiv preprint arXiv:2103.02243,

authors:
Nal Kalchbrenner
Aäron Oord
Karen Simonyan
Ivo Danihelka
Oriol Vinyals
Alex Graves
Koray Kavukcuoglu

title: Video pixel networks

authors:
Bohan Wu
Suraj Nair
Roberto Martin-Martin
Li Fei-Fei
Chelsea Finn

title: Greedy hierarchical variational autoencoders for large-scale video prediction

venue: arXiv preprint arXiv:2103.04174,

authors:
Andreas Geiger
Philip Lenz
Christoph Stiller
Raquel Urtasun

title: Vision meets robotics: The kitti dataset

venue: The International Journal of Robotics Research,

authors:
Piotr Dollar
Christian Wojek
Bernt Schiele
Pietro Perona

title: Pedestrian detection: An evaluation of the state of the art

venue: IEEE Transactions on Pattern Analysis and Machine Intelligence,

authors:
Ben Benfold
Ian Reid

title: Stable multi-target tracking in real-time surveillance video

authors:
Raghav Goyal
Samira Ebrahimi Kahou
Vincent Michalski
Joanna Materzynska
Susanne Westphal
Heuna Kim
Valentin Haenel
Ingo Fruend
Peter Yianilos
Moritz Mueller-Freitag

title: The" something something" video database for learning and evaluating visual common sense

title: The mnist database of handwritten digits. http://yann

venue: lecun. com/exdb/mnist/,

authors:
Sergiu Oprea
Pablo Martinez-Gonzalez
Alberto Garcia-Garcia
John Alejandro Castro-Vargas
Sergio Orts-Escolano
Jose Garcia-Rodriguez
Antonis Argyros

title: A review on deep learning techniques for video prediction

authors:
William Lotter
Gabriel Kreiman
David Cox

title: Deep predictive coding networks for video prediction and unsupervised learning

authors:
Ruben Villegas
Jimei Yang
Seunghoon Hong
Xunyu Lin
Honglak Lee

title: Decomposing motion and content for natural video sequence prediction

authors:
Zekun Hao
Xun Huang
Serge Belongie

title: Controllable video generation with sparse trajectories

authors:
Wonmin Byeon
Qin Wang
Rupesh Kumar Srivastava
Petros Koumoutsakos

title: Contextvp: Fully context-aware video prediction

venue: In European Conference on Computer Vision (ECCV),

heading: 1 Introduction

text:
Video prediction is a representative task in video predictive learning area, which aims to predict the unknown future on the basis of the limited knowledge and has been applied in a wide range of research areas, such as robotic control [1], video interpolation [2], autonomous driving [3], motion planning [4] and so on. However, compared with images, videos are more complex due to the time-varying motion information and predicting reliable motion information has always been a significant but challenging problem for video prediction tasks. Fortunately, deep learning technologies have shown their great power in learning meaningful features for multimedia data and have achieved great success in computer vision and natural language processing tasks. Motivated by this, learning-based methods have been applied for video prediction in recent years.
Recurrent neural networks (RNNs) are first applied to learn video representations due to their unique advantages in modeling sequential data [5]. Then the Long Short-Term Memory (LSTM) [6] and Gated Recurrent Unit (GRU) [7] are integrated into RNNs to help capture more reliable inter-frame temporal dependency [1, 8, 9, 10, 11, 12, 13, 14, 15]. In general, to save the computation resources and help predictive units to better perceive visual information, the fully connected layers in the predictive memories are replaced by convolutional layers in the above methods. Although the spatial receptive field of the unit has been improved by the integrated convolutional layers, the temporal receptive field is still narrow, and it is difficult for the unit at current time step to perceive what has happened in a longer past, which severely restrict the model expressivity to inter-frame motion information and the performance in predicting videos with complex scenarios and high resolutions is far from satisfactory.
Some works have attempted to broaden the temporal receptive field for the predictive units using 3D convolutional layers [16, 17]. However, the temporal receptive field is mainly determined by the kernel size of the integrated convolutional operators and the temporal dimension still needs to be set to a small value to meet the computation load requirement. Since then, the explorations for broadening the temporal receptive field for predictive models have been shelved and a variety of works begin to explore other ways to improve the expressivity of the model on videos with complex scenarios, which can be roughly categorized into two types, the structure-oriented methods and the loss-oriented methods. The structure-oriented methods utilized deep stochastic models to predict different futures for different samples based on their latent variables [18, 19, 20, 21]. However, the computation load of these methods is typically high, preventing their practicability in real world. And the loss-oriented methods aim to improve the traditional mean square error (MSE) based loss functions to generate more naturalistic results. Generative adversarial networks (GANs) [22, 23, 24, 25], perceptual loss [26] and so on have been utilized to generate results with higher perceptual quality. In spite of the explorations made by the above methods, only limited model performance improvements have been achieved and the unsatisfactory temporal receptive field still restricts the model performance in capturing reliable motion information between frames.
To solve the above problem, we propose the Motion-Aware Unit (MAU) to improve the model expressivity in capturing motion information by efficiently broadening the temporal receptive field. In particular, for each MAU, two modules are designed, the attention module and the fusion module. The attention module is designed for efficient attention and the fusion module is designed for efficient fusion. In particular, the attention module aims to help the unit to pay different levels of attention to the temporal states in the broadened temporal receptive field based on the corresponding spatial correlation scores. Using the attention scores, the temporal states can be aggregated to a more reliable augmented motion information (AMI) with a low computation load. The fusion module aims to further aggregate the augmented motion information (AMI) and the appearance information (the spatial state from current time step) using only two update gates. Moreover, an information recalling scheme is applied to further preserve the visual details of the predictions. Experimental results show that the proposed MAU can outperform other state-of-the-art methods on both video prediction and early action recognition tasks.

heading: 2 Related Work

text:
In this section, we introduce the learning-based video prediction methods in detail. Due to the unique power in modeling sequential data, RNNs are first utilized to model videos. Ranzato et al. [5] utilized RNNs to propose a baseline model for unsupervised feature learning on video data. Srivastava et al.
[8] further integrated Long Short-Term Memories (LSTMs) [6] into RNN-based models to capture the temporal long-short term dependencies for videos, which is denoted as FC-LSTM. However, the fully connected layers in FC-LSTM are computation-expensive, which limits its practicability in real world. To further reduce the computation load and increase local perceptions to visual data for LSTMs, Shi et al. [9] proposed the ConvLSTM by replacing the fully connected layers with convolutional layers. Ballas et al. [10] further integrated convolutional layers into Recurrent Gated Unit (GRU) [7], denoted as ConvGRU, which has achieved a similar performance but with lower computation load compared with ConvLSTM. Motivated by the success achieved from the above video prediction methods, RNNs have been further explored to predict videos with higher visual quality and video prediction models are beginning to be applied into more research areas, such as robotics [1], precipitation nowcasting [11] and so on. However, the above works merely focus on exploring the temporal dependency but ignore the spatial features for videos. Wand et al. proposed PredRNN [13] to solve this problem by adding a spatial information processing module for ConvLSTMs. And to solve the gradient propagation difficulties in PredRNNs, Wang et al. further designed a Gradient Highway Unit [14] and the new model was denoted as PredRNN++.
Although the above RNN-based models have achieved some satisfactory results, the datasets utilized are either with simple scenarios or low resolutions and the model performance on videos with complex scenarios and high resolutions is still far from satisfactory. One main reason for this is that the predicted frames at current time step still mainly depend on the inputs from current time step and the temporal receptive field of the predictive model is narrow, which is not enough to predict reliable motion information for the next time step. To solve this problem, Wang et al. employed 3D convolutional layers into PredRNNs and utilized multi-term temporal states to help increase temporal receptive field for the predictive unit, which is denoted as E3D-LSTM [16]. However, the computation load of E3D-LSTM is extremely high due to the integrated 3D convolutional operators and the recall gate. To further improve the model expressivity for the predictive models, many other methods have also been proposed, which can be summarized into four types. The first type aims to protect the visual details for the predictions [12, 17, 27, 28]. The second type aims to predict different futures rather than an averaged future for each sample based on their latent variables [18, 19, 21]. The third type aims to refer to deeper models to increase the model expressivity [20, 29, 30]. And the last type aims to improve the loss functions to generate more naturalistic results [22, 23, 24, 25, 26]. However, in the above methods, the temporal receptive field problem was still not fully explored. In this paper, we propose the motion-aware unit (MAU), which can efficiently broaden the temporal receptive field to predict more reliable motion information for videos and the computation load is relatively low. In addition, MAU can be easily employed in other predictive models.

heading: 3 Method

heading: 3.1 Problem formulation

text:
A video prediction model typically takes a video clip {v1, ..., vi} as the inputs and outputs the future video clip {v̂i+1, ..., v̂T }. And we want to optimize the following problem,
min T∑ t=i+1 [D(v̂t, vt)], (1)
where v̂t denotes the predicted frame at time step t, D denotes the loss function, such as the L1, L2 loss functions and so on.
To optimize the above problem, the error between the predicted frame v̂t and the ground truth vt is expected to be as small as possible. For most of the RNN-based video prediction methods, the frames are usually progressively predicted where the proposed model predicts one frame for each time step. In particular, the predicted frame v̂t depends on the spatial information, i.e. the frame input at the previous time step vt−1 and the temporal information, i.e. the transited motion information Tt−1. However, as the time steps move on, the predicted error in Eq. 1 dramatically accelerates due to the increasing uncertainty of the transited temporal information Tt−1. To solve this problem, the predictive unit needs to search for more useful temporal information from a wider range of time steps, i.e. the temporal receptive field is needed to be broadened. For time step t, the temporal receptive field is probably to be set as t− 1. However, it may be not efficient and necessary to utilize all the previous frames, thus the receptive field is more likely to be set to a fixed value τ . Although recent
work E3D-LSTM [16] has attempted to address this problem and the temporal receptive field is broadened, the computation load is extremely high with only a limited performance improvement (mainly achieved by the integrated 3D convolutional layers), which indicates the broadened temporal receptive field may not been fully used.
To ensure that the broadened temporal receptive field can be fully utilized, two problems are needed to be solved,
• The temporal states in current receptive field should be aggregated according to their importance.
• The motion information from the aggregated temporal state and the appearance information from the spatial state should be fused reasonably.
To solve the above two problems, we propose the Motion-Aware Unit (MAU) and the predicted frame v̂t can be represented as follows,
v̂t = Dec[MAU(Enc(vt−τ :t−1))], (2)
where Enc(·) denotes the encoder which is utilized to extract deep features from the video input and Dec(·) denotes the decoder which is utilized to map the predicted features to the frames. MAU(·) denotes the proposed motion-aware unit, which will be detailedly introduced in Section 3.2.

heading: 3.2 The proposed Motion-Aware Unit: MAU

text:
In this section, we introduce the structure details of MAU, as shown in Fig. 1 (right). Each MAU consists of two modules: the attention module and the fusion module. Typically, to improve the model expressivity, multiple MAUs are stacked, as shown in Fig. 1 (left). In particular, at time step t in layer k, two inputs will be fed into the MAU: the temporal states set T kt−τ :t−1 from previous τ time steps and the spatial states set Sk−1t−τ :t from previous τ + 1 time steps.
To solve the first problem in Section 3.1, we design the attention module, which aims to help the predictive unit to pay different levels of attention to different historical temporal states. The expected situation is that the predictive can always pay the highest level of attention to the most correlated states. Now the problem comes to how to quantify the correlations between different temporal states. Considering the fact that the visual quality of each frame can be the most factors to evaluate a video prediction model, the correlations between the corresponding spatial states can be an optimal choice.
Based on the analysis, the attention score αj for the temporal state T kt−j can be denoted as follows,
αj = eqj∑τ i=1 e qi ,
qi = SUM(S k−1 t−i ⊙ S ′), i = 1, ..., τ, S′ = Ws ∗ Sk−1t , (3)
where ⊙, ∗ denote the Hadamard product and the convolutional operator, respectively. Using the computed attention score, the temporal state set can be aggregated as follows,
Tatt = τ∑ j=1 αj · T kt−j . (4)
Tatt can be treated as the long-term motion information. However, besides the long-term motion information Tatt, the short-term motion information T kt−1 is also needed to be utilized to strengthen the final motion information. We define a fusion gate Uf to control the fusion process, which can be shown as follows,
Uf = σ(Wf ∗ T kt−1), TAMI = Uf ⊙ T kt−1 + (1− Uf )⊙ Tatt, (5)
where σ denotes the sigmoid function, TAMI denotes the augmented motion information.
To solve the second problem in Section 3.1, we design the fusion module to aggregate the motion information in the augmented motion information TAMI with the appearance information in the current input Sk−1t . To control the fusion ratios for both temporal and spatial information, two update gates are denoted as follows,
Ut = σ(Wtu ∗ TAMI), Us = σ(Wsu ∗ Sk−1t ), (6)
where Ut denotes the temporal update gate and Us denotes the spatial update gate. Using both gates, the aggregating process can be conducted as follows,
T kt = Ut ⊙ (Wtt ∗ TAMI) + (1− Ut)⊙ (Wst ∗ Sk−1t ), Skt = Us ⊙ (Wss ∗ Sk−1t ) + (1− Us)⊙ (Wts ∗ TAMI) + γ · Sk−1t , (7)
where the residual-like term γ · Sk−1t is utilized to stabilize the training process. In particular, as shown in Fig. 1 (left), the frame input vt is encoded to deep features by the encoder and the predicted spatial state is decoded back to the frame by the decoder, represented as follows,
St0 = Enc(vt),
v̂t+1 = Dec(S N t ), (8)
where N denotes the total number of the employed MAUs.

heading: 3.3 Information recalling scheme

text:
Considering the information loss problem during encoding, an information recalling scheme between encoders and decoders have been employed, which is defined as the information recalling scheme and can be represented as follows,
Dl = Decl(Dl−1 + E−l), l = 1, ..., N, (9)
where Dl, E−l denote decoded features from the lth layer of the decoder and the encoded features from the lth from the last layer of the encoder. Decl denotes the lth layer of the decoder. On the basis of the above information recalling scheme, the decoders can recall multi-level encoded information back and the visual quality of the predictions is better.

heading: 4 Experiments

heading: 4.1 Implementations

text: We evaluate the proposed MAU on five datasets, the Moving MNIST dataset [8], the KITTI dataset [31], the Caltech Pedestrian dataset [32], the TownCentreXVID dataset [33] and the SomethingSomething V2 dataset [34]. The number of the hidden state channels of MAUs are set to 64 and the integrated convolutional operators are set with a kernel size 5× 5 and stride 1. All experiments are optimized with the Adam optimizer. To stabilize the training process, we employ layer normalization operators after each integrated convolutional layer in MAUs.

heading: 4.2 Video Prediction

text: We conduct video prediction experiments on the the Moving MNIST dataset, the KITTI dataset, the Caltech Pedestrian dataset, and the TownCentreXVID dataset. The detailed experimental settings are summarized in Table 1. All models are optimized with the MSE loss function.

heading: 4.2.1 Moving MNIST

text:
The Moving MNIST dataset can be the most widely-used dataset in video prediction, where each sequence consists of 20 successive frames with 2 digits randomly placed. Each frame is with a size of 64× 64. In our experiments, sequences are generated from the training set of the standard MNIST dataset [35] and we utilize the test set collected by Srivastava et al. [8] to evaluate the proposed model. The Mean Square Error (MSE), the Structural Similarity Index (SSIM) are employed to indicate the visual quality of the predictions.
Fig. 2 shows the visual results predicted from different methods, where the proposed MAU significantly outperforms other methods, especially for the prediction in the last two time steps. Table 2 summarizes the quantitative scores of the predictions from different methods. The proposed MAU has achieved the best scores compared with other state-of-the-art methods. And the employed recalling scheme can help further improve the model performance.
In addition, the parameters and inference time are also recorded in Table 3. For a fair comparison, all models are implemented with the same encoder and decoder with the same number of predictive units. In particular, for the proposed MAU, the recalling scheme is disabled and all models are trained
using Adam optimizer based on the MSE loss. We record the parameters for a single unit and the inference time is recorded over 800 samples. The summarized results show that the MAU can achieve the best scores with the fewest parameters and a relatively low computation load.
Table 4 shows the model performance with different temporal receptive field τ (w/o recalling). Although the quality of the predictions becomes better as the temporal receptive field increases, the computation load also dynamically increases. Thus, τ is typically set to an appropriate value to achieve a satisfactory trade-off between the visual quality and the computation load. In particular, we set τ = 5 in this paper.

heading: 4.2.2 KITTI and Caltech Pedestrian datasets

text:
We use two car-mounted camera video datasets to evaluate the performance of MAU in real scenarios. KITTI and Caltech Pedestrian datasets are very similar to the real-world scenarios, which are collected to train the autonomous vehicles.
We follow the experimental settings in [37], where all frames are cropped and resized to 128× 160. The proposed model is trained on the KITTI dataset and tested on the Caltech Pedestrian dataset. In
particular, the frame rate of the Caltech Pedestrian dataset is adjusted to the same as KITTI (10 fps). A total of 32373 sequences are for training and 7725 sequences for testing. In addition, the proposed model is trained to predict the next frame with the first 10 frames as the inputs. While testing, the temporal period of the predictions is extended to 10 frames.
Fig. 3 shows the generated examples from the proposed MAU and two latest state-of-the-art methods. From the visual results, the proposed MAU can predict more clear traffic signs (t = 16), which indicates the MAU can capture more reliable temporal dynamics for videos. Table 5 shows the quantitative results from different methods, where the proposed MAU outperforms other methods in all scores. In particular, the recalling scheme can further improve the model performance.

heading: 4.2.3 TownCentreXVID

text:
In this section, we evaluate the proposed model on a surveillance dataset, TownCentreXVID, which is more close to the real scenarios and with a resolution of 1920× 1080. TownCentreXVID dataset contains a total of 7500 frames. To further evaluate the model performance in predicting highresolution videos, all frames are not resized. The first 4500 frames are for training and the last 3500 frames are for testing. Fig. 4 shows the visual results from different methods, where the proposed method can generate much better visual details compared with other state-of-the-art methods.
We further conduct object detection tasks on the predictions from different methods using the pretrained Yolov5s model [41] and the results are shown in Fig. 5. More persons have been detected by the pre-trained Yolo model from the predictions generated from MAU and the confidence is higher than others.
In addition, Table 6 summarized the detailed quantitative results from MAU and other methods, where MAU has achieved the best objective (PSNR, SSIM) and perceptual (LPIPS) scores.

heading: 4.3 Early action recognition: Something-Something V2

text:
The Something-SomethingV2 dataset is a large collection of labeled video clips that show humans performing pre-defined basic actions with everyday objects. The whole dataset consists of 174 categories of videos. The training set contains 168,913 videos and the validation set consists of 24,777 videos. The resolution of each video is 240 × 427. To further evaluate the performance in modeling high-level spatiotemporal representations for videos, the early action recognition task is conducted, which aims to categorize the whole video after observing only the front part of the videos. To accurately predict an activity category for current video, models need to extract useful spatiotemporal representations from merely the front part of the whole frames to predict a reliable future. In particular, we utilize the front 25% and 50% frames of each video to conduct this task, respectively. For each video, a total of 20 frames are sampled which can cover the whole temporal period. Each frame is resized to 128× 128. For 25% early action recognition task, 5 frames are as
the inputs to predict the next 15 frames. For 50% early action recognition task, 10 frames are as the inputs to predict the next 10 frames.
All models are first pre-trained to perform video prediction task with the front 25% or 50% frames as the inputs to predict the remaining 75% or 50% frames. After convergence, a total of 19 hidden states extracted from the pre-trained models are concatenated to train the classifier, which consists of 3 3D convolutional layers. In particular, the concatenated hidden states are transformed from C ×T ×H ×W : 64× 19× 16× 16 to 174× 1. To evaluate the performance of different predictive units in modeling spatiotemporal representations for videos, we utilize various predictive units as the backbone of the early action recognition model. For fair comparison, the encoder, decoder and classifier are set with the same structure for all models. A total of 16 predictive units are stacked for all models. The experimental results are summarized in Table 7. On the one hand, the predictive model with MAU has achieved the best PSNR score of the predictions. On the other hand, based on the learned spatiotemporal representations from the pre-trained models, the proposed MAU can also obtain the highest Top1 and Top5 accuracies.

heading: 5 Conclusion

text: We proposed the Motion-aware Unit (MAU) for video prediction and beyond. The motion-aware unit can take advantage in the broadened temporal receptive field, where more temporal states can be simultaneously perceived. In particular, the proposed unit are constructed based on the attention mechanism, which consists of two modules, the attention module and the fusion module. In particular, the attention module can extract attention weights from multi-term spatial states for multi-term temporal states. And the augmented motion information (AMI) can be aggregated from the multi-term temporal states. Then the fusion module is utilized to further aggregate the AMI and the spatial information to predict the final video frame. Although more states have been aggregated, the computation load is still relatively low because of the efficient structure in MAU. Moreover, an information recalling scheme was employed to help the decoders recall more multi-level encoded information. The proposed model was evaluated on two tasks, the video prediction task and the video classification task. Experimental results showed the proposed MAU can outperform other state-of-the-art methods on both tasks.

heading: 6 Limitations and Future Work

text:
There are lots of issues that urgently need to be solved in the video prediction area and this work is also far from completely solving all the problems, such as high-resolution video prediction, low accuracy in action recognition, not practical enough to be applied into other downstream tasks and so on. All these problems need to be carefully taken into consideration in our future work. In addition, videos are still predicted in a deterministic way rather than a stochastic way, which may not practical enough for the complex real-world scenarios. Thus, in our future work, we will explore more to combine the spatiotemporal dynamics in videos into stochastic models, which are more similar to real-world scenarios.
Acknowledgments and Disclosure of Funding
This work was supported in part by the National Natural Science Foundation of China (62072008, 62025101), PKU-Baidu Fund (2019BD003) and High-performance Computing Platform of Peking University, which are gratefully acknowledged.

title: MAU: A Motion-Aware Unit for Video Prediction and Beyond


summaries: This paper studies sample efficient RL with two-layer neural network function approximation with a generative model. In particular, they prove that they can learn an optimal policy with poly samples with only realizability in deterministic MDP, and that the sample complexity for learning a near-optimal policy in stochastic MDPs is in an order of $\epsilon^{-2}$ in two cases: policy completeness assumption and Bellman completeness assumption. The algorithms they use are based on simple (non-optimistic) value regression.

summaries: This paper studies reinforcement learning with a 1-hidden layer neural network and low-rank polynomial function approximation schemes.   Under mostly standard assumptions about realizability, completness etc, they provide algorithms mainly focusing on sample complexity in cases when there is access to a perfect generative model of the transitions and in the fully online setting, where planning is not possible in episodic reinforcement learning.  They improve upon the sample complexity with respect to existing baselines for the respective function approximation schemes.

summaries: The paper considers RL with neural function approximation, extending significantly previous works that only focuses on linear feature approximation. In particular, the authors propose (1) an efficient algorithm using two-layer NNs in a generative model assuming completeness, and (2) an efficient algorithm with two-layer NNs but only assuming realizability.  The results significantly extends prior research on linear methods, or methods with bounded eluder dimension.

summaries: This paper focuses on analyzing sampling efficiency of nonlinear reinforcement learning with neural network approximations of the $Q$ function. It reduces the sampling complexity from $O(d^{\text{poly}(1/\epsilon)})$ to $O(\text{poly}(d) \exp(k))$ where $k$ is the width of the hidden layer of a two-layer fully connected neural network. The idea is described accurately and the paper is overall well written.

abstractText: Deep Reinforcement Learning (RL) powered by neural net approximation of the Q function has had enormous empirical success. While the theory of RL has traditionally focused on linear function approximation (or eluder dimension) approaches, little is known about nonlinear RL with neural net approximations of the Q functions. This is the focus of this work, where we study function approximation with two-layer neural networks (considering both ReLU and polynomial activation functions). Our first result is a computationally and statistically efficient algorithm in the generative model setting under completeness for two-layer neural networks. Our second result considers this setting but under only realizability of the neural net function class. Here, assuming deterministic dynamics, the sample complexity scales linearly in the algebraic dimension. In all cases, our results significantly improve upon what can be attained with linear (or eluder dimension) methods.

authors:
Yasin Abbasi-Yadkori
Dávid Pál
Csaba Szepesvári

title: Improved algorithms for linear stochastic bandits

authors:
Zeyuan Allen-Zhu
Yuanzhi Li

title: What can resnet learn efficiently, going beyond kernels

venue: arXiv preprint arXiv:1905.10337,

authors:
Zeyuan Allen-Zhu
Yuanzhi Li
Zhao Song

title: A convergence theory for deep learning via over-parameterization

venue: In International Conference on Machine Learning (ICML),

authors:
Mohammad Gheshlaghi Azar
Ian Osband
Rémi Munos

title: Minimax regret bounds for reinforcement learning

venue: In Proceedings of the 34th International Conference on Machine Learning,

authors:
Yu Bai
Jason D. Lee

title: Beyond linearization: On quadratic and higher-order approximation of wide neural networks

authors:
Christopher Berner
Greg Brockman
Brooke Chan
Vicki Cheung
Przemyslaw Debiak
Christy Dennison
David Farhi
Quirin Fischer
Shariq Hashme
Chris Hesse

title: Dota 2 with large scale deep reinforcement learning

authors:
Jacek Bochnak
Michel Coste
Marie-Françoise Roy

title: Real algebraic geometry, volume 36

venue: Springer Science & Business Media,

authors:
Minshuo Chen
Yu Bai
Jason D Lee
Tuo Zhao
Huan Wang
Caiming Xiong
Richard Socher

title: Towards understanding hierarchical learning: Benefits of neural representations

venue: Neural Information Processing Systems (NeurIPS),

authors:
Alex Damian
Tengyu Ma
Jason Lee

title: Label noise sgd provably prefers flat global minimizers

venue: arXiv preprint arXiv:2106.06530,

authors:
Christoph Dann
Nan Jiang
Akshay Krishnamurthy
Alekh Agarwal
John Langford
Robert E. Schapire

title: On oracle-efficient PAC-RL with rich observations

authors:
Kefan Dong
Jian Peng
Yining Wang
Yuan Zhou

title: n-regret for learning in Markov decision processes with function approximation and low Bellman rank

venue: In Conference on Learning Theory,

authors:
Kefan Dong
Jiaqi Yang
Tengyu Ma

title: Provable model-based nonlinear bandit and reinforcement learning: Shelve optimism, embrace virtual curvature

venue: arXiv preprint arXiv:2102.04168,

authors:
Simon Du
Jason Lee
Haochuan Li
Liwei Wang
Xiyu Zhai

title: Gradient descent finds global minima of deep neural networks

authors:
Simon S Du
Wei Hu
Sham M Kakade
Jason D Lee
Qi Lei

title: Few-shot learning via learning the representation, provably

venue: arXiv preprint arXiv:2002.09434,

authors:
Simon S. Du
Sham M. Kakade
Jason D. Lee
Shachar Lovett
Gaurav Mahajan
Wen Sun
Ruosong Wang

title: Bilinear classes: A structural framework for provable generalization in rl

venue: arXiv preprint arXiv:2103.10897,

authors:
Simon S Du
Sham M Kakade
Jason D Lee
Shachar Lovett
Gaurav Mahajan
Wen Sun
Ruosong Wang

title: Bilinear classes: A structural framework for provable generalization in RL

authors:
Simon S. Du
Sham M. Kakade
Ruosong Wang
Lin F. Yang

title: Is a good representation sufficient for sample efficient reinforcement learning

authors:
Simon S Du
Sham M Kakade
Ruosong Wang
Lin F Yang

authors:
Simon S Du
Akshay Krishnamurthy
Nan Jiang
Alekh Agarwal
Miroslav Dudik
John Langford

title: Provably efficient RL with rich observations via latent state decoding

authors:
Simon S Du
Jason D Lee
Gaurav Mahajan
Ruosong Wang

title: Agnostic Q-learning with function approximation in deterministic systems: Tight bounds on approximation error and sample complexity

authors:
Cong Fang
Jason D Lee
Pengkun Yang
Tong Zhang

title: Modeling from features: a mean-field framework for over-parameterized deep neural networks

venue: arXiv preprint arXiv:2007.01452,

authors:
Massimo Fornasier
Timo Klock
Michael Rauchensteiner

title: Robust and resource efficient identification of two hidden layer neural networks

authors:
Massimo Fornasier
Jan Vybíral
Ingrid Daubechies

title: Robust and resource efficient identification of shallow neural networks by fewest samples

venue: arXiv preprint arXiv:1804.01592,

authors:
Dylan J. Foster
Alekh Agarwal
Miroslav Dudík
Haipeng Luo
Robert E. Schapire

title: Practical contextual bandits with regression oracles

venue: Proceedings of the 35th International Conference on Machine Learning,

authors:
Ruiqi Gao
Tianle Cai
Haochuan Li
Liwei Wang
Cho-Jui Hsieh
Jason D Lee

title: Convergence of adversarial training in overparametrized networks

authors:
Rong Ge
Jason D. Lee
Tengyu Ma

title: Learning one-hidden-layer neural networks with landscape design

venue: arXiv preprint arXiv:1711.00501,

venue: In International Conference on Learning Representations (ICLR),

authors:
Rong Ge
Jason D Lee
Tengyu Ma

venue: International Conference on Learning Representations (ICLR),

authors:
Behrooz Ghorbani
Song Mei
Theodor Misiakiewicz
Andrea Montanari

title: Linearized two-layers neural networks in high dimension

venue: arXiv preprint arXiv:1904.12191,

venue: The Annals of Statistics,

title: Active learning for cost-sensitive classification

venue: Foundations and Trends in Machine Learning,

authors:
Jeff Z. HaoChen
Colin Wei
Jason D. Lee
Tengyu Ma

title: Shape matters: Understanding the implicit bias of the noise covariance

venue: arXiv preprint arXiv:2006.08680,

authors:
Peter Henderson
Riashat Islam
Philip Bachman
Joelle Pineau
Doina Precup
David Meger

title: Deep reinforcement learning that matters

venue: In Proceedings of the AAAI Conference on Artificial Intelligence,

authors:
Baihe Huang
Kaixuan Huang
Sham M Kakade
Jason D Lee
Qi Lei
Runzhe Wang
Jiaqi Yang

title: Optimal gradient-based algorithms for non-concave bandit optimization

venue: arXiv preprint arXiv:2107.04518,

authors:
Arthur Jacot
Franck Gabriel
Clément Hongler

title: Neural tangent kernel: Convergence and generalization in neural networks. In Advances in neural information processing systems (NeurIPS)

authors:
Thomas Jaksch
Ronald Ortner
Peter Auer

title: Near-optimal regret bounds for reinforcement learning

venue: Journal of Machine Learning Research,

authors:
Majid Janzamin
Hanie Sedghi
Anankumar Anima

title: Beating the perils of nonconvexity: Guaranteed training of neural networks using tensor methods

venue: arXiv preprint arXiv:1506.08473,

authors:
Nan Jiang
Akshay Krishnamurthy
Alekh Agarwal
John Langford
Robert E Schapire

title: Contextual decision processes with low Bellman rank are PAC-learnable

authors:
Chi Jin
Zeyuan Allen-Zhu
Sebastien Bubeck
Michael I Jordan

title: Is Q-learning provably efficient

authors:
Chi Jin
Qinghua Liu
Sobhan

title: Miryoosefi. Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms

venue: arXiv preprint arXiv:2102.00875,

authors:
Chi Jin
Zhuoran Yang
Zhaoran Wang
Michael I Jordan

title: Provably efficient reinforcement learning with linear function approximation

title: On the sample complexity of reinforcement learning

venue: PhD thesis, University of College London,

authors:
Akshay Krishnamurthy
Alekh Agarwal
Tzu-Kuo Huang
Hal Daume III
John Langford

venue: Proceedings of the 34th International Conference on Machine Learning,

authors:
Volodymyr Kuleshov
Arun Chaganty
Percy Liang

title: Tensor factorization via matrix factorization

venue: In Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics (AISTATS),

authors:
Gene Li
Pritish Kamath
Dylan J. Foster
Nathan Srebro

title: Eluder dimension and generalized rank

venue: arXiv preprint arXiv:2104.06970,

authors:
Timothy P Lillicrap
Jonathan J Hunt
Alexander Pritzel
Nicolas Heess
Tom Erez
Yuval Tassa
David Silver
Daan Wierstra

title: Continuous control with deep reinforcement learning

venue: arXiv preprint arXiv:1509.02971,

authors:
Boyi Liu
Qi Cai
Zhuoran Yang
Zhaoran Wang

title: Neural proximal/trust region policy optimization attains globally optimal policy

authors:
Dhruv Malik
Aldo Pacchiano
Vishwak Srinivasan
Yuanzhi Li

title: Sample efficient reinforcement learning in continuous state spaces: A perspective beyond linearity

venue: arXiv preprint arXiv:2106.07814,

title: Algebraic geometry (v6.02), 2017

venue: Available at www.jmilne.org/math/

authors:
Volodymyr Mnih
Koray Kavukcuoglu
David Silver
Alex Graves
Ioannis Antonoglou
Daan- Wierstra
Martin Riedmiller

title: Playing atari with deep reinforcement learningep reinforcement learning

venue: arXiv preprint arXiv:1312.5602,

authors:
Volodymyr Mnih
Koray Kavukcuoglu
David Silver
Alex Graves
Ioannis Antonoglou
Daan Wierstra
Martin Riedmiller

title: Playing Atari with deep reinforcement learning

authors:
Matej Moravčík
Martin Schmid
Neil Burch
Viliam Lisỳ
Dustin Morrill
Nolan Bard
Trevor Davis
Kevin Waugh
Michael Johanson
Michael Bowling

title: Deepstack: Expert-level artificial intelligence in heads-up no-limit

venue: poker. Science,

authors:
Edward Moroshko
Suriya Gunasekar
Blake Woodworth
Jason D Lee
Nathan Srebro
Daniel Soudry

title: Implicit bias in deep linear classification: Initialization scale vs training accuracy

authors:
Mor Shpigel Nacson
Suriya Gunasekar
Jason Lee
Nathan Srebro
Daniel Soudry

title: Lexicographic and depth-sensitive margins in homogeneous and non-homogeneous deep models

authors:
Ian Osband
Daniel Russo
Benjamin Van Roy

title: more) efficient reinforcement learning via posterior sampling

authors:
Alexander Rakhlin
Karthik Sridharan
Ambuj Tewari

title: Online learning via sequential complexities

title: Sequential complexities and uniform martingale laws of large numbers

venue: Probability Theory and Related Fields,

authors:
Dan Russo
Benjamin Van Roy

title: Eluder dimension and the sample complexity of optimistic exploration

title: Worst-case regret bounds for exploration via randomized value functions

authors:
Daniel Russo
Benjamin Van Roy

title: Shafarevich. Basic Algebraic Geometry 1: Varieties in Projective Space

authors:
Shai Shalev-Shwartz
Shaked Shammah
Amnon Shashua

title: Safe, multi-agent, reinforcement learning for autonomous driving

venue: arXiv preprint arXiv:1610.03295,

authors:
Aaron Sidford
Mengdi Wang
Xian Wu
Lin F Yang
Yinyu Ye

title: Near-optimal time and sample complexities for solving discounted markov decision process with a generative model

venue: arXiv preprint arXiv:1806.01492,

authors:
David Silver
Aja Huang
Chris J. Maddison
Arthur Guez
Laurent Sifre
George Van Den Driessche
Julian Schrittwieser
Ioannis Antonoglou
Veda Panneershelvam
Marc Lanctot

title: Mastering the game of Go with deep neural networks and tree

venue: search. Nature,

authors:
Alexander L Strehl
Lihong Li
Eric Wiewiora
John Langford
Michael L Littman

title: PAC model-free reinforcement learning

venue: In Proceedings of the 23rd international conference on Machine learning,

authors:
Wen Sun
Nan Jiang
Akshay Krishnamurthy
Alekh Agarwal
John Langford

title: Modelbased RL in contextual decision processes: PAC bounds and exponential improvements over model-free approaches

authors:
Richard S Sutton
Andrew G. Barto

title: Reinforcement learning: An introduction

venue: MIT press,

authors:
Lingxiao Wang
Qi Cai
Zhuoran Yang
Zhaoran Wang

title: Neural policy gradient methods: Global optimality and rates of convergence

venue: arXiv preprint arXiv:1909.01150,

authors:
Ruosong Wang
Ruslan Salakhutdinov
Lin F Yang

title: Provably efficient reinforcement learning with general value function approximation

venue: arXiv preprint arXiv:2005.10804,

authors:
Xiang Wang
Chenwei Wu
Jason D Lee
Tengyu Ma
Rong Ge

title: Beyond lazy training for over-parameterized tensor decomposition

authors:
Yang Wang
Zhiqiang Xu

title: Generalized phase retrieval: measurement number, matrix recovery and beyond

venue: Applied and Computational Harmonic Analysis,

authors:
Yining Wang
Ruosong Wang
Simon S. Du
Akshay Krishnamurthy

title: Optimism in reinforcement learning with generalized linear function approximation

authors:
Yuanhao Wang
Ruosong Wang
Sham M. Kakade

title: An exponential lower bound for linearly-realizable mdps with constant suboptimality gap

venue: arXiv preprint arXiv:2103.12690,

authors:
Colin Wei
Jason D Lee
Qiang Liu
Tengyu Ma

title: Regularization matters: Generalization and optimization of neural nets vs their induced kernel

authors:
Gellert Weisz
Philip Amortila
Csaba Szepesvári

title: Exponential lower bounds for planning in mdps with linearly-realizable optimal action-value functions

venue: arXiv preprint arXiv:2010.01374,

authors:
Zheng Wen
Benjamin Van Roy

title: Efficient exploration and value function generalization in deterministic systems

title: Efficient reinforcement learning in deterministic systems with value function generalization

venue: Math. Oper. Res.,

authors:
Blake Woodworth
Suriya Genesekar
Jason Lee
Daniel Soudry
Nathan Srebro

title: Kernel and deep regimes in overparametrized models

venue: In Conference on Learning Theory (COLT),

authors:
Jiaqi Yang
Wei Hu
Jason D Lee
Simon S Du

title: Provable benefits of representation learning in linear bandits

venue: arXiv preprint arXiv:2010.06531,

authors:
Lin F Yang
Mengdi Wang

title: Reinforcement leaning in feature space: Matrix bandit, kernels, and regret bound

venue: International Conference on Machine Learning,

authors:
Zhuoran Yang
Chi Jin
Zhaoran Wang
Mengdi Wang
Michael Jordan

title: Provably efficient reinforcement learning with kernel and neural function approximations

authors:
Gilad Yehudai
Ohad Shamir

title: On the power and limitations of random features for understanding neural networks

venue: arXiv preprint arXiv:1904.00687,

authors:
Andrea Zanette
Emma Brunskill

title: Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds

authors:
Andrea Zanette
Alessandro Lazaric
Mykel Kochenderfer
Emma Brunskill

title: Learning near optimal policies with low inherent Bellman error

authors:
Kai Zhong
Zhao Song
Prateek Jain
Peter L. Bartlett
Inderjit S. Dhillon

title: Recovery guarantees for one-hidden-layer neural networks

venue: Proceedings of the Thirty-fourth International Conference on Machine Learning (ICML),

authors:
Dongruo Zhou
Lihong Li
Quanquan Gu

title: Neural contextual bandits with ucb-based exploration

venue: Proceedings of the 37th International Conference on Machine Learning,

heading: 1 Introduction

text:
In reinforcement learning (RL), an agent aims to learn the optimal decision-making rule by interacting with an unknown environment [71]. Deep Reinforcement Learning, empowered by deep neural networks [48, 32], has achieved tremendous success in various real-world applications, such as Go [68], Atari [54], Dota2 [7], Texas Holdém poker [56], and autonomous driving [66]. Those modern RL applications are characterized by large state-action spaces, and the empirical success of deep RL corroborates the observation that deep neural networks can extrapolate well across state-action spaces [35, 55, 50].
Although in practice non-linear function approximation scheme is prevalent, theoretical understandings of the sample complexity of RL mainly focus on tabular or linear function approximation settings [69, 38, 5, 41, 63, 88, 1, 43, 44, 77]. These results rely on finite state space or exact linear approximations. Recently, sample efficient algorithms under non-linear function approximation settings are proposed [82, 11, 20, 12, 51, 72, 13, 91, 86]. Those algorithms are based on Bellman rank [40], eluder dimension [64], neural tangent kernel [37, 4, 14, 92], or sequential Rademacher complexity [60, 61]. Yet, the understanding of how deep RL learns and generalizes in large state spaces is far from complete. While the aforementioned works study function approximation structures that possess the nice properties of linear models, such as low information gain and low eluder dimensions, the highly non-linear nature of neural networks renders challenges on their applicability to deep RL. For one thing, recent wisdoms in deep learning theory cast doubt on the ability of neural tangent kernel and random features to model the actual neural networks. Indeed, the neural tangent kernel
∗Alphabetical order. Correspondence to: Baihe Huang, baihehuang@pku.edu.cn, Jason D. Lee, Jasondl@ princeton.edu.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
approximately reduces neural networks to linear models, but the RKHS norm of neural networks is exponential [87]. Moreover, it remains unclear what neural networks models have low eluder dimensions. For example, recent work [13] shows that two layer neural networks have exponential eluder dimension in the dimension of features. Thus, the mismatch between the empirical success of deep RL and its theoretical understanding remains significant, which yields the following important question:
What are the structural properties that allow sample-efficient algorithms for RL with neural network function approximation?
Recent work in RL suggests that learning RL with neural networks function approximation is exponentially hard [13, 49, 52]. In this paper, however, we advance the understanding of the above question by displaying several structural properties that allow efficient RL algorithms with neural function approximations. We consider several value function approximation models that possess high information gain and high eluder dimension. Specifically, we study two structures, namely twolayer neural networks and structured polynomials (i.e. two-layer neural networks with polynomial activation functions), under two RL settings, namely RL with simulator model and online RL. In the simulator (generative model) setting [45, 67], the agent can simulate the MDP at any state-action pair. In online RL, the agent can only start at an initial state and interact with the MDP step by step. The goal in both settings is to find a near-optimal policy while minimizing the number of samples used.
We obtain the following results. For the simulator setting, we propose sample-efficient algorithms for RL with two-layer neural network function approximation. Under either policy completeness, Bellman completeness, or gap conditions, our method provably learns near-optimal policy with polynomial sample complexities. For online RL, we provide sample-efficient algorithms for RL with structured polynomial function approximation. When the transition is deterministic, we also present sample-efficient algorithms under only the realizability assumption [18, 78]. Our main techniques are based on neural network recovery [90, 39, 28], and algebraic geometry [53, 65, 8, 76].

heading: 1.1 Summary of our results

text:
Our main results in different settings are summarized in Table 1. We consider two-layer neural networks f(x) = ⟨v, σ(Wx)⟩ (where σ is ReLU activation) and rank k polynomials (see Example 4.3).
We make the following elaborations on Table 1.
• For simplicity, we display only the dependence on the feature dimension d, network width or polynomial rank k, precision ϵ, and degree p (of polynomials).
• In the table Sim. denotes simulator model, Onl. denotes online RL, Det. denotes deterministic transitions, Stoch. denotes stochastic transitions, Gap. denotes gap condition, (R) denotes realizability assumption only, and (C) denotes completeness assumption (either policy complete or Bellman complete) together with realizability assumption.
• We apply [21] for the deterministic transition baseline, and apply [19] for the stochastic transition baseline. We are unaware of any methods that can directly learn MDP with neural network value function approximation2.
• In polynomial case, the baseline first vectorizes the tensor ( 1 x )⊗p into a vector in R(d+1)p
and then performs on this vector. In the neural network case, the baseline uses a polynomial of degree 1/ϵ to approximate the neural network with precision ϵ and then vectorizes the polynomial into a vector in Rdpoly(1/ϵ) . The baseline method for realizable model (denoted
by (*)) needs a further gap assumption of gap ≥ dpoly(1/ϵ)ϵ to avoid the approximation error from escalating [21]; note for small ϵ this condition never holds but we include it in the table for the sake of comparison.
• In rank k polynomial case, our result O(dk) in simulator model can be found in Theorem 4.7 and our result O(dk) in online RL model can be found in Theorem 4.8. These results only require a realizability assumption. Efficient explorations are guaranteed by algebraic-geometric arguments. In neural network model, our result Õ(poly(d) · exp(k)) in simulator model can be found in Theorem 3.4. This result also only relies on the realizability assumption. For stochastic transitions, our result Õ(poly(d, k)/ϵ2) works for either policy complete or Bellman complete settings, as in Theorem 3.5 and Theorem 3.6 respectively. The Õ(poly(d, k)) result for gap condition can be found in Theorem 3.8.

heading: 1.2 Related Work

text:
Linear Function Approximation. RL with linear function approximation has been widely studied under various settings, including linear MDP and linear mixture MDP [44, 89, 85]. While these papers have proved efficient regret and sample complexity bounds, their analyses relied heavily on two techniques: they used the confidence ellipsoid to quantify the uncertainty, and they used the elliptical potential lemma to bound the total uncertainty [2]. These two techniques were integral to their analyses but are so restrictive that they generally do not extend to nonlinear cases.
Eluder Dimension. [62, 59] proposed eluder dimension, a complexity measure of the function space, and proved regret and sample complexity bounds that scaled with the eluder dimension, for bandits and reinforcement learning [73, 42]. They also showed that the eluder dimension is small in several settings, including generalized linear models and LQR. However, as shown in [13], the eluder dimension could be exponentially large even with a single ReLU neuron, which suggested the eluder dimension would face difficulty in dealing with neural network cases. The eluder dimension is only known to give non-trivial bounds for linear function classes and monotone functions of linear function classes. For structured polynomial classes, the eluder dimension simply embeds into an ambient linear space of dimension dp, where d is the dimension, and p is the degree. This parallels the lower bounds in linearization / neural tangent kernel (NTK) works [79, 30, 3], which show that linearization also incurs a similarly large penalty of dp sample complexity, and more advanced algorithm design is need to circumvent linearization[6, 9, 22, 83, 26, 58, 29, 57, 34, 75, 10].
Bellman Rank and Completeness. [40, 70] studied RL with general function approximation. They used Bellman rank to measure the error of the function class under the Bellman operator and gave proved bounds in the term of it. Recently, [16] propose bilinear rank and encompass more function approximation models. However, it is hard to bound either the Bellman rank or the bilinear rank for neural nets. Therefore, their results are not known to include the neural network approximation setting. Another line of work shows that exponential sample complexity is unavoidable even with good representations [19, 80, 78], which implies the realizability assumption alone might be insufficient for function approximations.

heading: 2 Preliminaries

text:
An episodic Markov Decision Process (MDP) is defined by the tupleM = (S,A, H,P, r) where S is the state space, A is the action set, H is the number of time steps in each episode, P is the transition kernel and r is the reward function. In each episode the agent starts at a fixed initial state s1 and at each time step h ∈ [H] it takes action ah, receives reward rh(sh, ah) and transits to sh+1 ∼ P(·|sh, ah). A deterministic policy π is a length-H sequence of functions π = {πh : S 7→ A}Hh=1. Given a policy π, we define the value function V πh (s) as the expected sum of reward under policy π starting from
2Prior work on neural function approximation has focused on neural tangent kernels, which would require dpoly(1/ϵ) to approximate a two-layer network [31].
sh = s:
V πh (s) := E [ H∑ t=h rt(st, at)|sh = s ] and we define the Q function Qπh(s, a) as the the expected sum of reward taking action a in state sh = s and then following π:
Qπh(s, a) := E [ H∑ t=h rt(st, at)|sh = s, ah = a ] .
The Bellman operator Th applied to Q-function Qh+1 is defined as follow Th(Qh+1)(s, a) := rh(s, a) + Es′∼P(·|s,a)[max
a′ Qh+1(s
′, a′)].
There exists an optimal policy π∗ that gives the optimal value function for all states, i.e. V π ∗
h (s) =
supπ V π h (s) for all h ∈ [H] and s ∈ S. For notational simplicity we abbreviate V π
∗ as V ∗ and
correspondingly Qπ ∗ as Q∗. Therefore Q∗ satisfies the following Bellman optimality equations for all s ∈ S, a ∈ A and h ∈ [H]:
Q∗h(s, a) = Th(Q∗h+1)(s, a).
The goal is to find a policy π that is ϵ-optimal in the sense that V ∗1 (s1)− V π1 (s1) ≤ ϵ, within a small number of samples. We consider two query models of interacting with MDP:
• In the simulator model ([45], [67]), the agent interacts with a black-box that simulates the MDP. At each time step h ∈ [H], the agent can start at a state-action pair (s, a) and interact with the black box by executing some policy π chosen by the agent.
• In online RL, the agent can only start at the initial state and interact with the MDP by using a policy and observing the rewards and the next states. In each episode k, the agent proposes a policy πk based on all history up to episode k − 1 and executes πk to generate a single trajectory {skh, akh}Hh=1 with akh = πkh(skh) and skh+1 ∼ P(·|skh, akh).

heading: 2.1 Function approximation

text:
In reinforcement learning with value function approximation, the learner is given a function class F = F1×· · ·×FH , whereFh ⊂ {f : S×A 7→ [0, 1]} is a set of candidate functions to approximate Q∗. The following assumption is commonly adopted in the literature [43, 74, 42, 17]. Assumption 2.1 (Realizability). Q∗h ∈ Fh for all h ∈ [H].
The function approximation is equipped with feature mapping ϕ : S ×A 7→ {u ∈ Rd : ∥u∥2 ≤ Bϕ} that is known to the agent. We focus the continuous action setting (e.g. in control and robotics problems) and make the following regularity assumption on the feature function ϕ. Assumption 2.2 (Bounded features). Assume ϕ(s, a) ≤ Bϕ,∀(s, a) ∈ S ×A.
Notation For any vector x ∈ Rd, let xmax := maxi∈[d] xi and xmin := mini∈[d] xi. Let si(·) denote the i-th singular value, smin(·) denotes the minimum eigenvalue and smax(·) denotes the maximum eigenvalue. The conditional number is defined by κ(·) := smax(·)/smin(·). We use ⊗ to denote Kronecker product and ◦ to denote Hadamard product. For a given integer H , we use [H] to denote the set {1, 2, . . . ,H}. For a function f : X 7→ Y, we use f−1(y) := {x ∈ X : f(x) = y} to denote the preimage of y ∈ Y. We use the shorthand x ≲ y (x ≳ y) to indicate x ≤ O(y) (x ≥ Ω(y)).

heading: 3 Neural Network Function Approximation

text:
In this section we show sample-efficient algorithms with neural network function approximations. The function class of interest is given in the following definition. More general neural network class is discussed in Appendix B.5.
Definition 3.1 (Neural Network Function Class). We use FNN to denote the function class of f(ϕ(s, a)) : S ×A 7→ R where f(x) = ⟨v, σ(Wx)⟩ : Rd 7→ R is a two-layer neural network where σ is ReLU, ∥W∥F ≤ BW , v ∈ {±1}k, ∏k i=1 si(W )/smin(W ) ≤ λ, smax(W )/smin(W ) ≤ κ and k ≤ d. Here ϕ : A × S 7→ Rd is a known feature map whose image contains a ball {u ∈ Rd : ∥u∥2 ≤ δϕ} with δϕ ≥ d · polylog(d).3
We introduce the following completeness properties in the setting of value function approximations. Along with Assumption 2.1, they are commonly adopted in the literature . Definition 3.2 (Policy complete). Given MDPM = (S,A,P, r,H), function class Fh : S ×A 7→ R, h ∈ [H] is called policy complete if for all π and h ∈ [H], Qπh ∈ Fh. Definition 3.3 (Bellman complete). Given MDPM = (S,A,P, r,H), function class Fh : S ×A 7→ R, h ∈ [H] is called Bellman complete if for all h ∈ [H] and Qh+1 ∈ Fh+1, Th(Qh+1) ∈ Fh.

heading: 3.1 Warmup: Realizable Q∗ with deterministic transition

text:
We start by considering the case when the transition kernel is deterministic. In this case only Assumption 2.1 is required for the expressiveness of neural network function approximations. Algorithm 1 learns optimal policy from time step H to 1. Suppose we have learned policies πh+1, . . . , πH at level h and they are exactly the optimal policies. We first explore features ϕ(sih, a i h) over a standard Gaussian distribution, and if ∥ϕ(sih, aih)∥2 ≥ δϕ then we simply skip this trial. Recall that δϕ ≥ d ·poly log(d), so with high probability (w.r.t d) almost all feature samples will be explored. We next construct an estimate Q̂ih of Q ∗(sih, a i h) by collecting cumulative rewards using πh+1, . . . , πH as the roll-out. Since the transition is deterministic, Q̂ih = Q ∗(sih, a i h) for all explored samples (s i h, a i h). Recall that Q∗h is a two-layer neural network, we can now recover its parameters in Line 12 exactly by invoking techniques in neural network optimization (see, e.g. [39, 27, 90]). Details of this step can be found in Appendix B.5, where the method is mainly based on [90]. This means the reconstructed Q̂h in Line 13 is precisely Q∗, and the algorithm can thus find optimal policy π∗h in the h-th level.
Algorithm 1 Learning realizable Q∗ with deterministic transition 1: for h = H, . . . 1 do 2: Sample xih, i ∈ [n] from standard Gaussian N (0, Id) 3: for i ∈ [n] do 4: if ∥xih∥ ≤ δϕ then 5: Find (sih, a i h) ∈ ϕ−1(xih) and locate the state sih in the generative model
6: Pull action aih and use πh+1, . . . , πH as the roll-out to collect rewards r (i) h , . . . , r (i) H 7: Construct estimation
Q̂ih ← r (i) h + · · ·+ r (i) H
8: else 9: Let Q̂ih ← 0.
10: end if 11: end for 12: Compute (vh,Wh)← NEURALNETRECOVERY({(xih, Q̂ih) : i ∈ [n]}) 13: Set Q̂h(s, a)← v⊤h σ(Whϕ(s, a)) 14: Let πh(s)← argmaxa∈S Q̂h(s, a) 15: end for 16: Return π1, . . . , πH
Theorem 3.4. (Informal) If n ≥ d · poly(κ, k, λ, log d,BW , Bϕ, H), then with high probability Algorithm 1 learns the optimal policy.
The formal statement and complete proof are deferred to the Appendix B.1. The main idea of exact neural network recovery can be summarized in the following. We first use method of moments to
3Here the δϕ is chosen only for simplicity. In general this assumption can be relaxed to that the image of ϕ contains an arbitrary dense ball near the origin, since one can always rescale the feature mapping in the neural function approximation.
find a ‘rough’ parameter recovery. If this ‘rough’ recovery is sufficiently close to the true parameter, the empirical ℓ2 loss function is locally strongly convex and there is unique global minimum. Then we can apply gradient descent to find this global minimum which is exactly the true parameter.

heading: 3.2 Policy complete neural function approximation

text:
Now we consider general stochastic transitions. Difficulties arise in this scenario due to noises in the estimation of Q-functions. In the presence of model misspecification, these noises cause estimation errors to amplify through levels and require samples to be exponential in H . In this section, we show that neural network function approximation is still learnable, assuming the function class FNN is policy complete with regard to MDP M. Thus for all π ∈ Π, we can denote Qπh(s, a) = ⟨vπ, σ(Wπϕ(s, a))⟩.
Algorithm 2 Learn policy complete NN with simulator. 1: for h = H, . . . 1 do 2: Sample xih, i ∈ [n] from standard Gaussian N (0, Id) 3: for i ∈ [n] do 4: if ∥xih∥ ≤ δϕ then 5: Find (sih, a i h) ∈ ϕ−1(xih) and locate the state sih in the generative model
6: Pull action aih and use πh+1, . . . , πH as the roll-out to collect rewards r (i) h , . . . , r (i) H 7: Construct unbiased estimation of Qπh+1,...,πHh (s i h, a i h)
Q̂ih ← r (i) h + · · ·+ r (i) H
8: else 9: Let Q̂ih ← 0.
10: end if 11: end for 12: Compute (vh,Wh)← NEURALNETNOISYRECOVERY({(xih, Q̂ih) : i ∈ [n]}) 13: Set Q̂h(s, a)← v⊤h σ(Whϕ(s, a)) 14: Let πh(s)← argmaxa∈S Q̂h(s, a) 15: end for 16: Return π1, . . . , πH
Algorithm 2 learns policy from level H,H − 1, . . . , 1. In level h, the algorithm has learned policy πh+1, . . . , πH that is only sub-optimal by (H − h)ϵ/H . Then it explores features ϕ(s, a) from N (0, Id). The algorithm then queries (s, a) and uses learned policy πh+1, . . . , πH as roll out to collect an unbiased estimate of the Q-function Qπh+1,...,πHh (s, a). Since Q πh+1,...,πH h (s, a) ∈ FNN is a two-layer neural network, it can then be recovered from samples. Details of this step can be found in Appendix B.5, where the methods are mainly based on [90]. The algorithm then reconstructs this Q-function and finds its optimal policy πh.
Theorem 3.5. (Informal) Fix ϵ, t, if n ≥ ϵ−2 · d · poly(κ, k,BW , Bϕ, H, log(d/t)), then with probability at least 1− t Algorithm 2 returns an ϵ-optimal policy π.
The formal statement and complete proof are deferred to Appendix B.2. Notice that unlike the case of Theorem 3.4, the sample complexity does not depend on λ, thus avoiding the potential exponential dependence in k.
The main idea of the proof is that at each time step a neural network surrogate of Q∗ can be constructed by the policy already learned. Suppose we have learned πh+1, . . . , πH in level h, then from policy completeness Qπh+1,...,πHh belongs to FNN and we can interact with the simulator to obtain its estimate Q̂h. If ∥Q̂h −Q πh+1,...,πH h ∥∞ is small, the optimistic planning based on Q̂h is not far from the optimal policy of Qπh+1,...,πHh . Therefore the errors can be decoupled into the errors in recovering Q
πh+1,...,πH h and the suboptimality of Q πh+1,...,πH h , which depends on level h + 1. This reasoning
can then be recursively performed to level H , and thus we can bound the suboptimality of πh.

heading: 3.3 Bellman complete neural function approximation

text:
In addition to policy completeness, we show that neural network function approximation can also learn efficiently under the setting where the function class FNN is Bellman complete with regard to MDPM. Specifically, for Qh+1 ∈ Fh+1, there are vQh+1 and WQh+1 such that Th(Qh+1)(s, a) = ⟨vQh+1 , σ(WQh+1ϕ(s, a))⟩. Algorithm 3 is similar to the algorithm in previous section. Suppose in level h, the algorithm has constructed the Q-function Q̂h+1(s, a) = v⊤h+1σ(Wh+1ϕ(s, a)) that is (H − h)ϵ/H-close to the optimal Q∗h+1. It then recovers weights vh,Wh from Th(Q̂h+1)(s, a) = ⟨vQ̂h+1 , σ(W Q̂h+1ϕ(s, a))⟩, using unbiased estimates rh(sih, a i h) + V̂h+1(s i h+1). The Q-function Q̂h(s, a) = v ⊤ h σ(Whϕ(s, a)) reconstructed from weights vh,Wh is thus (H − h+ 1)ϵ/H-close to the Q∗h.
Algorithm 3 Learn Bellman complete NN with simulator. 1: for h = H, . . . 1 do 2: Sample xih, i ∈ [n] from standard Gaussian N (0, Id) 3: for i ∈ [n] do 4: if ∥xih∥ ≤ δϕ then 5: Find (sih, a i h) ∈ ϕ−1(xih) and locate the state sih in the generative model
6: Pull action aih and and observe rh(s i h, a i h), s i h+1 7: Construct unbiased estimation of Th(Q̂h+1)(sih, aih)
Q̂ih ← rh(sih, aih) + V̂h+1(sih+1)
8: else 9: Let Q̂ih ← 0.
10: end if 11: end for 12: Compute (vh,Wh)← NEURALNETNOISYRECOVERY({(xih, Q̂ih) : i ∈ [n]}) 13: Set Q̂h(s, a)← v⊤h σ(Whϕ(s, a)) and V̂h ← maxa∈A Q̂h(s, a) 14: Let πh(s)← argmaxa∈A Q̂h(s, a) 15: end for 16: Return π1, . . . , πH
Theorem 3.6. (Informal) Fix ϵ, t, if n ≥ ϵ−2 · d · poly(κ, k,BW , Bϕ, H, log(d/t)), then with probability at least 1− t Algorithm 3 returns an ϵ-optimal policy π.
Due to Bellman completeness, the error of estimation Q̂h can be controlled recursively. In fact, we can show ∥Q̂h − Q∗(s, a)∥∞ is small by induction. The formal statement and detailed proof are deferred to Appendix B.3. Similar to Theorem 3.5, the sample complexity does not explicitly depend on λ, thus avoiding potentially exponential dependence in k.

heading: 3.4 Realizable Q∗ with optimality gap

text:
In this section we consider MDPs where there is a non-zero gap between the optimal policy and any other ones. This concept, known as optimality gap, is widely used in reinforcement learning and bandit literature [20, 19, 21].
Definition 3.7. The optimality gap is defined as
ρ = inf a:Q∗(s,a) ̸=V ∗(s)
V ∗(s)−Q∗(s, a).
We show that in the presence positive optimality gap, there exists an algorithm that can learn the optimal policy with polynomial samples even without the completeness assumptions. Intuitively, this is because one only needs to recover the neural network up to precision ρ/4 in order to make sure the greedy policy is identical to the optimal one. The formal statement and proof are deferred to Appendix B.4.
Theorem 3.8. (Informal) Fix t ∈ (0, 1), if n = dρ2 · poly(κ, k,BW , Bϕ, H, log(d/t)), then with probability at least 1− t there exists an algorithm that returns the optimal policy π∗. Remark 3.9. In all aforementioned methods, there are two key components that allow efficient learning. First, the exploration is conducted in a way that guarantees an ℓ∞ recovery of candidate functions. By ℓ∞ recovery we mean the algorithm recovers a candidate Q-function in this class deviating from the target function Q∗ by at most ϵ uniformly for all state-action pairs in the domain of interest. This notion of learning guarantee has received study in active learning [33, 46] and recently gain interest in contextual bandits [25]. Second, the agent constructs unbiased estimators of certain approximations to Q∗ that lie in the neural function approximation class. This allows the recovery error to decouple linearly across time steps, which is made possible in several well-posed MDP instances, such as deterministic MDPs, MDPs with completeness assumptions, and MDPs with gap conditions. In principle, we note that provably efficient RL algorithms with general function approximation is possible as long as the above two components are present. We will see in the next section another example of learning RL with highly non-convex function approximations, where the function class of interest, admissible polynomial families, also allows for exploration schemes to achieve ℓ∞ recovery.

heading: 4 Polynomial Realizability

text:
In this section, we study the sample complexity to learn deterministic MDPs under polynomial realizability. We identify sufficient and necessary conditions for efficiently learning the MDPs for two different settings — the generative model setting and the online RL setting. Specifically, we show that if the image of the feature map ϕh(sh, ah) satisfies some positive measure conditions, then by random exploring, we can identify the optimal policy with samples linear in the algebraic dimension of the underlying polynomial class. We also provide a lower bound example showing the separation between the two settings.
Next, we introduce the notion of Admissible Polynomial Families, which are the families of structured polynomials that enable efficient learning. Definition 4.1 (Admissible Polynomial Families). For x ∈ Rd, denote x̃ = [1, x⊤]⊤. Let X :={ x̃⊗p : x ∈ Rd } . For any algebraic variety V , we define FV := {fΘ(x) = ⟨Θ, x̃⊗p⟩ : Θ ∈ V} as the polynomial family parameterized by Θ ∈ V . We say FV is admissible4 w.r.t. X , if for any Θ ∈ V , dim(X ∩ {X ∈ X : ⟨X,Θ⟩ = 0⟩}) < dim(X ) = d. We define the dimension D of the family to be the dimension of V .
The following theorem shows that to learn an admissible polynomial family, the sample complexity only scales with the algebraic dimension of the polynomial family.
Theorem 4.2 ([36]). Consider the polynomial family FV of dimension D. For n ≥ 2D, there exists a Lebesgue-measure zero set N ∈ Rd × . . .Rd, such that if (x1, · · · , xn) /∈ N , for any yi, there is a unique f (or no such f ) to the system of equations yi = f(xi) for f ∈ FV .
We give two important examples of admissible polynomial families with low dimension.
Example 4.3. (Low-rank Polynomial of rank k) The function f ∈ FV is a polynomial with k terms, that is
F (x) = k∑ i=1 λi⟨vi, x⟩pi ,
where p = max{pi}. The dimension of this family is upper bounded by D ≤ dk. Neural network with monomial/polynomial activation functions are low-rank polynomials.
Example 4.4. The function f ∈ FV is of the form f(x) = q(Ux), where U ∈ Rk×d and q is a degree p polynomial. The polynomial q and matrix U are unknown. The dimension of this family is upper bounded by D ≤ d(k + 1)p.
Next, we introduce the notion of positive measure.
4Admissible means the dimension of X decreases by one when there is an additional linear constraint ⟨Θ, X⟩ = 0
Definition 4.5. We say a measurable set E ∈ Rd is of positive measure if µ(E) > 0, where µ is the standard Lebesgue measure on Rd.
If a measurable set E satisfies µ(E) > 0, then there exists a procedure to draw samples from E, such that for any N ⊂ Rd of Lebesgue-measure zero, the probability that the sample falls in N is zero. In fact, the sampling probability can be given by Px∈N (0,Id)(·|x ∈ E). The intuition behind its definition is that for all admissible polynomial families, the set of (x1, · · · , xn) with "redundant information" about learning the parameter Θ is of Lebesgue-measure zero. Therefore, a positive measure set allows you to query randomly and avoids getting coherent measurements.
Next two theorems identify the sufficent conditions for efficiently learning deterministic MDPs under polynomial realizability. Specifically, under online RL setting, we require the strong assumption that the set {ϕh(s, a)|a ∈ A} is of positive measure for all h ∈ [H] and all s ∈ S , while under generative model setting, we only require the union set ⋃ s∈S{ϕh(s, a)|a ∈ A} to be of positive measure for all h ∈ [H]. The algorithms for solving the both cases are summarized in Algorithms 4 and 5. Assumption 4.6 (Polynomial Realizability). For all h ∈ [H], Q∗h(sh, ah), viewed as the function of ϕh(sh, ah), lies in some admissible polynomial family FVh with dimension bounded by D. Theorem 4.7. For the generative model setting, assume that the set {ϕh(s, a) | s ∈ S, a ∈ A} is of positive measure at any level h. Under the polynomial realizability, Algorithm 4 almost surely learns the optimal policy π⋆ with at most N = 2DH samples. Theorem 4.8. For the online RL setting, assume that {ϕh(s, a) | a ∈ A} is of positive measure for every state s at every level h. Under polynomial realizability, within T = 2DH episodes, Algorithm 5 learns the optimal policy π⋆ almost surely.
Algorithm 4 Dynamic programming under generative model settings 1: for h = H, · · · , 1 do 2: Sample 2D points {ϕh(s(i)h , a (i) h )}2Di=1 according to Px∈N (0,Id)(·|x ∈ Eh) where Eh =
{ϕh(s, a) | s ∈ S, a ∈ A}. 3: Query the generative model with state-action pair (s(i)h , a (i) h ) at level h for i = 1, . . . , 2D,
and observe the next state s̃(i)h and reward r (i) h .
4: Solve for Q∗h with the 2D equations Q ∗ h(s (i) h , a (i) h ) = r (i) h + V ∗ h+1(s̃ (i) h ). 5: Set π∗h(s) = argmaxa Q ∗ h(s, a) and V ∗ h (s) = maxa Q ∗ h(s, a). 6: end for 7: Output π∗
Algorithm 5 Dynamic programming under online RL settings 1: for h = H, · · · , 1 do 2: Fix any action sequence a1, · · · , ah−1. 3: Play a1, · · · , ah−1 for the first h − 1 levels and reach a state sh. Sample 2D points {ϕh(sh, a(i)h )}2Di=1 according to Px∈N (0,Id)(·|x ∈ Eh) where Eh = {ϕh(sh, a) | a ∈ A}.
4: Play a(i)h at sh for i = 1, . . . , 2D, and observe the next state s̃ (i) h and reward r (i) h . 5: Solve for Q∗h with the 2D equations Q ∗ h(s (i) h , a (i) h ) = r (i) h + V ∗ h+1(s̃ (i) h ). 6: Set π∗h(s) = argmaxa Q ∗ h(s, a) and V ∗ h (s) = maxa Q ∗ h(s, a). 7: end for 8: Output π∗
We remark that our Theorem 4.8 for learning MDPs under the online RL setting relies on a very strong assumption that allows the learner to explore randomly for any state. However, this assumption is necessary in some sense, as is suggested by our lower bound example in the next subsection.

heading: 4.1 Necessity of Generic Feature Maps in Online RL

text:
In this section, we consider lower bounds for learning deterministic MDPs with polynomial realizable Q∗ under online RL setting. Our goal is to show that in the online setting the generic assumption on
the feature maps ϕh(s, ·) is necessary. On the contrary, under the generative model setting one can efficiently learn the MDPs without such a strong assumption, since at every level h the we can set the state arbitrarily.
MDP construction We briefly introduce the intuition of our construction. Consider a family of MDPs with only two states S = {Sgood, Sbad}. we set the feature map ϕh such that, for the good state Sgood, it allows the learner to explore randomly, i.e., {ϕh(Sgood, a) | a ∈ A} is of postive measure. However, for the bad state Sbad, all actions are mapped to some restricted set, which forbids random exploration, i.e., {ϕh(Sbad, a) | a ∈ A} is measure zero. This is illustrated in Figure 1. Specifically, at least Ω(dp) actions are needed to identify the groud-truth polynomial of Q∗h for Sbad, while O(d) actions suffice for Sgood.
The transition Ph is constructed as Ph(sbad|s, a) = 1 for all s ∈ S, a ∈ A, which means it is impossible for the online scenarios to reach the good state for h > 1.
Theorem 4.9. There exists a family of MDPs satisfying Assumption 4.6, such that the set {ϕh(s, a) | s ∈ S, a ∈ A} is of positive measure at any level h, but for all h there is some sbad ∈ S such that {ϕh(sbad, a) | a ∈ A} is measure zero. Under the online RL setting, any algorithm needs to play at least Ω(dp) episodes to identify the optimal policy. On the contrary, under the generative model setting, only O(d)H samples are needed.

heading: 5 Conclusions

text:
In this paper, we consider neural network and polynomial function approximations in the simulator and online settings. To our knowledge, this is the first paper that shows sample-efficient reinforcement learning is possible with neural net function approximation. Our results substantially improve upon what can be achieved with existing results that primarily rely on embedding neural networks into linear function classes. The analysis reveals that for function approximations that allows for efficient ℓ∞ recovery, such as two layer neural networks and admissible polynomial families, reinforcement learning can be reduced to parameter recovery problems, as well-studied in theories for deep learning, phase retrieval, and etc. Our method can also be potentially extended to handle three-layer and deeper neural networks, with advanced tools in [23, 24].
Our results for polynomial activation require deterministic transitions, since we cannot handle how noise propagates in solving polynomial equations. We leave to future work an in-depth study of the stability of roots of polynomial systems with noise, which is a fundamental mathematical problem and even unsolved for homogeneous polynomials. In particular, noisy tensor decomposition approaches combined with zeroth-order optimization may allow for stochastic transitions [36].
In the online RL setting, we can only show efficient learning under a very strong yet necessary assumption on the feature mapping. We leave to future work identifying more realistic and natural conditions which permit efficient learning in the online RL setting.
Finally, in future work, we hope to consider deep neural networks where parameter recovery or ℓ∞ error is unattainable, and deep reinforcement learning with representation learning [84, 15].

heading: Acknowledgements

text: JDL acknowledges support of the ARO under MURI Award W911NF-11-1-0303, the Sloan Research Fellowship, NSF CCF 2002272, and an ONR Young Investigator Award. QL is supported by NSF 2030859 and the Computing Research Association for the CIFellows Project. SK acknowledges funding from the NSF Award CCF-1703574 and the ONR award N00014-18-1-2247.

title: Going Beyond Linear RL: Sample Efficient Neural Function Approximation