summaries: The authors propose a RhythmicNet that can generate a musical soundtrack associating with human movements in a video. Unlike most existing works that aim to generate sync sounds of audio sources in videos, this work focuses on generating musical rhythm and beat along with visual motions. It mainly consists of three parts: Video2Rhythm, Rhythm2Drum, and Drum2Music. Experiments can validate that the proposed RhythmicNet can generate plausible soundtracks for different body movements.   ***Post-Rebuttal***  The rebuttal has successfully addressed my major concerns. Thus, I would like to keep my positive rating. The authors should revise the main paper by improving writing and adding new results and discussions provided in the rebuttal.

summaries: In this paper, the authors propose to generate music based on human motion videos. The authors propose the Video2Rhythm to capture the  rhythmic nature of free body movements. Then they use Rhythm2Drum module to generate drum. Finally, piano and guitar tracks are added to enrich the music through Drum2Music. Experiments show that they can generate plausible music that aligns with the videos.

summaries: The paper proposes an approach to generate rhythmic music from a human movement video. In detail, the model is three step process: 1) Video2Rhythm: Uses the patterns in the motion of human skeleton to detect a rhythm. 2) Rhytm2Drum: Convert the rhythmic patterns to drum beats and 3) Drum2Music: Use the drum beats to update the remi representation of another instrument (or multi-instrument song). These three steps are trained independently in a supervised learning paradigm.

summaries: The authors propose a method to generate musical soundtracks for silent videos of human activity. The method is named RhythmNet and is composed of three parts: Video2Rhythm, Rhythm2Drum, and Drum2Music. These three are sequential modules which take an input silent video and generate a musical soundtrack to accompany the video.  The Video2Rhythm component predicts musical beats given the video. It uses keypoints extracted from the video and encodes the rhythm as the beat and style. The Rhythm2Drum component uses the predicted rhythm and generates a drum pattern following the setup of GrooveVAE using a transformer-based encoder-decoder architecture followed by U-net for velocity and offset prediction. Finally, the Drum2Music component adds either piano or guitar accompaniment to the drum track to make a full musical soundtrack. Each of these individual components are independently trained.

summaries: The paper proposes a new method to produce a rhythmic sound consisting of basic instruments such as (piano roll, guitar chords and drum beat) given an input video containing at least one human activity. The authors leverage the input human action dynamics first using a keypoint estimation network and their velocity features. The latter features as used consequently to produce a rhythmic pattern which is used to generate a sequence of drum beats. The aforementioned drum beat sequence is then used as an output or as conditioning to a late-stage generation of a piano roll or a sequence of guitar chords. The intermediate representations and the architecture choices are discussed for each staged of the process. The authors provide both qualitative and quantitative results (opinion scores, video examples) for showing the effectiveness of their proposed architecture.

abstractText: One of the primary purposes of video is to capture people and their unique activities. It is often the case that the experience of watching the video can be enhanced by adding a musical soundtrack that is in-sync with the rhythmic features of these activities. How would this soundtrack sound? Such a problem is challenging since little is known about capturing the rhythmic nature of free body movements. In this work, we explore this problem and propose a novel system, called ‘RhythmicNet’, which takes as an input a video with human movements and generates a soundtrack for it. RhythmicNet works directly with human movements, by extracting skeleton keypoints and implementing a sequence of models translating them to rhythmic sounds. RhythmicNet follows the natural process of music improvisation which includes the prescription of streams of the beat, the rhythm and the melody. In particular, RhythmicNet first infers the music beat and the style pattern from body keypoints per each frame to produce the rhythm. Next, it implements a transformerbased model to generate the hits of drum instruments and implements a U-net based model to generate the velocity and the offsets of the instruments. Additional types of instruments are added to the soundtrack by further conditioning on generated drum sounds. We evaluate RhythmicNet on large scale video datasets that include body movements with inherit sound association, such as dance, as well as ’in the wild’ internet videos of various movements and actions. We show that the method can generate plausible music that aligns with different types of human movements.

title: How music and instruments began: a brief overview of the origin and entire development of music, from its earliest stages

venue: Frontiers in Sociology,

authors:
Bjorn H Merker
Guy S Madison
Patricia Eckerdal

title: On the role and origin of isochrony in human rhythmic entrainment

title: Percussion instruments and their history

venue: Bold Strummer Limited,

authors:
Sijie Yan
Yuanjun Xiong
Dahua Lin

title: Spatial temporal graph convolutional networks for skeleton-based action recognition

venue: arXiv preprint arXiv:1801.07455,

authors:
Ashish Vaswani
Noam Shazeer
Niki Parmar
Jakob Uszkoreit
Llion Jones
Aidan N Gomez
Łukasz Kaiser
Illia Polosukhin

title: Attention is all you need

venue: In Advances in neural information processing systems,

authors:
Olaf Ronneberger
Philipp Fischer
Thomas Brox

title: U-net: Convolutional networks for biomedical image segmentation

venue: In International Conference on Medical image computing and computer-assisted intervention,

authors:
Zihang Dai
Zhilin Yang
Yiming Yang
Jaime Carbonell
Quoc V Le
Ruslan Salakhutdinov

title: Transformer-xl: Attentive language models beyond a fixed-length context

authors:
Relja Arandjelovic
Andrew Zisserman

title: Look, listen and learn

venue: In Proceedings of the IEEE International Conference on Computer Vision,

authors:
Yusuf Aytar
Carl Vondrick
Antonio Torralba

title: Soundnet: Learning sound representations from unlabeled video

authors:
David Harwath
Antonio Torralba
James Glass

title: Unsupervised learning of spoken language with visual context

venue: In Advances in Neural Information Processing Systems,

authors:
Andrew Owens
Jiajun Wu
Josh H McDermott
William T Freeman
Antonio Torralba

title: Ambient sound provides supervision for visual learning

venue: In European conference on computer vision,

authors:
Ruohan Gao
Rogerio Feris
Kristen Grauman

title: Learning to separate object sounds by watching unlabeled video

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

authors:
Hang Zhao
Chuang Gan
Andrew Rouditchenko
Carl Vondrick
Josh McDermott
Antonio Torralba

title: The sound of pixels

venue: In Proceedings of the European conference on computer vision (ECCV),

authors:
Hang Zhao
Chuang Gan
Wei-Chiu Ma
Antonio Torralba

title: The sound of motions

authors:
Chuang Gan
Deng Huang
Hang Zhao
Joshua B Tenenbaum
Antonio Torralba

title: Music gesture for visual sound separation

venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,

authors:
Yapeng Tian
Jing Shi
Bochen Li
Zhiyao Duan
Chenliang Xu

title: Audio-visual event localization in unconstrained videos

authors:
Eli Shlizerman
Lucio Dery
Hayden Schoen
Ira Kemelmacher-Shlizerman

title: Audio to body dynamics

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

authors:
Shiry Ginosar
Amir Bar
Gefen Kohavi
Caroline Chan
Andrew Owens
Jitendra Malik

title: Learning individual styles of conversational gesture

authors:
Hsin-Ying Lee
Xiaodong Yang
Ming-Yu Liu
Ting-Chun Wang
Yu-Ding Lu
Ming-Hsuan Yang
Jan Kautz

title: Dancing to music

authors:
Supasorn Suwajanakorn
Steven M Seitz
Ira Kemelmacher-Shlizerman

title: Synthesizing obama: learning lip sync from audio

venue: ACM Transactions on Graphics (TOG),

authors:
Amir Jamaludin
Joon Son Chung
Andrew Zisserman

title: You said that?: Synthesising talking faces from audio

venue: International Journal of Computer Vision,

authors:
Tae-Hyun Oh
Tali Dekel
Changil Kim
Inbar Mosseri
William T Freeman
Michael Rubinstein
Wojciech Matusik

title: Speech2face: Learning the face behind a voice

authors:
Yang Zhou
Xintong Han
Eli Shechtman
Jose Echevarria
Evangelos Kalogerakis
Dingzeyu Li

title: Makelttalk: speaker-aware talking-head animation

authors:
Ruohan Gao
Tae-Hyun Oh
Kristen Grauman
Lorenzo Torresani

title: Listen to look: Action recognition by previewing audio

authors:
Xiang Long
Chuang Gan
Gerard De Melo
Xiao Liu
Yandong Li
Fu Li
Shilei Wen

title: Multimodal keyless attention fusion for video classification

venue: In Thirty-Second AAAI Conference on Artificial Intelligence,

authors:
Chenyu You
Nuo Chen
Yuexian Zou

title: MRD-Net: Multi-Modal Residual Knowledge Distillation for Spoken Question Answering

venue: In IJCAI,

title: Self-supervised contrastive cross-modality representation learning for spoken question answering

venue: arXiv preprint arXiv:2109.03381,

authors:
Nuo Chen
Fenglin Liu
Chenyu You
Peilin Zhou
Yuexian Zou

title: Adaptive bi-directional attention: Exploring multi-granularity representations for machine reading comprehension

venue: In ICASSP,

authors:
Chenyu You
Nuo Chen
Fenglin Liu
Dongchao Yang
Yuexian Zou

title: Towards data distillation for end-to-end spoken conversational question answering

venue: arXiv preprint arXiv:2010.08923,

title: Knowledge distillation for improved accuracy in spoken question answering

authors:
Chuang Gan
Jeremy Schwartz
Seth Alter
Martin Schrimpf
James Traer
Julian De Freitas
Jonas Kubilius
Abhishek Bhandwaldar
Nick Haber
Megumi Sano

title: Threedworld: A platform for interactive multi-modal physical simulation

venue: NeurIPS,

authors:
Chenyu You
Qingsong Yang
Lars Gjesteby
Guang Li
Shenghong Ju
Zhuiyang Zhang
Zhen Zhao
Yi Zhang
Wenxiang Cong
Ge Wang

title: Structurally-sensitive multi-scale deep neural network for low-dose CT denoising

venue: IEEE Access,

authors:
Chenyu You
Guang Li
Yi Zhang
Xiaoliu Zhang
Hongming Shan
Mengzhou Li
Shenghong Ju
Zhen Zhao
Zhuiyang Zhang
Wenxiang Cong

title: CT super-resolution GAN constrained by the identical, residual, and cycle learning ensemble (gan-circle)

venue: IEEE Transactions on Medical Imaging,

authors:
Indranil Guha
Syed Ahmed Nadeem
Chenyu You
Xiaoliu Zhang
Steven M Levy
Ge Wang
James C Torner
Punam K Saha

title: Deep learning based high-resolution reconstruction of trabecular bone microstructures from low-resolution ct scans using gan-circle

venue: In Medical Imaging

authors:
Chenyu You
Linfeng Yang
Yi Zhang
Ge Wang

title: Low-Dose CT via Deep CNN with Skip Connection and Network in Network. In Developments in X-Ray Tomography XII, volume 11113, page 111131W

authors:
Qing Lyu
Chenyu You
Hongming Shan
Ge Wang

title: Super-resolution mri through deep learning

venue: arXiv preprint arXiv:1810.06776,

authors:
Andrew Owens
Phillip Isola
Josh McDermott
Antonio Torralba
Edward H Adelson
William T Freeman

title: Visually indicated sounds

venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,

authors:
Lele Chen
Sudhanshu Srivastava
Zhiyao Duan
Chenliang Xu

title: Deep cross-modal audiovisual generation

venue: In Proceedings of the on Thematic Workshops of ACM Multimedia 2017,

authors:
Yipin Zhou
Zhaowen Wang
Chen Fang
Trung Bui
Tamara L Berg

title: Visual to sound: Generating natural sound for videos in the wild

authors:
Peihao Chen
Yang Zhang
Mingkui Tan
Hongdong Xiao
Deng Huang
Chuang Gan

title: Generating visually aligned sound from videos

venue: IEEE Transactions on Image Processing,

authors:
Tamara Berg
Debaleena Chattopadhyay
Margaret Schedel
Timothy Vallier

title: Interactive music: Human motion initiated music generation using skeletal tracking by kinect

venue: In Proc. Conf. Soc. Electro-Acoustic Music United States,

authors:
Yujia Wang
Wei Liang
Wanwan Li
Dingzeyu Li
Lap-Fai Yu

title: Scene-aware background music synthesis

venue: In Proceedings of the 28th ACM International Conference on Multimedia,

authors:
A Sophia Koepke
Olivia Wiles
Yael Moses
Andrew Zisserman

title: Sight to sound: An end-to-end approach for visual piano transcription

venue: IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP),

authors:
Kun Su
Xiulong Liu
Eli Shlizerman

title: Audeo: Audio generation for a silent performance video

venue: Advances in Neural Information Processing Systems,

authors:
Chuang Gan
Deng Huang
Peihao Chen
Joshua B. Tenenbaum
Antonio Torralba

title: Foley music: Learning to generate music from videos

venue: In ECCV,

title: Multi-instrumentalist net: Unsupervised generation of music from body movements

venue: arXiv preprint arXiv:2012.03478,

authors:
Fabrizio Pedersoli
Masataka Goto

title: Dance beat tracking from visual information alone

authors:
Hao-Wen Dong
Wen-Yi Hsiao
Li-Chia Yang
Yi-Hsuan Yang

title: Musegan: Multi-track sequential generative adversarial networks for symbolic music generation and accompaniment

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

authors:
Adam Roberts
Jesse Engel
Colin Raffel
Curtis Hawthorne
Douglas Eck

title: A hierarchical latent vector model for learning long-term structure in music

venue: In International Conference on Machine Learning,

authors:
Jon Gillick
Adam Roberts
Jesse Engel
Douglas Eck
David Bamman

title: Learning to groove with inverse sequence transformations

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

authors:
Sageev Oore
Ian Simon
Sander Dieleman
Douglas Eck
Karen Simonyan

title: This time with feeling: Learning expressive musical performance

venue: Neural Computing and Applications,

authors:
Cheng-Zhi Anna Huang
Ashish Vaswani
Jakob Uszkoreit
Ian Simon
Curtis Hawthorne
Noam Shazeer
Andrew M Dai
Matthew D Hoffman
Monica Dinculescu
Douglas Eck

title: Music transformer: Generating music with long-term structure

venue: In International Conference on Learning Representations,

authors:
Curtis Hawthorne
Andriy Stasyuk
Adam Roberts
Ian Simon
Cheng-Zhi Anna Huang
Sander Dieleman
Erich Elsen
Jesse Engel
Douglas Eck

title: Enabling factorized piano music modeling and generation with the maestro dataset

venue: arXiv preprint arXiv:1810.12247,

authors:
Yu-Siang Huang
Yi-Hsuan Yang

title: Pop music transformer: Beat-based modeling and generation of expressive pop piano compositions

authors:
Jesse Engel
Matthew Hoffman
Adam Roberts

title: Latent constraints: Learning to generate conditionally from unconditional generative models

venue: arXiv preprint arXiv:1711.05772,

authors:
Prafulla Dhariwal
Heewoo Jun
Christine Payne
Jong Wook Kim
Alec Radford
Ilya Sutskever

title: Jukebox: A generative model for music

venue: arXiv preprint arXiv:2005.00341,

title: Musenet. OpenAI Blog, 2019

authors:
Kristy Choi
Curtis Hawthorne
Ian Simon
Monica Dinculescu
Jesse Engel

title: Encoding musical style with transformer autoencoders

venue: arXiv preprint arXiv:1912.05537,

authors:
Stefan Lattner
Maarten Grachten

title: High-level control of drum track generation using learned patterns of rhythmic interaction

venue: IEEE Workshop on Applications of Signal Processing to Audio and Acoustics (WASPAA),

authors:
Zhe Cao
Gines Hidalgo
Tomas Simon
Shih-En Wei
Yaser Sheikh

title: Openpose: realtime multi-person 2d pose estimation using part affinity fields

venue: arXiv preprint arXiv:1812.08008,

authors:
Peter Shaw
Jakob Uszkoreit
Ashish Vaswani

title: Self-attention with relative position representations

venue: arXiv preprint arXiv:1803.02155,

authors:
Marco Körner
Joachim Denzler

title: Temporal self-similarity for appearance-based action recognition in multi-view setups

venue: In International Conference on Computer Analysis of Images and Patterns,

authors:
Chuan Sun
Imran Nazir Junejo
Marshall Tappen
Hassan Foroosh

title: Exploring sparseness and self-similarity for action recognition

authors:
Debidatta Dwibedi
Yusuf Aytar
Jonathan Tompson
Pierre Sermanet
Andrew Zisserman

title: Counting out time: Class agnostic video repetition counting in the wild

authors:
Florian Krebs
Sebastian Böck
Gerhard Widmer

title: An efficient state-space model for joint tempo and meter tracking

venue: In ISMIR,

authors:
Peter Grosche
Meinard Müller
Frank Kurth

title: Cyclic tempogram—a mid-level tempo representation for musicsignals

venue: IEEE International Conference on Acoustics, Speech and Signal Processing,

authors:
Abe Davis
Maneesh Agrawala

title: Visual rhythm and beat

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops,

authors:
Nitish Shirish Keskar
Bryan McCann
Lav R Varshney
Caiming Xiong
Richard Socher

title: Ctrl: A conditional transformer language model for controllable generation

authors:
Shuhei Tsuchida
Satoru Fukayama
Masahiro Hamasaki
Masataka Goto

title: Aist dance video database: Multi-genre, multi-dancer, and multi-camera database for dance information processing

title: Learning-based methods for comparing sequences, with applications to audio-tomidi alignment and matching

venue: PhD thesis, Columbia University,

authors:
Adam Paszke
Sam Gross
Francisco Massa
Adam Lerer
James Bradbury
Gregory Chanan
Trevor Killeen
Zeming Lin
Natalia Gimelshein
Luca Antiga

title: Pytorch: An imperative style, high-performance deep learning library

venue: arXiv preprint arXiv:1912.01703,

authors:
Matthew EP Davies
Norberto Degara
Mark D Plumbley

title: Evaluation methods for musical audio beat tracking algorithms

venue: Queen Mary University of London, Centre for Digital Music, Tech. Rep. C4DM-TR-09-06,

authors:
Eitan Richardson
Yair Weiss

title: On gans and gmms

authors:
Jesse Engel
Kumar Krishna Agrawal
Shuo Chen
Ishaan Gulrajani
Chris Donahue
Adam Roberts

title: Gansynth: Adversarial neural audio synthesis

heading: 1 Introduction

text:
Rhythmic sounds are everywhere, from raindrops falling on surfaces, to birds chirping, to machines generating unique sound patterns. When sounds accompany visual scenes, they enhance the perception of the scene by complementing it with additional cues such as semantic association of events, means of communication, drawing attention to parts of the scene, and many more. For visual scenes ∗These authors contributed equally. †Department of Electrical & Computer Engineering, University of Washington, Seattle, USA. ‡Department of Applied Mathematics, University of Washington, Seattle, USA §Corresponding author: shlizee@uw.edu
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
that include activity of people, rhythmical music that is in-sync with the rhythm of body movements can emphasize the actions of the person and enhance the perception of the activity [1, 2]. Indeed, to support such synchrony, a usual practice is that a musical soundtrack is chosen manually in professionally edited videos.
Drum instruments serve as the fundamental part in music by generating the underlying leading rhythm patterns. While drum instruments vary in shape, form, and mechanics, their main purpose is to set the essential rhythm for any music. Indeed, drums are known to have existed from around 6000 BC, and even beforehand there were instruments based on principle of hitting two objects and generating sounds [3]. On top of drum patterns, additional instruments add secondary patterns and melody, creating rich multifaceted music. In modern music, in composition and improvisation, it is also the case that composers would start a new musical piece by designing the rhythm for the corresponding drum track. As the piece evolves, additional accompanying instruments tracks are gradually superimposed on top of the drum track to produce the final music.
Inspired by the possibility of associating rhythmic soundtracks to videos, in this work we explore automatic generation of rhythmic music correlated with human body movements. We follow similar music composition and improvisation steps as in music improvisation by first generating the rhythm of the music that is strongly correlated with the beat and movements patterns. Such rhythm can then be then used to generate novel drums music accompanying the body movements. With the rhythm being inferred, we follow further steps of music improvisation and add new instruments (piano and guitar) tracks to enrich the music. In summary, we address the challenge of generating a rhythmic soundtrack for a human movement video by proposing a novel pipeline named ‘RhythmicNet’, which translates human movements from the domain of video to rhythmic music with three sequential components: Video2Rhythm, Rhythm2Drum, and Drum2Music.
In the first stage of RhythmicNet, given a human movement video, we extract the keypoints from the video and use a spatio-temporal graph convolutional network [4] in conjunction with transformer encoder [5] to capture motion features for estimation of music beats. Since music beats are periodic and there are various visual changes occurring in human movements, we propose an additional stream, called the style, which captures fast movements. The combination of the two streams constitutes the movements rhythm and guides music generation in the next stage, called Rhythm2Drum. This stage includes an encoder-decoder transformer that given the rhythm, generates the drums performance hits and a U-net [6] which subsequently generates drums velocities and offsets. We find that these two stages are critical for generation of quality drum music. In the last stage, called Drum2Music, we complete the drum music by adopting an encoder-decoder architecture using transformer-XL [7] to generate a music track of either piano or guitar conditioning on the generated drum performance. An overview of RhythmicNet is shown in Fig. 2. Our main contributions are: (i) To the best of our knowledge, we are the first to generate a novel musical soundtrack that is in-sync with human activities. (ii) We introduce an entire pipeline, named ‘RhythmicNet’, which implements three stages to complete the transformation. (iii) RhythmicNet is robust and generalizable. Experiments on datasets of large-scale dance videos and ‘in the wild’ internet videos show that music generated by RhythmicNet will be consistent with human body movements in videos.

heading: 2 Related Work

text:
Generation of sounds for a video is a challenging problem since it aims to relate two signals that are indirectly correlated. It belongs to the class of problems of Audio-Visual learning, which deals with exploration and leveraging of the correlation of both audio and video for tasks such as audiovisual correspondence [8, 9, 10, 11], video sound separation [12, 13, 14, 15], audio-visual event localization [16], transformations of audio to body movements [17, 18, 19], lips movements [20] and talking faces [21, 22, 23]. Audio-visual systems are usually developed by using multi-modal learning techniques which have been shown effective in action recognition [24, 25], speech question answering [26, 27, 28, 29, 30], 3D world physical simulation [31], and medical images analysis [32, 33, 34, 35, 36].
Several approaches were proposed for the relation of sounds to a video. A deep learning approach showed the potential of such application by proposing a recurrent neural network to predict the audio features of impact sounds from videos. The approach was able to produce a waveform from these features [37]. In a subsequent work, a conditional generative adversarial network was proposed to achieve cross-modal audio-visual generation of musical performances [38]. In both methods, single image was used as an input, and the network performed supervision on instrument classes to generate a low-resolution spectrogram. Concurrently, for natural sounds, a Sample RNN-based method [39] has been introduced to generate sounds such as baby crying, water flowing, given a visual scene. This approach was enhanced by an audio forwarding regularizer that considers the real sound as an input and outputs bottle-necked sound features which provide stronger supervision for natural sound predictions only from visual features [40]. Compared to natural sounds with relatively simple characteristics, music contains more complex elements. While such problem is more challenging, the possibility to correlate movement and sounds was shown by a rule-based sensor system which succeeded to convert sensed motion to music notes [41].
In recent years there has been remarkable progress in the generation of music from video. An interactive background music synthesis algorithm guided by visual content was introduced to synthesize dynamic background music for different scenarios [42]. The method, however, relied on reference music retrieval and could not generate new music directly. Direct music generation approaches have been developed for videos capturing a musician playing an instrument. A ResNet-based method was proposed to predict the pitch and the onsets events, given video frames of top-view videos of pianists playing the piano [43]. Later, Audeo [44] demonstrated the possibility to transcribe video to high-quality music. While the results of such methods are promising, the generation is limited to a single instrument. Thereby, Foley Music [45] proposed a Graph-Transformer network to generate Midi events from body keypoints and achieved convincing synthesized music from Midi. Further, Multi-instrumentalist Net [46] showed generation of music waveform of different instruments in an unsupervised way. While these approaches demonstrate the possibilities of generating music from videos, the videos need to contain solid visual cues such as instruments to indicate the types of music being generated. It still remains unclear whether it is possible to generate music when such visual cues do not exist. With respect to human movement, this would be extracting the characteristics of the movement and attempting to match music with them. In this regard, a recent novel approach of dance beat tracking was proposed [47]. The approach is aimed at detecting the characteristics of musical beats from a video of a dance by using visual information only. Inspired by this work, we design a novel methodology to estimate in a precise way musical characteristics, such as beats, from movements and utilize them to improvise new music.
There has been vital recent progress in the generation of music from its representations, such as symbolic representations, as well. In particular, Musical Instrument Digital Interface (Midi) representation has been shown to be useful in modeling and generating music. Initial works converted Midi into piano-roll representation and used generative adversarial networks [48] or variational autoencoders [49, 50] to generate new music. A limitation of the piano-roll is that it may result in memory inefficiency when the length of the music is too long. In order to address this limitation, eventbased representation has been proposed and was shown to be a useful and efficient representation in modeling music [51, 52, 53]. While the event-based representation enabled models to obtain convincing generated results, it lacks metrical structure, leading to unsteady beats in the generated samples. Thereby, recently, a new representation called Remi was proposed to impose a metrical structure in the input data so that the models can include awareness of the beat-bar-phrase hierarchical structure in the music [54]. In our work, we utilize the Remi representation by converting the Midi into
Remi in the Drum2Music stage. While the methods mentioned above generate unconditional music, it was shown to be possible to constrain music generation. For example, it was proposed to constrain generative models to sample for predefined attributes [55]. Systems such as Jukebox [56] and MuseNet [57] showed the possibility of generating music based on user preferences which correspond to network model specifically trained with labeled tokens as a conditioning input. Furthermore, a Transformer autoencoder has been proposed to aggregate encoding of Midi data across time to obtain a global representation of style from a given performance. Such a global representation can be used to control the style of the music [58]. Additional models have been proposed, such as a model capable of generating kick drums given conditional signals including beat, downbeat, onset of snare and Bass [59]. In RhythmicNet, conditioning additional music instruments on the drum track is expected to provide a richer soundtrack. For this purpose, in the Drum2music stage, we utilize the Transformer autoencoder and consider the drum track as the conditioning input and generate the track of another musical instrument, such as piano or guitar.

heading: 3 Methods

text:
RhythmicNet includes three sequential components: 1) Association of rhythm with human movements (Video2Rhythm), 2) Generation of drum track from rhythm (Rhythm2Drum), 3) Adding instruments to the drum track (Drum2Music). We describe the details of each stage below.
Video2Rhythm. We decompose the rhythm into two streams: beats and style. We propose a novel model to predict music beats and a kinematic offsets based approach to extract style patterns from human movements.
Music Beats Prediction. Beat is a binary periodic signal determined by fixed tempo, and it is obtained by music beat prediction network, which learns the beat by pairing body keypoints with ground truth music beats in a supervised way. To predict regular music beats from human body movements, we extract 2D skeleton keypoints via the OpenPose framework [60] and perform first-order difference to obtain the velocity for each video. Motion sequences is considered as three dimensional tensor X ∈ RV×T×2 where V is the number of keypoints, T is the number of frames, and the last dimension indicates the 2D coordinates. We formulate the prediction of music beats as a temporal binary classification problem: Given the skeleton keypoints X , we aim to generate the output with the same length Y ∈ RT , where each frame is classified into ‘beat’ (y = 1) or ‘non-beat’ (y = 0). We encode the keypoints using a spatio-temporal graph convolutional neural network (ST-GCN) [4]. Such encoding represents the skeleton sequence as an undirected graph G = (V,E), where each node vi ∈ V corresponds to a key point of the human body and edges reflect the connectivity of body keypoints. The sequence passes through a spatial GCN to obtain the features at each frame independently, and then a temporal convolution is applied to the features to aggregate the temporal cues. The encoded motion features are then represented as P = AXWSWT ∈ RV×Tv×Cv , where X is the input, A ∈ RV×V is the adjacency of matrix of the graph defined based on the body keypoints connections. WS and WT are the weight matrices of spatial graph convolution and temporal convolution. Tv and Cv indicate the number of temporal dimension and feature channels. We obtain the final motion features P ∈ RTv×Cv by averaging the node features. Given the motion feature P , we use a transformer encoder that contains a stack of multi-head selfattention layers to learn the correlation between different frames. Due to the periodicity of the music beats, we introduce two components to allow the model to capture them more accurately: 1) We adopt a relative position encoding [61] to allow attention to explicitly resolve the distance between two tokens in a sequence instead of using common positional sinusoids to represent timing information.
This encoding is critical for modeling the timing in music where relative differences matter more than their absolute values [52]. 2) We use temporal self-similarity matrix of motion features (SSM), which has been shown effective in human action recognition in regularization of the transformer and counting the repetitions of periodic movements [62, 63, 64]. SSM can be constructed by computing all pairwise similarities Sij = f(Pi, Pj) between pairs of frame-level motion features Pi and Pj , where f(·) is the similarity function. We use the negative of the squared euclidean distance as the similarity function, f(a, b) = −||a− b||2, followed by taking softmax over the time axis. SSM has only one channel and it goes through a convolution layer Ŝ = Conv(S) and then added to every attention head in the self attention component implemented as
Attention(Q,K, V ) = Softmax( QKT + Ŝ +R√
Dk )V,
where Q,K, V are the standard query, key and value respectively, and R is the ordered relative position encoding for each possible pairwise distance among pairs of query and key on each head. We train the model using weighted binary cross-entropy loss that puts more weight toward the beat category to address imbalances. In comparison with previous work [47], the combination of graph representation, relative selfattention and SSM components enables the model to better capture the spatial-temporal structures in body dynamics which allows for more accurate beat estimation. The output of the network is the beat activation function; i.e., for each video frame, the model predicts its probability of being a ‘beat’ frame. To obtain beat positions, we apply an algorithm based on HMM decoding proposed in [65].
Style Extraction. While beats represent the monotonic periodic pattern occurring at fixed time intervals (i.e. periodic signal), there are additional a-periodic components in the rhythm. In particular, between two music beats, there are typically various irregular movements that contribute to the rhythm. In contrast to beats, these patterns are inconsistent and it is unclear how to systematically extract such patterns from visual information. We, therefore, define an additional stream, called style, which records incidences of transitional movements of the human body, such as rapid and sudden movements. For prediction of such events, we apply a rule-based approach since the definition of style is implicit and there is no data to learn a mapping from body keypoints to transitional movements. The style is defined as a binary stream that indicates transition time points as 1 and non-transitional time points as 0. We compose the style stream by implementing several steps based on spectral analysis of kinematic offsets of the motion [66]. The first step is to compute kinematic offsets. Kinematic offsets are 1D time series signal representing the average acceleration of the human body over time. To obtain kinematic offsets, we calculate the directogram of the motion by factoring it into different angles. Given Ft(j, t) as the velocity magnitude of joint j at time t, we formulate the directogram D(t, θ) [67] as:
D(t, θ) = ∑ j Ft(j, t)1θ(∠Ft(j, t)), where 1θ(φ) = { 1 |θ − φ| ≤ 2π/Nbins 0 otherwise
(1)
The indicator function 1θ(φ) is used to distribute the motion of all joints into Nbins angular intervals. Then the first-order difference of the directogram is calculated to obtain the acceleration of motion across different angles. The mean acceleration in the positive direction measures motion strength (i.e., the larger the value, the more remarkable in motion strength) and corresponds to the kinematic offsets. Once kinematic offsets are obtained, in the next step we perform a Short-Time-Fourier Transform (STFT) on them to identify peaks in the change of acceleration. The highest frequency bin in STFT (out of 8) represents the most profound transitions in the signal and we use the highest frequency bin to extract the style patterns from motion. The peaks are defined as 10% top magnitudes over the duration of the video. We mark the timepoints of the peaks as 1 and other timepoints as 0. Since STFT results with low temporal resolution (due to hop-size set to 4 for efficient computation) we upsample the binary signal by the hop size to obtain a binary signal that matches the resolution of the video. The output signal is re-sampled to have the same sampling rate as the music beats.
Rhythm Composition. We obtain the rhythm by adding the streams of the beats and the style into a single signal. The rhythm should correspond to the correlation of body movements with the tempo of the soundtrack.
Rhythm2Drum. The stage of Rhythm2Drum interprets the provided rhythm from previous stage into drum sounds. In this stage we follow the GrooveVAE setup [50], where each drum track can be represented by three matrices: hits, velocities, and offsets. The hits represent the presence of drum onsets and is a binary matrix H ∈ RN×T , where N is the number of drum instruments and T is the number of time steps (one per 16-th note). The velocities is a continuous matrix, V , that reflects how hard drums are struck, with values in the range of [0, 1]. The offsets O is also a continuous matrix and stores the timing offsets, with values in the range of [−0.5, 0.5). These values indicate how far and in which direction each note’s timing lie, relative to the nearest 16-th note. The matrices V O, and H have the same shape.
Given the input rhythm sequence Y ∈ R1×T , we aim to generate the H , V and O. In contrast to GrooveVAE [50], which models all three matrices simultaneously with multiple losses, we model H , V , and O smoothly in two steps using the combination of an encoder-decoder transformer [5] and a U-net [6]. In the first step, the binary rhythm is passed as an input to the transformer encoder. In the decoder, the H matrix is converted into word a sequence defined by a small vocabulary set of all possible combinations of hits, and is mapped back to a binary matrix for the final output. We observe that autoregressively learning the hits H as a word sequence, the transformer can generate more natural and diverse drum onsets. We train the transformer with the cross-entropy loss. In the second step, we add style patterns (velocity and offsets) to the onsets. Since H has the same shape as V and O, we can consider it as a transformation between 2 images of the same shape. To achieve such transformation, we adopt a U-net [6] to take the onset matrix H as an input and to generate V and O. We use Mean-Square Error (MSE) loss for U-net optimization. Finally, we convert the generated matrices H , V and O to the Midi representation to produce the drum track.
Drum2Music. In this last stage we add further instruments to enrich the soundtrack. Since the drum track contains rhythmic music, we propose to condition the additional instrument stream on the generated drum track. Specifically, we propose an encoder-decoder architecture, such that the encoder receives the drum track as an input, and the decoder generates the track of another instrument. We consider the piano or guitar as the additional instruments, since these are dominant instruments. We use Remi representation [54] to represent multi-track music. Compared to the commonly-used Midilike event representation [52], the Remi representation includes information such as Tempo changes, Chord, Position, and Bar, which allow our model to learn the dependency of note events occurring at same positions across bars. For both the encoder and decoder, we adopt the transformer-XL network model which extends the transformer by including the recurrence mechanism [7]. The recurrence mechanism enables the model to leverage the information of past tokens beyond the current training segment and to look further into the history.
The encoder contains stack of multi-head self-attention layers. Its output Ei can be represented as: Ei = Enc(xi,MEi ), where M E i is the encoder memory used for the i-th bar input and the encoder hidden state sequence computed in previous recurrent steps. Similarly, in the decoder, the prediction of j-th token of the i-th bar yi,j is formulated as yi,j = Dec(yi,t<j ,MDi , Ei), where yi,t<j are the previously generated tokens in the same bar, MDi is the decoder memory used for i-th bar, and Ei is the corresponding encoder output of the same bar. The decoder consists of a stack of layers with casual self-attention, cross-attention to the encoder output, and feed-forward network.
For the training data, we split the music piece into segments with a total number of bars. In the encoder, for recurrent step i, we provide the i-th bar of drum performance xi to the transformer-XL. We adopt a teacher forcing strategy and feed the ground truth tokens into the decoder to generate the next tokens. We minimize the negative log-likelihood (NLL) between generated tokens and ground truth tokens to optimize the model. During inference, the drum track is given to the encoder for each bar and the tokens in the decoder are generated one by one. Finally, we use the temperature-controlled stochastic top-k sampling method [68] to randomly generate a new music track.

heading: 4 Experiments & Results

text:
Datasets. We use the AIST Dance Video Database, a large-scale collection of dance videos in 60fps for training and testing of Video2Rhythm [69]. This database includes 10 street dance genres, 35 dancers, 9 camera viewpoints, and 60 musical pieces covering 12 types of tempo. For each genre, we use 1080 dance videos, resulting in total of 10, 800 videos. We split the samples into train/validate/test sets by 0.8/0.1/0.1 based on the dance genres, dancers, and camera ids.
For Rhythm2Drum, we use the Groove Midi dataset [50] which contains 1150 Midi files and over 22, 000 measures of drumming. We split the data into 0.8/0.1/0.1 of train/validate/test sets.
For Drum2Music, we extract two subsets of Lakh Midi dataset [70] to separately train Drum2Piano and Drum2Guitar models. For Drum2Piano, we select the Midi files that contain both tracks of drums and acoustic piano with at least 16 bars, and we consider 16 bars to be a single segment. This results in 34991/1944/1944 segments for train/validate/test sets respectively. For drum2guitar, we perform a similar selection to obtain 12904/717/717 segments for train/validate/test sets respectively.
Implementation Details. We use Pytorch [71] to implement all models in RhymicNet with two Titan X GPUs. For all videos, we extract 17 keypoints of body joints. In Video2Rhythm, the network contains a 10-layer ST-GCN and a 2-layer transformer encoder with 2-head attention. For the style extraction part, the motion sequence is down-sampled to 15fps to calculate the kinematic offsets. The number of bins used for the directogram is 12, and a 16-point FFT with hop-size of 4 is applied to extract candidate styles. Each detected style is repeated 4 times to match the hop size, and then is up-sampled to original time resolution of 60fps and re-indexed in unit of quarter note based on estimated tempo. In Rhythm2Drum, the Hits transformer includes 3 layers, and 4 heads in both the encoder and the decoder. The vocabulary size of the decoder input is 152, consisting of all possible combinations of 9 types of drum hits in the dataset. U-net that generates velocity and offsets contains
4 down-sample blocks with channel sizes of 16, 32, 64, 128. In Drum2Music, the model consists of a recurrent transformer encoder and a recurrent transformer decoder. We set the number of encoder layers, decoder layers, encoder heads and decoder heads to 4, 8, 8, and 8 respectively. The length of the training input tokens and the length of the memory is 256. We provide additional configuration details in the supplementary materials. Code. System setup and code are available in a Github repository5.
Video2Rhythm Evaluation. Following the rubrics proposed for musical beat tracking [72], we compute the performance in terms of F-score measure, Cemgil’s score (Cem), and Correct Metrical Level continuity required/not required (CMLc/t) score. To compare with existing approaches, we implement a baseline temporal convolutional network (TCN) for beat prediction [47]. The comparison and ablation results are shown in Table 1. The best method of Video2Rhythm (STGCN+TF+SSM+RelAttn) significantly outperforms the baseline model in all metrics by a large margin. In particular, the continuity scores outperform the baseline model by more than 25%, indicating the estimated beat sequence is significantly more consistent.
Rhythm2Drum Evaluation. We use several metrics to evaluate Rhythm2Drum. For measuring the diversity of the generated drum hits, we adopt the Number of Statistically-Different Bins (NDB) metric proposed and used in [73, 74, 45]. To compute NDB, we cluster all training examples into k = 50 Voronoi cells by K-means. The generated examples are then assigned to the nearest cell. NDB is reported as the number of cells where the number of training examples is statistically significantly different from the number of generated examples by a two-sample Binomial test. For each model, we generate 9000 samples from the testing set and perform the comparison. For evaluation of velocities and offsets, we compute the Mean-Squared Error (MSE) for the test set. We compare our methods with the baseline model GrooveVAE [50]. The results are shown in Table 2. The results show that using hits sequences to generate the drum track enables a more diverse set of samples such that the next U-net component, which generates velocities and offsets, in turn will generate more realistic drumming sounds.
Drum2Music Evaluation. To evaluate the generated piano and guitar tracks, we use objective metrics such as PC/bar (pitch count per bar), PI (average pitch interval), IOI (average inter-onset interval) described in [75]. For these metrics we compare the statistics calculated on the test dataset and on the generated music. For additional metrics of PCH (pitch class histogram) and NLH (note length histogram), we calculate the overlapping area (OA) between the statistics on the test dataset and the generated music for each sample and report the average of them. In addition, we compare the NLL loss based on the validation set. The numerical results are shown in Table 3. We compare two versions (with and without using memory) to show the effectiveness of the recurrence mechanism. Our results show that for both Drum2Piano and Drum2Guitar with recurrent encoder-decoder transformer (i.e. with memory), the NLL loss is lower for the validation set and the statistics of the generated samples are much closer to the test dataset than the no-memory counterpart.
In the wild Experiments and Qualitative Evaluation. In Fig. 6, we show a set of examples of generated soundtracks for video clips in AIST dataset and ‘in the wild’ clips downloaded from YouTube. For the AIST dataset, we generate and compare tracks of predicted beats with the ground-truth(GT) beats. The predicted and GT tracks appear to be in close agreement. We then demonstrate the extracted style and its correspondence to frames which exhibit special movements. The beat and style tracks constitute the rhythm from which the waveform of drum music is generated. To test and demonstrate the generality of RhythmicNet we apply it to videos clips of various human activity. Examples of such
5https://github.com/shlizee/RhythmicNet
activities are shown in Fig. 6 and include Ice Skating and Playing Football. We provide additional examples and videos clips along with the soundtracks in the Supplementary Materials. The generated rhythms are well synchronized with the videos and the drum track appears to be in-sync with the activities. In addition, we demonstrate the generated waveform an additional instrument (guitar) in Fig. 6. Additional instruments indeed provide a richer music that accompanies the movements.
Human Perceptual Evaluation of Soundtrack Music. In addition to the objective evaluation of the different components of RhythmicNet we also performed human perceptual surveys using Amazon Mechanical Turk. These surveys were intended to evaluate the effectiveness of RhythmicNet generated soundtracks to align with the movements and the extent that the generated soundtrack enhance the overall perception of the video compared with various soundtrack controls. Since RhythmicNet ultimately targets in the wild videos, for which there are no given background soundtracks we ran three surveys that focused on these videos. For all surveys, no background on the survey or RhythmicNet was given to the participants to avoid perceptual biases. We surveyed 85 participants individually, where each participant was asked to evaluate 10 videos each with around 10 seconds (850 segments in total) along with different generated soundtracks.
In the first survey, we asked people (non-experts) to choose the video that they prefer, including a video without soundtrack and 3 variations of soundtracks generated by our approach (drums-only or drums with another instrument). Results in Table 4 clearly indicate a preference of a video
with a soundtrack. Furthermore, interestingly, preference for which instruments are included in the track split almost equally between the 3 provided variations, with slight preference for tracks with Drums+Piano.
In the second survey, we asked people to watch the same human activity video with different soundtracks and answer the question: "In which video the sound best matches the movements?". The given options of the soundtracks were generated soundtracks with Random, Shuffle and RhythmicNet rhythms. The Random drum track was generated with Rhythm2Drum method with a random rhythm with 50% chance to be ON or OFF at each time step. The chance of 50% was chosen such that there is a significant probability that the a rhythm that sounds like a real rhythm will be sampled. We found that sampling with lower probability would generate rhythms that do not sound well at all. The Shuffle drum track was generated with Rhythm2Drum method but the order in the rhythm is shuffled. RhythmicNet option corresponded to the drum track generated with Rhythm2Drum method. From results shown in Table 5(left) we observe a clear indication that the drum tracks generated with our method are chosen to be the best match to the movements more frequently (41.4% (Ours) v.s. 30.8% (Random) and 27.8% (Shuffle)).
In an additional survey, we performed a perceptual ablation study to test how the two components, Video2Rhythm and Rhythm2Drum, influence the perception of the soundtrack compared to baseline approaches. Survey results shown in Table 5(right) and suggest that in comparison to the baseline these two components significantly improve the perception of the soundtrack.

heading: 5 Conclusion and Discussion

text: In this exploratory work, we have considered a creative task of automatically generating novel rhythmic soundtracks consistent with human body movements captured in a video. Our results show that RhythmicNet pipeline is able to achieve this creative task and generate soundtracks that align with movements and enhance the perception of them when the video is being watched. At its core, RhythmicNet defines and implements a systemic approach of soundtrack generation by following the process of music improvisation in which a rhythm of movements is established and is translated to drumming music with potentially additional accompanying instruments. We foresee future potential applications in video creation and editing, which RhythmicNet can pave the way to unlock. As features for music generation we have chosen body keypoints, while it is unclear which features are most informative for music generation. For human body movements, body keypoints are strongly correlated with movements, and in addition, body keypoints are efficiently computed per each frame. In terms of limitations and future enhancements of the current setup of RhythmicNet, novel components will need to be considered to address the transition from rhythmic drum track to a full bodied music with a symphony of instruments, since currently the addition of a single instrument (piano or guitar) to the drum track is implemented. Furthermore, enabling RhythmicNet to operate in real-time would allow the music to be interactive with people and their movements. However this may require a more computationally extensive generative approach. Due to the fact that the main cue for the generated music is human body movements, one possible concern could be that the soundtrack generated with RhythmicNet could be used to manipulate the original sounds of the video, and to create a fake impression of people activity. Also additional concern is that generated music could sound too familiar to the music on which the models in RhythmicNet have been trained. These are common concerns in the application of generative models. Failure in RhythmicNet may bring up an unsatisfying soundtrack but we do not expect serious consequences from this.

title: How Does it Sound? Generation of Rhythmic Soundtracks for Human Movement Videos


summaries: Popular RL (both online and offline) algorithms iterate between two stages: policy evaluation where a Q-function: $S \times A \rightarrow \mathbb{E} \sum r$ is estimated and policy improvement where the policy $\pi: S \rightarrow A$ which maximizes the rewards is constructed. Typically, the stages are interleaved through the training process. The paper evaluates and argues for the idea of using, in the case of offline RL, only a single step of policy improvement after training Q-function to convergence.

summaries: # Offline RL Without Off-Policy Evaluation  ## Summary  The paper examines an issue with existing offline RL methods and proposes a way to prevent the issue that leads to a strong family of baselines. The key idea is not to perform multiple steps of off-policy evaluation and improvement in offline RL.  In addition to providing evidence to the claim that one-step methods outperform multistep and iterative ones, the paper also provides explantion and a toy example that shed light on the issues faced by multistep and iterative offline RL methods. I believe these examples can be useful in the future as "unit tests" for new offline RL methods.  ## For the response  Could you please comment on Gulcehre et al. (https://arxiv.org/pdf/2103.09575.pdf) in relation to your work?   Please include a discussion of the broader societal impact of your work.

summaries: The paper investigates the well-known 1-step heuristic for Q-function based offline RL methods. The method is evaluated for a model-free, Q-function based offline RL method on various benchmarks and the overall good performance of the approach is shown. The paper differs from results published in [1] mainly by the benchmarks used and the analysis of the reasons for the good performance.   [1] Gulcehre et al, Addressing Extrapolation Error in Deep Offline Reinforcement Learning, preprint 2021.

summaries: The authors study the notion of iterative policy improvement in offline reinforcement learning, notably finding that a single policy improvement step can outperform standard iterative benchmarks on the D4RL benchmark. To provide more insight on this, the authors also compare to an intermediate version, “multi-step”, and analyze the performance of the three variants (one-step, multi-step, and iterative) with different regularization hyperparameters. They also show results for the MSE of the estimated Q function, as well as illustrate multi-step overestimation on Gridworld environments. Finally, the authors discuss when multi-step algorithms are better, namely when noise signal is low and more propagation of signal can help.

summaries: This paper applies a simple baseline to the offline-RL paradigm. Rather than iterating through steps of policy evaluation and improvement as done by most current offline-RL algorithms, in this work the authors investigate the performance of one-step of constrained policy improvement on the D4RL benchmark. This simple baseline is shown to perform considerably well when compared to existing methods. The paper then claims that the reason for this is likely due to the deleterious effects of off-policy evaluation. A simple experiment of different algorithms shows that strong regularization against the behavior policy during learning can be crucial in the offline setting. The authors then analyze the potential pitfalls of off policy evaluation through simple analysis on an existing task and a convincing gridworld experiment. Finally the paper tries to shed some intuition as to when multi-step approaches may perform better than the one-step methods.

abstractText: Most prior approaches to offline reinforcement learning (RL) have taken an iterative actor-critic approach involving off-policy evaluation. In this paper we show that simply doing one step of constrained/regularized policy improvement using an on-policy Q estimate of the behavior policy performs surprisingly well. This onestep algorithm beats the previously reported results of iterative algorithms on a large portion of the D4RL benchmark. The one-step baseline achieves this strong performance while being notably simpler and more robust to hyperparameters than previously proposed iterative algorithms. We argue that the relatively poor performance of iterative approaches is a result of the high variance inherent in doing off-policy evaluation and magnified by the repeated optimization of policies against those estimates. In addition, we hypothesize that the strong performance of the one-step algorithm is due to a combination of favorable structure in the environment and behavior policy.

authors:
Joshua Achiam
David Held
Aviv Tamar
Pieter Abbeel

title: Constrained policy optimization

venue: In International Conference on Machine Learning,

authors:
Alekh Agarwal
Nan Jiang
S. Kakade

title: Reinforcement learning: Theory and algorithms

authors:
P. Amortila
Nan Jiang
Tengyang Xie

title: A variant of the wang-foster-kakade lower bound for the discounted setting

authors:
Jacob Buckman
Carles Gelada
Marc G. Bellemare

title: The importance of pessimism in fixed-dataset policy optimization, 2020

title: The truncated normal distribution

authors:
Jinglin Chen
Nan Jiang

title: Information-theoretic considerations in batch reinforcement learning

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

authors:
Xinyue Chen
Zijian Zhou
Zheng Wang
Che Wang
Yanqiu Wu
Keith Ross

title: Bail: Bestaction imitation learning for batch deep reinforcement learning

venue: Advances in Neural Information Processing Systems,

authors:
Yaqi Duan
Zeyu Jia
Mengdi Wang

title: Minimax-optimal off-policy evaluation with linear function approximation

authors:
Justin Fu
Aviral Kumar
Ofir Nachum
George Tucker
Sergey Levine

title: D4rl: Datasets for deep data-driven reinforcement learning

venue: arXiv preprint arXiv:2004.07219,

authors:
Scott Fujimoto
David Meger
Doina Precup

title: Off-policy deep reinforcement learning without exploration

venue: arXiv preprint arXiv:1812.02900,

authors:
Scott Fujimoto
Herke van Hoof
David Meger

title: Addressing function approximation error in actor-critic methods

venue: arXiv preprint arXiv:1802.09477,

authors:
Scott Fujimoto
Edoardo Conti
Mohammad Ghavamzadeh
Joelle Pineau

title: Benchmarking batch deep reinforcement learning algorithms

venue: arXiv preprint arXiv:1910.01708,

authors:
Wonjoon Goo
Scott Niekum

title: You only evaluate once – a simple baseline algorithm for offline rl

venue: In Offline Reinforcement Learning Workshop at Neural Information Processing Systems,

authors:
Caglar Gulcehre
Ziyu Wang
Alexander Novikov
Tom Le Paine
Sergio Gómez Colmenarejo
Konrad Zolna
Rishabh Agarwal
Josh Merel
Daniel Mankowitz
Cosmin Paduraru

title: Rl unplugged: Benchmarks for offline reinforcement learning

venue: arXiv preprint arXiv:2006.13888,

authors:
Caglar Gulcehre
Sergio Gómez Colmenarejo
Ziyu Wang
Jakub Sygnowski
Thomas Paine
Konrad Zolna
Yutian Chen
Matthew Hoffman
Razvan Pascanu
Nando de Freitas

title: Regularized behavior value estimation

venue: arXiv preprint arXiv:2103.09575,

authors:
Natasha Jaques
Asma Ghandeharioun
Judy Hanwen Shen
Craig Ferguson
Agata Lapedriza
Noah Jones
Shixiang Gu
Rosalind Picard

title: Way off-policy batch deep reinforcement learning of implicit human preferences in dialog, 2019

authors:
Sham Kakade
John Langford

title: Approximately optimal approximate reinforcement learning

venue: In ICML,

authors:
Diederik P Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

venue: arXiv preprint arXiv:1412.6980,

authors:
Ilya Kostrikov
Jonathan Tompson
Rob Fergus
Ofir Nachum

title: Offline reinforcement learning with fisher divergence critic regularization

venue: arXiv preprint arXiv:2103.08050,

authors:
Aviral Kumar
Justin Fu
Matthew Soh
George Tucker
Sergey Levine

title: Stabilizing off-policy q-learning via bootstrapping error reduction

venue: In Advances in Neural Information Processing Systems,

authors:
Aviral Kumar
Aurick Zhou
George Tucker
Sergey Levine

title: Conservative q-learning for offline reinforcement learning

venue: arXiv preprint arXiv:2006.04779,

authors:
Romain Laroche
Paul Trichelair
Remi Tachet Des Combes

title: Safe policy improvement with baseline bootstrapping

authors:
Sergey Levine
Aviral Kumar
George Tucker
Justin Fu

title: Offline reinforcement learning: Tutorial, review, and perspectives on open problems

venue: arXiv preprint arXiv:2005.01643,

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:
Volodymyr Mnih
Koray Kavukcuoglu
David Silver
Andrei A Rusu
Joel Veness
Marc G Bellemare
Alex Graves
Martin Riedmiller
Andreas K Fidjeland
Georg Ostrovski

title: Human-level control through deep reinforcement learning

authors:
Rémi Munos
Tom Stepleton
Anna Harutyunyan
Marc Bellemare

title: Safe and efficient off-policy reinforcement learning

authors:
Ofir Nachum
Bo Dai
Ilya Kostrikov
Yinlam Chow
Lihong Li
Dale Schuurmans

title: Algaedice: Policy gradient from arbitrary experience

authors:
Kimia Nadjahi
Romain Laroche
Rémi Tachet des Combes

title: Safe policy improvement with soft baseline bootstrapping, 2019

authors:
Tom Le Paine
Cosmin Paduraru
Andrea Michi
Caglar Gulcehre
Konrad Zolna
Alexander Novikov
Ziyu Wang
Nando de Freitas

title: Hyperparameter selection for offline reinforcement learning, 2020

authors:
Xue Bin Peng
Aviral Kumar
Grace Zhang
Sergey Levine

title: Advantage-weighted regression: Simple and scalable off-policy reinforcement learning

authors:
Martin L Puterman
Moon Chirl Shin

title: Modified policy iteration algorithms for discounted markov decision problems

venue: Management Science,

authors:
Aravind Rajeswaran
Vikash Kumar
Abhishek Gupta
Giulia Vezzani
John Schulman
Emanuel Todorov
Sergey Levine

title: Learning complex dexterous manipulation with deep reinforcement learning and demonstrations

venue: arXiv preprint arXiv:1709.10087,

authors:
Bruno Scherrer
Victor Gabillon
Mohammad Ghavamzadeh
Matthieu Geist

title: Approximate modified policy iteration

venue: arXiv preprint arXiv:1205.3054,

authors:
John Schulman
Sergey Levine
Pieter Abbeel
Michael Jordan
Philipp Moritz

title: Trust region policy optimization

venue: In International conference on machine learning,

authors:
Noah Siegel
Jost Tobias Springenberg
Felix Berkenkamp
Abbas Abdolmaleki
Michael Neunert
Thomas Lampe
Roland Hafner
Nicolas Heess
Martin Riedmiller

title: Keep doing what worked: Behavior modelling priors for offline reinforcement learning

authors:
Richard S Sutton
Andrew G Barto

title: Reinforcement learning: An introduction

venue: MIT press,

authors:
Hado Van Hasselt
Arthur Guez
David Silver

title: Deep reinforcement learning with double qlearning

venue: In Thirtieth AAAI conference on artificial intelligence,

authors:
Cameron Voloshin
Hoang M Le
Nan Jiang
Yisong Yue

title: Empirical study of off-policy policy evaluation for reinforcement learning

authors:
Qing Wang
Jiechao Xiong
Lei Han
Han Liu
Tong Zhang

title: Exponentially weighted imitation learning for batched historical data

authors:
Ruosong Wang
Dean P. Foster
Sham M. Kakade

title: What are the statistical limits of offline rl with linear function approximation?, 2020a

authors:
Ruosong Wang
Yifan Wu
Ruslan Salakhutdinov
Sham M Kakade

title: Instabilities of offline rl with pre-trained neural representation

venue: arXiv preprint arXiv:2103.04947,

authors:
Ziyu Wang
Alexander Novikov
Konrad Zolna
Josh S Merel
Jost Tobias Springenberg
Scott E Reed
Bobak Shahriari
Noah Siegel
Caglar Gulcehre
Nicolas Heess

title: Critic regularized regression

authors:
Yifan Wu
George Tucker
Ofir Nachum

title: Behavior regularized offline reinforcement learning, 2019

title: Exponential lower bounds for batch reinforcement learning: Batch rl can be exponentially harder than online

heading: 1 Introduction

text:
An important step towards effective real-world RL is to improve sample efficiency. One avenue towards this goal is offline RL (also known as batch RL) where we attempt to learn a new policy from data collected by some other behavior policy without interacting with the environment. Recent work in offline RL is well summarized by Levine et al. [2020]. In this paper, we challenge the dominant paradigm in the deep offline RL literature that primarily relies on actor-critic style algorithms that alternate between policy evaluation and policy improvement [Fujimoto et al., 2018a, 2019, Peng et al., 2019, Kumar et al., 2019, 2020, Wang et al., 2020b, Wu et al., 2019, Kostrikov et al., 2021, Jaques et al., 2019, Siegel et al., 2020, Nachum et al., 2019]. All these algorithms rely heavily on off-policy evaluation to learn the critic. Instead, we find that a simple baseline which only performs one step of policy improvement using the behavior Q function often outperforms the more complicated iterative algorithms. Explicitly, we find that our one-step algorithm beats prior results of iterative algorithms on most of the gym-mujoco [Brockman et al., 2016] and Adroit [Rajeswaran et al., 2017] tasks in the the D4RL benchmark suite [Fu et al., 2020]. We then dive deeper to understand why such a simple baseline is effective. First, we examine what goes wrong for the iterative algorithms. When these algorithms struggle, it is often due to poor off-policy evaluation leading to inaccurate Q values. We attribute this to two causes: (1) distribution shift between the behavior policy and the policy to be evaluated, and (2) iterative error exploitation whereby policy optimization introduces bias and dynamic programming propagates this bias across the state space. We show that empirically both issues exist in the benchmark tasks and that one way to avoid these issues is to simply avoid off-policy evaluation entirely. Finally, we recognize that while the the one-step algorithm is a strong baseline, it is not always the best choice. In the final section we provide some guidance about when iterative algorithms can perform better than the simple one-step baseline. Namely, when the dataset is large and behavior policy has good coverage of the state-action space, then off-policy evaluation can succeed and iterative
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
algorithms can be effective. In contrast, if the behavior policy is already fairly good, but as a result does not have full coverage, then one-step algorithms are often preferable. Our main contributions are:
• A demonstration that a simple baseline of one step of policy improvement outperforms more complicated iterative algorithms on a broad set of offline RL problems.
• An examination of failure modes of off-policy evaluation in iterative offline RL algorithms. • A description of when one-step algorithms are likely to outperform iterative approaches.

heading: 2 Setting and notation

text:
We will consider an offline RL setup as follows. LetM = {S,A, ρ, P,R, γ} be a discounted infinitehorizon MDP. In this work we focus on applications in continuous control, so we will generally assume that both S andA are continuous and bounded. We consider the offline setting where rather than interacting withM, we only have access to a dataset DN of N tuples of (si, ai, ri) collected by some behavior policy β with initial state distribution ρ. Let r(s, a) = Er|s,a[r] be the expected reward. Define the state-action value function for any policy π by Qπ(s, a) := EP,π|s0=s, a0=a[ ∑∞ t=0 γ
tr(st, at)]. The objective is to maximize the expected return J of the learned policy:
J(π) := E ρ,P,π [ ∞∑ t=0 γtr(st, at) ] = E s∼ρ a∼π|s [Qπ(s, a)]. (1)
Following Fu et al. [2020] and others in this line of work, we allow access to the environment to tune a small (< 10) set of hyperparameters. See Paine et al. [2020] for a discussion of the active area of research on hyperparameter tuning for offline RL. We also discuss this further in Appendix C.

heading: 3 Related work

text:
Iterative algorithms. Most prior work on deep offline RL consists of iterative actor-critic algorithms. The primary innovation of each paper is to propose a different mechanism to ensure that the learned policy does not stray too far from the data generated by the behavior policy. Broadly, we group these methods into three camps: policy constraints/regularization, modifications of imitation learning, and Q regularization:
1. The majority of prior work acts directly on the policy. Some authors have proposed explicit constraints on the learned policy to only select actions where (s, a) has sufficient support under the data generating distribution [Fujimoto et al., 2018a, 2019, Laroche et al., 2019]. Another proposal is to regularize the learned policy towards the behavior policy [Wu et al., 2019] usually either with a KL divergence [Jaques et al., 2019] or MMD [Kumar et al., 2019]. This is a very straighforward way to stay close to the behavior with a hyperparameter that determines just how close. All of these algorithms are iterative and rely on off-policy evaluation.
2. Siegel et al. [2020], Wang et al. [2020b], Chen et al. [2020] all use algorithms that filter out datapoints with low Q values and then perform imitation learning. Wang et al. [2018], Peng et al. [2019] use a weighted imitation learning algorithm where the weights are determined by exponentiated Q values. These algorithms are iterative.
3. Another way to prevent the learned policy from choosing unknown actions is to incorporate some form of regularization to encourage staying near the behavior and being pessimistic about unknown state, action pairs [Wu et al., 2019, Nachum et al., 2019, Kumar et al., 2020, Kostrikov et al., 2021, Gulcehre et al., 2021]. However, being able to properly quantify uncertainty about unknown states is notoriously difficult when dealing with neural network value functions [Buckman et al., 2020].
One-step algorithms. Some recent work has also noted that optimizing policies based on the behavior value function can perform surprisingly well. As we do, Goo and Niekum [2020] studies the continuous control tasks from the D4RL benchmark, but they examine a complicated algorithm involving ensembles, distributional Q functions, and a novel regularization technique. In contrast, we analyze a substantially simpler algorithm and get better performance on the D4RL tasks. We also focus more of our contribution on understanding and explaining this performance. Gulcehre et al. [2021] studies the discrete action setting and finds that a one-step algorithm (which they call “behavior value estimation”) outperforms prior work on Atari games and other discrete action tasks from the RL Unplugged benchmark [Gulcehre et al., 2020]. They also introduce a novel regularizer for the evaluation step. In contrast, we consider the continuous control setting. This is a substantial difference in setting since continuous control requires actor-critic algorithms with parametric policies while in the discrete setting the policy improvement step can be computed exactly from the Q function. Moreover, while Gulcehre et al. [2021] attribute the poor performance of iterative algorithms to “overestimation”, we define and separate the issues of distribution shift and iterative error exploitation which can combine to cause overestimation. This separation helps to expose the difference between the fundamental limits of off-policy evaluation from the specific problems induced by iterative algorithms, and will hopefully be a useful distinction to inspire future work. Finally, a one-step variant is also briefly discussed in Nadjahi et al. [2019], but is not the focus of that work. There are also important connections between the one-step algorithm and the literature on conservative policy improvement [Kakade and Langford, 2002, Schulman et al., 2015, Achiam et al., 2017], which we discuss in more detail in Appendix B.

heading: 4 Defining the algorithms

text: In this section we provide a unified algorithmic template for model-free offline RL algorithms as offline approximate modified policy iteration. We show how this template captures our one-step algorithm as well as a multi-step policy iteration algorithm and an iterative actor-critic algorithm. Then any choice of policy evaluation and policy improvement operators can be used to define one-step, multi-step, and iterative algorithms.

heading: 4.1 Algorithmic template

text:
Algorithm 1: OAMPI
input :K, dataset DN , estimated behavior β̂ Set π0 = β̂. Initialize Q̂π−1 randomly. for k = 1, . . . , K do
Policy evaluation: Q̂πk−1 = E(πk−1, DN , Q̂πk−2) Policy improvement: πk = I(Q̂πk−1 , β̂,DN , πk−1)
end We consider a generic offline approximate modified policy iteration (OAMPI) scheme, shown in Algorithm 1 (and based off of Puterman and Shin [1978], Scherrer et al. [2012]). Essentially the algorithm alternates between two steps. First, there is a policy evaluation step where we estimate the Q function of the current policy πk−1 by Q̂πk−1 using only the dataset DN . Implementations also often use the prior Q estimate Q̂πk−2 to warm-start the approximation process. Second, there is a policy improvement step. This step takes in the estimated Q function Q̂πk−1 , the estimated behavior β̂, and the dataset DN and produces a new policy πk. Again an algorithm may use πk−1 to warm-start the optimization. Moreover, we expect this improvement step to be regularized or constrained to ensure that πk remains in the support of β and DN . Choices for this step are discussed below. Now we discuss a few ways to instantiate the template.
One-step. The simplest algorithm sets the number of iterations K = 1. We learn β̂ by maximum likelihood and train the policy evaluation step to estimate Qβ . Then we use any one of the policy improvement operators discussed below to learn π1. Importantly, this algorithm completely avoids off-policy evaluation.
Multi-step. The multi-step algorithm now sets K > 1. The evaluation operator must evaluate off-policy since DN is collected by β, but evaluation steps for K ≥ 2 require evaluating policies πk−1 6= β. Each iteration is trained to convergence in both the estimation and improvement steps.
Iterative actor-critic. An actor critic approach looks somewhat like the multi-step algorithm, but does not attempt to train to convergence at each iteration and uses a much larger K. Here each iteration consists of one gradient step to update the Q estimate and one gradient step to improve the policy. Since all of the evaluation and improvement operators that we consider are gradient-based, this algorithm can adapt the same evaluation and improvement operators used by the multi-step algorithm. Most algorithms from the literature fall into this category [Fujimoto et al., 2018a, Kumar et al., 2019, 2020, Wu et al., 2019, Wang et al., 2020b, Siegel et al., 2020].

heading: 4.2 Policy evaluation operator

text: Following prior work on continuous state and action problems, we always evaluate by simple fitted Q evaluation [Fujimoto et al., 2018a, Kumar et al., 2019, Siegel et al., 2020, Wang et al., 2020b, Paine et al., 2020, Wang et al., 2021]. In practice this is optimized by TD-style learning with the use of a target network [Mnih et al., 2015] as in DDPG [Lillicrap et al., 2015]. We do not use any double Q learning or Q ensembles [Fujimoto et al., 2018b]. For the one-step and multi-step algorithms we train the evaluation procedure to convergence on each iteration and for the iterative algorithm each iteration takes a single stochastic gradient step. See Voloshin et al. [2019], Wang et al. [2021] for more comprehensive examinations of policy evaluation and some evidence that this simple fitted Q iteration approach is reasonable. It is an interesting direction for future work to consider other operators that use things like importance weighting [Munos et al., 2016] or pessimism [Kumar et al., 2020, Buckman et al., 2020].

heading: 4.3 Policy improvement operators

text:
To instantiate the template, we also need to choose a specific policy improvement operator I. We consider the following improvement operators selected from those discussed in the related work section. Each operator has a hyperparameter controlling deviation from the behavior policy.
Behavior cloning. The simplest baseline worth including is to just return β̂ as the new policy π. Any policy improvement operator ought to perform at least as well as this baseline.
Constrained policy updates. Algorithms like BCQ [Fujimoto et al., 2018a] and SPIBB [Laroche et al., 2019] constrain the policy updates to be within the support of the data/behavior. In favor of simplicity, we implement a simplified version of the BCQ algorithm that removes the “perturbation network” which we call Easy BCQ. We define a new policy π̂Mk by drawing M samples from β̂ and then executing the one with the highest value according to Q̂β . Explicitly:
π̂Mk (a|s) = 1[a = argmax aj {Q̂πk−1(s, aj) : aj ∼ πk−1(·|s), 1 ≤ j ≤M}]. (2)
Regularized policy updates. Another common idea proposed in the literature is to regularize towards the behavior policy [Wu et al., 2019, Jaques et al., 2019, Kumar et al., 2019]. For a general divergence D we can define an algorithm that maximizes a regularized objective:
π̂αk = argmax π ∑ i E a∼π|s [Q̂πk−1(si, a)]− αD(β̂(·|si), π(·|si)) (3)
A comprehensive review of different variants of this method can be found in Wu et al. [2019] which does not find dramatic differences across regularization techniques. In practice, we will use reverse KL divergence, i.e. KL(π(·|si)‖β̂(·|si)). To compute the reverse KL, we draw samples from π(·|si) and use the density estimate β̂ to compute the divergence. Intuitively, this regularization forces π to remain within the support of β rather than incentivizing π to cover β.
Variants of imitation learning. Another idea, proposed by [Wang et al., 2018, Siegel et al., 2020, Wang et al., 2020b, Chen et al., 2020] is to modify an imitation learning algorithm either by filtering or weighting the observed actions to incentivize policy improvement. The weighted version that we implement uses exponentiated advantage estimates to weight the observed actions:
π̂τk = argmax π ∑ i exp(τ(Q̂πk−1(si, ai)− V̂ (si))) log π(ai|si). (4)
With these definitions, we can now move on to testing various combinations of algorithmic template (one-step, multi-step, or iterative) and improvement operator (Easy BCQ, reverse KL regularization, or exponentially weighted imitation).

heading: 5 Benchmark Results

text:
Our main empirical finding is that one step of policy improvement is sufficient to beat state of the art results on much of the D4RL benchmark suite [Fu et al., 2020]. This is striking since prior work focuses on iteratively estimating the Q function of the current policy iterate, but we only use one step derived from Q̂β . Results are shown in Table 1. Full experimental details are in Appendix C and code can be found at https://github.com/davidbrandfonbrener/onestep-rl.
As we can see in the table, all of the one-step algorithms usually outperform the best iterative algorithms tested by Fu et al. [2020]. The one notable exception is the case of random data (especially on halfcheetah), where iterative algorithms have a clear advantage. We will discuss potential causes of this further in Section 7. To give a more direct comparison that controls for any potential implementation details, we use our implementation of reverse KL regularization to create multi-step and iterative algorithms. We are not using algorithmic modifications like Q ensembles, regularized Q values, or early stopping that have been used in prior work. But, our iterative algorithm recovers similar performance to prior regularized actor-critic approaches. These results are shown in Table 2.
Put together, these results immediately suggest some guidance to the practitioner: it is worthwhile to run the one-step algorithm as a baseline before trying something more elaborate. The one-step algorithm is substantially simpler than prior work, but frequently achieves better performance.

heading: 6 What goes wrong for iterative algorithms?

text: The benchmark experiments show that one step of policy improvement often beats iterative and multi-step algorithms. In this section we dive deeper to understand why this happens. First, by examining the learning curves of each of the algorithms we note that iterative algorithms require stronger regularization to avoid instability. Then we identify two causes of this instability: distribution shift and iterative error exploitation. Distribution shift causes evaluation error by reducing the effective sample size in the fixed dataset for evaluating the current policy and has been extensively considered in prior work as discussed below. Iterative error exploitation occurs when we repeatedly optimize policies against our Q estimates and exploit their errors. This introduces a bias towards overestimation at each step (much like the training error in supervised learning is biased to be lower than the test error). Moreover, by iteratively re-using the data and using prior Q estimates to warmstart training at each step, the errors from one step are amplified at the next. This type of error is particular to multi-step and iterative algorithms.

heading: 6.1 Learning curves and hyperparameter sensitivity

text:
To begin to understand why iterative and multi-step algorithms can fail it is instructive to look at the learning curves. As shown in Figure 2, we often observe that the iterative algorithm will begin to learn and then crash. Regularization can help to prevent this crash since strong enough regularization towards the behavior policy ensures that the evaluation is nearly on-policy.
In contrast, the one-step algorithm is more robust to the regularization hyperparameter. The rightmost panel of the figure shows this clearly. While iterative and multi-step algorithms can have their performance degrade very rapidly with the wrong setting of the hyperparameter, the one-step approach is more stable. Moreover, we usually find that the optimal setting of the regularization hyperparameter is lower for the one-step algorithm than the iterative or multi-step approaches.

heading: 6.2 Distribution shift

text:
Any algorithm that relies on off-policy evaluation will struggle with distribution shift in the evaluation step. Trying to evaluate a policy that is substantially different from the behavior reduces the effective sample size and increases the variance of the estimates. Explicitly, by distribution shift we mean the shift between the behavior distribution (the distribution over state-action pairs in the dataset) and the evaluation distribution (the distribution that would be induced by the policy π we want to evaluate).
Prior work. There is a substantial body of prior theoretical work that suggests that off-policy evaluation can be difficult and this difficulty scales with some measure of distribution shift. Wang et al. [2020a], Amortila et al. [2020], Zanette [2021] give exponential (in horizon) lower bounds on sample complexity in the linear setting even with good feature representations that can represent the desired Q function and assuming good data coverage. Upper bounds generally require very strong assumptions on both the representation and limits on the distribution shift [Wang et al., 2021, Duan et al., 2020, Chen and Jiang, 2019]. Moreover, the assumed bounds on distribution shift can be exponential in horizon in the worst case. On the empirical side, Wang et al. [2021] demonstrates issues with distribution shift when learning from pre-trained features and provides a nice discussion of why distribution shift causes error amplification. Fujimoto et al. [2018a] raises a similar issue under the name “extrapolation error”. Regularization and constraints are meant to reduce issues stemming from distribution shift, but also reduce the potential for improvement over the behavior.
Empirical evidence. Both the multi-step and iterative algorithms in our experiments rely on offpolicy evaluation as a key subroutine. We examine how easy it is to evaluate the policies encountered along the learning trajectory. To control for issues of iterative error exploitation (discussed in the next subsection), we train Q estimators from scratch on a heldout evaluation dataset sampled from the behavior policy. We then evaluate these trained Q function on rollouts from 1000 datapoints sampled from the replay buffer. Results are shown in Figure 3. The results show a correlation betweed KL and MSE. Moreover, we see that the MSE generally increases over training. One way to mitigate this, as seen in the figure, is to use a large value of α. We just cannot take a very large step before running into problems with distribution shift. But, when we take such a small step, the information from the on-policy Q̂β is about as useful as the newly estimated Q̂π. This is seen, for example, in Figure 2 where we get very similar performance across algorithms at high levels of regularization.

heading: 6.3 Iterative error exploitation

text:
The previous subsection identifies how any algorithm that uses off-policy evaluation is fundamentally limited by distribution shift, even if we were given fresh data and trained Q functions from scratch at every iteration. But, in practice, iterative algorithms repeatedly iterate between optimizing policies against estimated Q functions and re-estimating the Q functions using the same data and using the Q function from the previous step to warm-start the re-estimation. This induces dependence between steps that causes a problem that we call iterative error exploitation.
Intuition about the problem. In short, iterative error exploitation happens because πi tends to choose overestimated actions in the policy improvement step, and then this overestimation propagates via dynamic programming in the policy evaluation step. To illustrate this issue more formally, consider the following: at each s, a we suffer some Bellman error επβ(s, a) based on our fixed dataset collected by β. Formally,
Q̂π(s, a) = r(s, a) + γ E s′|s,a a′∼π|s′ [Q̂π(s′, a′)] + επβ(s, a). (5)
Intuitively, επβ will be larger at state-actions with less coverage in the dataset collected by β. Note that επβ can absorb all error whether it is caused by the finite sample size or function approximation error.
All that is needed to cause iterative error exploitation is that the πβ are highly correlated across different π, but for simplicity, we will assume that επβ is the same for all policies π estimated from our fixed offline dataset and instead write εβ . Now that the errors do not depend on the policy we can treat the errors as auxiliary rewards that obscure the true rewards and see that
Q̂π(s, a) = Qπ(s, a) + Q̃πβ(s, a), Q̃ π β(s, a) := E
π|s0,a0=s,a [ ∞∑ t=0 γtεβ(st, at) ] . (6)
This assumption is somewhat reasonable since we expect the error to primarily depend on the data. And, when the prior Q function is used to warm-start the current one (as is generally the case in practice), the approximation errors are automatically passed between steps. Now we can explain the problem. Recall that under our assumption the εβ are fixed once we have a dataset and likely to have larger magnitude the further we go from the support of the dataset. So, with each step πi is able to better maximize εβ , thus moving further from β and increasing the magnitude of Q̃πiβ relative to Q πi . Even though Qπi may provide better signal than Qβ , it can easily be drowned out by Q̃πiβ . In contrast, Q̃ β β has small magnitude, so the one-step algorithm is robust to errors 1.
An example. Now we consider a simple gridworld example to illustrate iterative error exploitation. This example fits exactly into the setup outlined above since all errors are due to reward estimation so the εβ is indeed constant over all π. The gridworld we consider has one deterministic good state with reward 1 and many stochastic bad states that have rewards distributed as N (−0.5, 1). We collect a dataset of 100 trajectories, each of length 100. One run of the multi-step offline regularized policy iteration algorithm is illustrated in Figure 4. In the example we see that one step often outperforms multiple steps of improvement. Intuitively, when there are so many noisy states, it is likely that a few of them will be overestimated. Since the data is re-used for each step, these overestimations persist and propagate across the state space due to iterative error exploitation. This property of having many bad, but poorly estimated states likely also exists in the high-dimensional control problems encountered in the benchmark where there are many ways for the robots to fall down that are not observed in the data for non-random behavior. Moreover, both settings have larger errors in areas where we have less data. So even though the errors in the gridworld are caused by noise in the rewards, while errors in D4RL are caused by function approximation, we think this is a useful mental model of the problem.
1We should note that iterative error exploitation is similar to the overestimation addressed by double Q learning [Van Hasselt et al., 2016, Fujimoto et al., 2018b], but distinct. Since we are in the offline setting, the errors due to our finite dataset can be iteratively exploited more and more, while in the online setting considered by double Q learning, fresh data prevents this issue. We are also considering an algorithm based on policy iteration rather than value iteration.
Empirical evidence. In practice we cannot easily visualize the progression of errors. However, the dependence between steps still arises as overestimation of the Q values. We can track the overestimation of the Q values over training as a way to measure how much bias is being induced by optimizing against our dependent Q estimators. As a control we can also train Q estimators from scratch on independently sampled evaluation data. These independently trained Q functions do not have the same overestimation bias even though the squared error does tend to increase as the policy moves further from the behavior (as seen in Figure 3). Explicitly, we track 1000 state, action pairs from the replay buffer over training. For each checkpointed policy we perform 3 rollouts at each state to get an estimate of the true Q value and compare this to the estimated Q value. Results are shown in Figure 5.

heading: 7 When are multiple steps useful?

text:
So far we have focused on why the one-step algorithm often works better than the multi-step and iterative algorithms. However, we do not want to give the impression that one-step is always better. Indeed, our own experiments in Section 5 show a clear advantage for the multi-step and iterative approaches when we have randomly collected data. While we cannot offer a precise delineation of when one-step will outperform multi-step, in this section we offer some intuition as to when we can expect to see benefits from multiple steps of policy improvement. As seen in Section 6, multi-step and iterative algorithms have problems when they propagate estimation errors. This is especially problematic in noisy and/or high dimensional environments. While the multi-step algorithms propagate this noise more widely than the one-step algorithm, they also
propagate the signal. So, when we have sufficient coverage to reduce the magnitude of the noise, this increased propagation of signal can be beneficial. The D4RL experiments suggest that we are usually on the side of the tradeoff where the errors are large enough to make one-step preferable. In Appendix A we illustrate a simple gridworld example where a slight modification of the behavior policy from Figure 4 makes multi-step dramatically outperform one-step. This modified behavior policy (1) has better coverage of the noisy states (which reduces error, helping multi-step), and (2) does a worse job propagating the reward from the good state (hurting one-step). We can also test empirically how the behavior policy effects the tradeoff between error and signal propagation. To do this we construct a simple experiment where we mix data from the random behavior policy with data from the medium behavior policy. Explicitly we construct a dataset D out of the datasets Dr for random and Dm for medium such that each trajectory in D comes from the medium dataset with probability pm. So for pm = 0 we have the random dataset and pm = 1 we have the medium dataset, and in between we have various mixtures. Results are shown in Figure 6. It takes surprisingly little data from the medium policy for one-step to outperform the iterative algorithm.

heading: 8 Discussion, limitations, and future work

text:
This paper presents the surprising effectiveness of a simple one-step baseline for offline RL. We examine the failure modes of iterative algorithms and the conditions where we might expect them to outperform the simple one-step baseline. This provides guidance to a practitioner that the simple one-step baseline is a good place to start when approaching an offline RL problem. But, we leave many questions unanswered. One main limitation is that we lack a clear theoretical characterization of which environments and behaviors can guarantee that one-step outperforms multi-step or visa versa. Such results will likely require strong assumptions, but could provide useful insight. We don’t expect this to be easy as it requires understanding policy iteration which has been notoriously difficult to analyze, often converging much faster than the theory would suggest [Sutton and Barto, 2018, Agarwal et al., 2019]. Another limitation is that while only using one step is perhaps the simplest way to avoid the problems of off-policy evaluation, there are possibly other more elaborate algorithmic solutions that we did not consider here. However, our strong empirical results suggest that the one-step algorithm is at least a strong baseline.
Broader impact. Our paper studies a simple and effective baseline approach to the offline RL problem. The effectiveness of this baseline raises some serious questions about the utility of prior work proposing substantially more complicated methods. By making this observation of prior shortcomings, our paper has the potential to encourage researchers to derive new and better methods for offline RL. This has many potential impacts on fields as diverse as robotics and healthcare where better offline decision making can lead to better real-world performance. As always, we note that machine learning improvements come in the form of “building machines to do X better”. For a sufficiently malicious or ill-informed choice of X, almost any progress in machine learning might indirectly lead to a negative outcome, and our work is not excluded from that.

heading: Acknowledgements

text: This work is partially supported by the Alfred P. Sloan Foundation, NSF RI-1816753, NSF CAREER CIF 1845360, NSF CHS-1901091, Samsung Electronics, and the Institute for Advanced Study. DB is supported by the Department of Defense (DoD) through the National Defense Science & Engineering Graduate Fellowship (NDSEG) Program.

title: Offline RL Without Off-Policy Evaluation