summaries: This paper introduces a method  to perform text-image matching and demonstrate that  it can be used to solve several language-vision downstream tasks  ranging from image-text retrieval, VQA and national language for visual reasoning among others.   * Given an  image and a textual input visual and  textual embedding are obtained  that are then fed  to a multimodal encoder with  cross-attention layers.  * The first key idea of this paper lies in the image-text contrastive loss employed between the image/text embeddings before feeding them to the multimodal  decoder with the intuition behind that being that forcing these embeddings to align before fusing them through the multi-modal encoder results into better representations for downstream tasks * The second key idea is in the usage of  a momentum model that generates pseudo-target labels by keeping a moving average that are then used for supervision at training time.   An in-depth discussion is provided: 1) for each of the losses used, 2) on the fact that the proposed approach maximizes a lower bound on the mutual information between different “views” of an image-text pair  Extensive Results for several tasks and datasets are provided and strong results are reported. The qualitative results demonstrating where the learned attention is focusing for each downstream task are also quite insightful

summaries: This paper proposes a new vision-language representation learning framework, ALBEF, which uses image-text contrastive (ITC), masked language modeling (MLM), and image-text matching (ITM) losses with momentum distillation to learn SOTA representations. The ITC and MLM losses are adapted to be convex combinations of the original loss and the KL divergence between the predicted probability distribution (of the image or text or masked tokens) and the soft pseudo targets obtained from the momentum model.   The pipeline is evaluated on image-text retrieval, visual entailment, NLVR, VQA, and grounding and shows improved performance on all tasks compared to prior work, and with fewer training samples in comparison to several prior methods. Qualitative visualizations also verify the quality of the learned representations, with convincing heat maps suggesting well grounded, semantically aligned embeddings.

summaries: This paper presents an vision-and-language pretraining framework that utilizes momentum distillation to address the issue of training on noisy web data. More specifically, it presents a self-training approach to learn from pseudo-targets that are generated by a momentum model. In contrast to existing approaches which simply use cross-modal attention to reason about concatenated sequences of image regions and words, this work also leverages contrastive learning to learn more effective representations before using cross-modal attention.

summaries: The paper proposes to learn joint vision and language representations by addressing several limitations in the existing methods. Firstly, they learn separate image and text representations using unimodal encoders without the need for bounding box annotations. Second, they fuse these two representations using a multimodal encoder based on cross modal attention and, third, they address the noise in large scale web based image-text datasets using a Momentum Distillation approach that generates pseudo-targets as additional supervision. They demonstrate the effectiveness of their approach on various downstream V+L tasks and gain substantial improvement over SOTA methods. Their main contributions are: removing the need for pre-trained object detector and high resolution images and combining it with the contrastive loss function for learning effective multi-modal representations, image-text contrastive learning loss (ITC). They also generate pseudo-targets for the ITC loss and the masked language modeling (MLM) loss using the momentum encoder model to address the weak correlations in the noisy image-text web data. This achieves high performance on both reasoning and retrieval tasks unlike other methods. The paper  is very well written and easy to follow and understand.

summaries: In this paper, the authors study the vision-transformer-like vision-language-pretraining (VLP) methods. The raw image and text are first encoded by a vision transformer and a text transformer respectively, and are then sent into a multimodal transformer for fusion. There are two major technical contributions, i.e., 1) the proposed ITC loss and 2) the moving average “teacher” to generate the pseudo targets.     The proposed method (ALBEF) outperforms previous E2E VLP methods, and achieves comparable performance to the VLP methods that take object region features.

abstractText: Large-scale vision and language representation learning has shown promising improvements on various vision-language tasks. Most existing methods employ a transformer-based multimodal encoder to jointly model visual tokens (region-based image features) and word tokens. Because the visual tokens and word tokens are unaligned, it is challenging for the multimodal encoder to learn image-text interactions. In this paper, we introduce a contrastive loss to ALign the image and text representations BEfore Fusing (ALBEF) them through cross-modal attention, which enables more grounded vision and language representation learning. Unlike most existing methods, our method does not require bounding box annotations nor high-resolution images. To improve learning from noisy web data, we propose momentum distillation, a self-training method which learns from pseudo-targets produced by a momentum model. We provide a theoretical analysis of ALBEF from a mutual information maximization perspective, showing that different training tasks can be interpreted as different ways to generate views for an image-text pair. ALBEF achieves state-of-the-art performance on multiple downstream visionlanguage tasks. On image-text retrieval, ALBEF outperforms methods that are pre-trained on orders of magnitude larger datasets. On VQA and NLVR2, ALBEF achieves absolute improvements of 2.37% and 3.84% compared to the state-ofthe-art, while enjoying faster inference speed. Code and models are available at https://github.com/salesforce/ALBEF.

authors:
H. Tan
M. Bansal

title: LXMERT: learning cross-modality encoder representations from transformers

authors:
Y. Chen
L. Li
L. Yu

title: UNITER: universal image-text representation learning

venue: In ECCV,

authors:
X. Li
X. Yin
C. Li

title: Oscar: Object-semantics aligned pre-training for vision-language tasks

authors:
P. Sharma
N. Ding
S. Goodman

title: Conceptual captions: A cleaned, hypernymed, image alt-text dataset for automatic image captioning

authors:
V. Ordonez
G. Kulkarni
T.L. Berg

title: Im2text: Describing images using 1 million captioned photographs

authors:
A. Radford
J.W. Kim
C. Hallacy

title: Learning transferable visual models from natural language supervision

venue: arXiv preprint arXiv:2103.00020,

authors:
C. Jia
Y. Yang
Y. Xia

title: Scaling up visual and vision-language representation learning with noisy text supervision

venue: arXiv preprint arXiv:2102.05918,

authors:
Z. Gan
Y. Chen
L. Li

title: Large-scale adversarial training for vision-and-language representation learning

authors:
R.R. Selvaraju
M. Cogswell
A. Das

title: Grad-cam: Visual explanations from deep networks via gradient-based localization

venue: In ICCV,

authors:
W. Su
X. Zhu
Y. Cao

title: Vl-bert: Pre-training of generic visual-linguistic representations

venue: In ICLR

authors:
J. Lu
D. Batra
D. Parikh

title: Vilbert: Pretraining task-agnostic visiolinguistic representations for vision-and-language tasks

authors:
J. Lu
V. Goswami
M. Rohrbach

title: 12-in-1: Multi-task vision and language representation learning

venue: In CVPR,

authors:
L.H. Li
M. Yatskar
D. Yin

title: Visualbert: A simple and performant baseline for vision and language

venue: arXiv preprint arXiv:1908.03557,

authors:
D. Qi
L. Su
J. Song

title: Imagebert: Cross-modal pre-training with large-scale weaksupervised image-text data

venue: arXiv preprint arXiv:2001.07966,

authors:
G. Li
N. Duan
Y. Fang

title: Unicoder-vl: A universal encoder for vision and language by cross-modal pre-training

venue: In AAAI,

authors:
F. Yu
J. Tang
W. Yin

title: Ernie-vil: Knowledge enhanced vision-language representations through scene graph

venue: arXiv preprint arXiv:2006.16934,

authors:
P. Zhang
X. Li
X. Hu

title: Vinvl: Making visual representations matter in vision-language models

venue: arXiv preprint arXiv:2101.00529,

authors:
Z. Huang
Z. Zeng
Y. Huang

title: Seeing out of the box: End-to-end pre-training for vision-language representation learning

venue: arXiv preprint arXiv:2104.03135,

authors:
A. Suhr
S. Zhou
A. Zhang

title: A corpus for reasoning about natural language grounded in photographs

authors:
S. Antol
A. Agrawal
J. Lu

title: VQA: visual question answering

authors:
W. Kim
B. Son
I. Kim

title: Vilt: Vision-and-language transformer without convolution or region supervision

venue: arXiv preprint arXiv:2102.03334,

authors:
F. Faghri
D.J. Fleet
J.R. Kiros

title: VSE++: improving visual-semantic embeddings with hard negatives

venue: In BMVC,

authors:
K. Li
Y. Zhang

title: Visual semantic reasoning for image-text matching

authors:
K. He
H. Fan
Y. Wu

title: Momentum contrast for unsupervised visual representation learning

venue: In CVPR

authors:
T. Chen
S. Kornblith
M. Norouzi

title: A simple framework for contrastive learning of visual representations

venue: In ICML

authors:
J. Li
P. Zhou
C. Xiong

title: Prototypical contrastive learning of unsupervised representations

authors:
J. Li
C. Xiong
S.C. Hoi

title: Mopro: Webly supervised learning with momentum prototypes

authors:
G. Hinton
O. Vinyals
J. Dean

title: Distilling the knowledge in a neural network

venue: arXiv preprint arXiv:1503.02531,

authors:
S. Zagoruyko
N. Komodakis

title: Paying more attention to attention: Improving the performance of convolutional neural networks via attention transfer

authors:
T. Furlanello
Z.C. Lipton
M. Tschannen

title: Born-again neural networks

authors:
H. Touvron
M. Cord
M. Douze

title: Training data-efficient image transformers & distillation through attention

venue: arXiv preprint arXiv:2012.12877,

authors:
V. Sanh
L. Debut
J. Chaumond

title: Distilbert, a distilled version of bert: smaller, faster, cheaper and lighter

authors:
Y. Zhang
T. Xiang
T.M. Hospedales

title: Deep mutual learning

authors:
R. Anil
G. Pereyra
A. Passos

title: Large scale distributed neural network training through online distillation

authors:
A. Tarvainen
H. Valpola

title: Mean teachers are better role models: Weight-averaged consistency targets improve semi-supervised deep learning results

venue: In NIPS,

authors:
J. Li
R. Socher
S.C. Hoi

title: Dividemix: Learning with noisy labels as semi-supervised learning

authors:
R. Cheng
B. Wu
P. Zhang

title: Data-efficient language-supervised zero-shot learning with self-distillation

venue: arXiv preprint arXiv:2104.08945,

authors:
A. Dosovitskiy
L. Beyer
A. Kolesnikov

title: An image is worth 16x16 words: Transformers for image recognition at scale

authors:
A. Vaswani
N. Shazeer
N. Parmar

title: Attention is all you need

authors:
J. Devlin
M. Chang
K. Lee

title: BERT: pre-training of deep bidirectional transformers for language understanding

authors:
T. Lin
M. Maire
S.J. Belongie

title: Microsoft COCO: common objects in context

venue: eds., ECCV,

authors:
R. Krishna
Y. Zhu
O. Groth

title: Visual genome: Connecting language and vision using crowdsourced dense image

venue: annotations. IJCV,

authors:
S. Changpinyo
P. Sharma
N. Ding

title: Conceptual 12M: Pushing web-scale image-text pre-training to recognize long-tail visual concepts

authors:
I. Loshchilov
F. Hutter

title: Decoupled weight decay regularization

venue: arXiv preprint arXiv:1711.05101,

authors:
E.D. Cubuk
B. Zoph
J. Shlens

title: Randaugment: Practical automated data augmentation with a reduced search space

venue: In CVPR Workshops,

authors:
Y. Tian
C. Sun
B. Poole

title: What makes for good views for contrastive learning

authors:
Oord
A. v. d
Y. Li
O. Vinyals

title: Representation learning with contrastive predictive coding

venue: arXiv preprint arXiv:1807.03748,

authors:
L. Kong
C. de Masson d’Autume
L. Yu

title: A mutual information maximization perspective of language representation learning

venue: In ICLR. OpenReview.net,

authors:
B.A. Plummer
L. Wang
C.M. Cervantes

title: Flickr30k entities: Collecting region-to-phrase correspondences for richer image-to-sentence models

authors:
V. Do
O.-M. Camburu
Z. Akata

title: e-snli-ve: Corrected visual-textual entailment with natural language explanations

venue: arXiv preprint arXiv:2004.03744,

authors:
N. Xie
F. Lai
D. Doran

title: Visual entailment: A novel task for fine-grained image understanding

venue: arXiv preprint arXiv:1901.06706,

authors:
Y. Goyal
T. Khot
D. Summers-Stay

title: Making the V in VQA matter: Elevating the role of image understanding in visual question answering

authors:
L. Yu
Z. Lin
X. Shen

title: Mattnet: Modular attention network for referring expression comprehension

authors:
J. Cho
J. Lei
H. Tan

title: Unifying vision-and-language tasks via text generation

venue: arXiv preprint arXiv:2102.02779,

authors:
J. Kim
J. Jun
B. Zhang

title: Bilinear attention networks

authors:
L. Yu
P. Poirson
S. Yang

title: Modeling context in referring expressions

authors:
X. Liu
L. Li
S. Wang

title: Adaptive reconstruction network for weakly supervised referring expression grounding

title: Counterfactual contrastive learning fo weakly-supervised vision-language grounding

title: Deep visual-semantic alignments for generating image descriptions

title: A large annotated corpus for learning natural language inference

title: Deep modular co-attention networks for visual question answering

title: Referitgame: Referring to objects in photographs of natural scenes

title: Human Attention in Visual Question Answering: Do Humans and Deep Networks Look at the Same Regions? 2016

heading: 1 Introduction

text:
Vision-and-Language Pre-training (VLP) aims to learn multimodal representations from large-scale image-text pairs that can improve downstream Vision-and-Language (V+L) tasks. Most existing VLP methods (e.g. LXMERT [1], UNITER [2], OSCAR [3]) rely on pre-trained object detectors to extract region-based image features, and employ a multimodal encoder to fuse the image features with word tokens. The multimodal encoder is trained to solve tasks that require joint understanding of image and text, such as masked language modeling (MLM) and image-text matching (ITM).
While effective, this VLP framework suffers from several key limitations: (1) The image features and the word token embeddings reside in their own spaces, which makes it challenging for the multimodal encoder to learn to model their interactions; (2) The object detector is both annotation-expensive and compute-expensive, because it requires bounding box annotations during pre-training, and highresolution (e.g. 600⇥1000) images during inference; (3) The widely used image-text datasets [4, 5] are collected from the web and are inherently noisy, and existing pre-training objectives such as MLM may overfit to the noisy text and degrade the model’s generalization performance.
We propose ALign BEfore Fuse (ALBEF), a new VLP framework to address these limitations. We first encode the image and text independently with a detector-free image encoder and a text encoder. Then we use a multimodal encoder to fuse the image features with the text features through crossmodal attention. We introduce an intermediate image-text contrastive (ITC) loss on representations from the unimodal encoders, which serves three purposes: (1) it aligns the image features and the text features, making it easier for the multimodal encoder to perform cross-modal learning; (2) it
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
improves the unimodal encoders to better understand the semantic meaning of images and texts; (3) it learns a common low-dimensional space to embed images and texts, which enables the image-text matching objective to find more informative samples through our contrastive hard negative mining.
To improve learning under noisy supervision, we propose Momentum Distillation (MoD), a simple method which enables the model to leverage a larger uncurated web dataset. During training, we keep a momentum version of the model by taking the moving-average of its parameters, and use the momentum model to generate pseudo-targets as additional supervision. With MoD, the model is not penalized for producing other reasonable outputs that are different from the web annotation. We show that MoD not only improves pre-training, but also downstream tasks with clean annotations.
We provide theoretical justifications on ALBEF from the perspective of mutual information maximization. Specifically, we show that ITC and MLM maximize a lower bound on the mutual information between different views of an image-text pair, where the views are generated by taking partial information from each pair. From this perspective, our momentum distillation can be interpreted as generating new views with semantically similar samples. Therefore, ALBEF learns vision-language representations that are invariant to semantic-preserving transformations.
We demonstrate the effectiveness of ALBEF on various downstream V+L tasks including image-text retrieval, visual question answering, visual reasoning, visual entailment, and weakly-supervised visual grounding. ALBEF achieves substantial improvements over existing state-of-the-art methods. On image-text retrieval, it outperforms methods that are pre-trained on orders of magnitude larger datasets (CLIP [6] and ALIGN [7]). On VQA and NLVR2, it achieves absolute improvements of 2.37% and 3.84% compared to the state-of-the-art method VILLA [8], while enjoying much faster inference speed. We also provide quantitative and qualitative analysis on ALBEF using Grad-CAM [9], which reveals its ability to perform accurate object, attribute and relationship grounding implicitly.

heading: 2 Related Work

heading: 2.1 Vision-Language Representation Learning

text:
Most existing work on vision-language representation learning fall into two categories. The first category focuses on modelling the interactions between image and text features with transformerbased multimodal encoders [10, 11, 12, 13, 1, 14, 15, 2, 3, 16, 8, 17, 18]. Methods in this category achieve superior performance on downstream V+L tasks that require complex reasoning over image and text (e.g. NLVR2 [19], VQA [20]), but most of them require high-resolution input images and pre-trained object detectors. A recent method [21] improves inference speed by removing the object detector, but results in lower performance. The second category focuses on learning separate unimodal encoders for image and text [22, 23, 6, 7]. The recent CLIP [6] and ALIGN [7] perform pre-training on massive noisy web data using a contrastive loss, one of the most effective loss for representation learning [24, 25, 26, 27]. They achieve remarkable performance on image-text retrieval tasks, but lack the ability to model more complex interactions between image and text for other V+L tasks [21].
ALBEF unifies the two categories, leading to strong unimodal and multimodal representations with superior performance on both retrieval and reasoning tasks. Furthermore, ALBEF does not require object detectors, a major computation bottleneck for many existing methods [1, 2, 3, 8, 17].

heading: 2.2 Knowledge Distillation

text: Knowledge distillation [28] aims to improve a student model’s performance by distilling knowledge from a teacher model, usually through matching the student’s prediction with the teacher’s. While most methods focus on distilling knowledge from a pre-trained teacher model [28, 29, 30, 31, 32], online distillation [33, 34] simultaneously trains multiple models and use their ensemble as the teacher. Our momentum distillation can be interpreted as a form of online self-distillation, where a temporal ensemble of the student model is used as the teacher. Similar ideas have been explored in semi-supervised learning [35], label noise learning [36], and very recently in contrastive learning [37]. Different from existing studies, we theoretically and experimentally show that momentum distillation is a generic learning algorithm that can improve the model’s performance on many V+L tasks.

heading: 3 ALBEF Pre-training

text: In this section, we first introduce the model architecture (Section 3.1). Then we delineate the pretraining objectives (Section 3.2), followed by the proposed momentum distillation (Section 3.3). Lastly we describe the pre-training datasets (Section 3.4) and implementation details (Section 3.5).

heading: 3.1 Model Architecture

text: As illustrated in Figure 1, ALBEF contains an image encoder, a text encoder, and a multimodal encoder. We use a 12-layer visual transformer ViT-B/16 [38] as the image encoder, and initialize it with weights pre-trained on ImageNet-1k from [31]. An input image I is encoded into a sequence of embeddings: {vcls,v1, ...,vN}, where vcls is the embedding of the [CLS] token. We use a 6-layer transformer [39] for both the text encoder and the multimodal encoder. The text encoder is initialized using the first 6 layers of the BERTbase [40] model, and the multimodal encoder is initialized using the last 6 layers of the BERTbase. The text encoder transforms an input text T into a sequence of embeddings {wcls,w1, ...,wN}, which is fed to the multimodal encoder. The image features are fused with the text features through cross attention at each layer of the multimodal encoder.

heading: 3.2 Pre-training Objectives

text:
We pre-train ALBEF with three objectives: image-text contrastive learning (ITC) on the unimodal encoders, masked language modeling (MLM) and image-text matching (ITM) on the multimodal encoder. We improve ITM with online contrastive hard negative mining.
Image-Text Contrastive Learning aims to learn better unimodal representations before fusion. It learns a similarity function s = gv(vcls)>gw(wcls), such that parallel image-text pairs have higher similarity scores. gv and gw are linear transformations that map the [CLS] embeddings to normalized lower-dimensional (256-d) representations. Inspired by MoCo [24], we maintain two queues to store the most recent M image-text representations from the momentum unimodal encoders. The normalized features from the momentum encoders are denoted as g0v(v0cls) and g 0 w(w 0 cls). We define s(I, T ) = gv(vcls)>g0w(w 0 cls) and s(T, I) = gw(wcls) >g0v(v 0 cls).
For each image and text, we calculate the softmax-normalized image-to-text and text-to-image similarity as:
pi2tm (I) = exp(s(I, Tm)/⌧)PM
m=1 exp(s(I, Tm)/⌧) , pt2im (T ) = exp(s(T, Im)/⌧)PM m=1 exp(s(T, Im)/⌧)
(1)
where ⌧ is a learnable temperature parameter. Let yi2t(I) and yt2i(T ) denote the ground-truth one-hot similarity, where negative pairs have a probability of 0 and the positive pair has a probability of 1. The image-text contrastive loss is defined as the cross-entropy H between p and y:
Litc = 1
2 E(I,T )⇠D
⇥ H(yi2t(I),pi2t(I)) + H(yt2i(T ),pt2i(T )) ⇤ (2)
Masked Language Modeling utilizes both the image and the contextual text to predict the masked words. We randomly mask out the input tokens with a probability of 15% and replace them with the special token [MASK]1. Let T̂ denote a masked text, and pmsk(I, T̂ ) denote the model’s predicted probability for a masked token. MLM minimizes a cross-entropy loss:
Lmlm = E(I,T̂ )⇠DH(y msk,pmsk(I, T̂ )) (3)
where ymsk is a one-hot vocabulary distribution where the ground-truth token has a probability of 1.
Image-Text Matching predicts whether a pair of image and text is positive (matched) or negative (not matched). We use the multimodal encoder’s output embedding of the [CLS] token as the joint representation of the image-text pair, and append a fully-connected (FC) layer followed by softmax to predict a two-class probability pitm. The ITM loss is:
Litm = E(I,T )⇠DH(yitm,pitm(I, T )) (4) where yitm is a 2-dimensional one-hot vector representing the ground-truth label.
We propose a strategy to sample hard negatives for the ITM task with zero computational overhead. A negative image-text pair is hard if they share similar semantics but differ in fine-grained details. We use the contrastive similarity from Equation 1 to find in-batch hard negatives. For each image in a mini-batch, we sample one negative text from the same batch following the contrastive similarity distribution, where texts that are more similar to the image have a higher chance to be sampled. Likewise, we also sample one hard negative image for each text.
The full pre-training objective of ALBEF is: L = Litc + Lmlm + Litm (5)

heading: 3.3 Momentum Distillation

text:
The image-text pairs used for pre-training are mostly collected from the web and they tend to be noisy. Positive pairs are usually weakly-correlated: the text may contain words that are unrelated to the image, or the image may contain entities that are not described in the text. For ITC learning, negative texts for an image may also match the image’s content. For MLM, there may exist other words different from the annotation that describes the image equally well (or better). However, the one-hot labels for ITC and MLM penalize all negative predictions regardless of their correctness.
To address this, we propose to learn from pseudo-targets generated by the momentum model. The momentum model is a continuously-evolving teacher which consists of exponential-moving-average versions of the unimodal and multimodal encoders. During training, we train the base model such that its predictions match the ones from the momentum model. Specifically, for ITC, we first compute the image-text similarity using features from the momentum unimodal encoders as s0(I, T ) = g0v(v 0 cls) >g0w(w 0 cls) and s 0 (T, I) = g0w(wcls) >g0v(v 0 cls). Then we compute soft pseudotargets qi2t and qt2i by replacing s with s0 in Equation 1. The ITCMoD loss is defined as:
Lmoditc = (1 ↵)Litc + ↵
2 E(I,T )⇠D
⇥ KL(qi2t(I) k pi2t(I)) + KL(qt2i(T ) k pt2i(T )) ⇤ (6)
1following BERT, the replacements are 10% random tokens, 10% unchanged, and 80% [MASK]
Similarly, for MLM, let qmsk(I, T̂ ) denote the momentum model’s prediction probability for the masked token, the MLMMoD loss is:
Lmodmlm = (1 ↵)Lmlm + ↵E(I,T̂ )⇠DKL(q msk (I, T̂ ) k pmsk(I, T̂ )) (7) In Figure 2, we show examples of the top-5 candidates from the pseudo-targets, which effectively capture relevant words/texts for an image. More examples can be found in Appendix.
We also apply MoD to the downstream tasks. The final loss for each task is a weighted combination of the original task’s loss and the KL-divergence between the model’s prediction and the pseudo-targets. For simplicity, we set the weight ↵ = 0.4 for all pre-training and downstream tasks 2.

heading: 3.4 Pre-training Datasets

text: Following UNITER [2], we construct our pre-training data using two web datasets (Conceptual Captions [4], SBU Captions [5]) and two in-domain datasets (COCO [41] and Visual Genome [42]). The total number of unique images is 4.0M, and the number of image-text pairs is 5.1M. To show that our method is scalable with larger-scale web data, we also include the much noisier Conceptual 12M dataset [43], increasing the total number of images to 14.1M 3. Details are in Appendix.

heading: 3.5 Implementation Details

text: Our model consists of a BERTbase with 123.7M parameters and a ViT-B/16 with 85.8M parameters. We pre-train the model for 30 epochs using a batch size of 512 on 8 NVIDIA A100 GPUs. We use the AdamW [44] optimizer with a weight decay of 0.02. The learning rate is warmed-up to 1e 4 in the first 1000 iterations, and decayed to 1e 5 following a cosine schedule. During pre-training, we take random image crops of resolution 256⇥ 256 as input, and also apply RandAugment4 [45]. During fine-tuning, we increase the image resolution to 384⇥ 384 and interpolate the positional encoding of image patches following [38]. The momentum parameter for updating the momentum model is set as 0.995, and the size of the queue used for image-text contrastive learning is set as 65,536. We linearly ramp-up the distillation weight ↵ from 0 to 0.4 within the 1st epoch.

heading: 4 A Mutual Information Maximization Perspective

text:
In this section, we provide an alternative perspective of ALBEF and show that it maximizes a lower bound on the mutual information (MI) between different “views” of an image-text pair. ITC, MLM, and MoD can be interpreted as different ways to generate the views.
Formally, we define two random variables a and b as two different views of a data point. In selfsupervised learning [24, 25, 46], a and b are two augmentations of the same image. In vision-language representation learning, we consider a and b as different variations of an image-text pair that capture its semantic meaning. We aim to learn representations invariant to the change of view. This can be achieved by maximizing the MI between a and b. In practice, we maximize a lower bound on MI(a, b) by minimizing the InfoNCE loss [47] defined as:
LNCE = Ep(a,b)
" log exp(s(a, b)) P
b̂2B̂ exp(s(a, b̂))
# (8)
where s(a, b) is a scoring function (e.g., a dot product between two representations), and B̂ contains the positive sample b and |B̂| 1 negative samples drawn from a proposal distribution. Our ITC loss with one-hot labels (Equation 2) can be re-written as:
Litc = 1
2 Ep(I,T )
⇥ log exp(s(I, T )/⌧) PM
m=1 exp(s(I, Tm)/⌧) + log
exp(s(T, I)/⌧) PM
m=1 exp(s(T, Im)/⌧)
⇤ (9)
Minimizing Litc can be seen as maximizing a symmetric version of InfoNCE. Hence, ITC considers the two individual modalities (i.e., I and T ) as the two views of an image-text pair, and trains the unimodal encoders to maximize the MI between the image and text views for the positive pairs.
2our experiments show that ↵ = 0.3, 0.4, 0.5 yield similar performance, with ↵ = 0.4 slightly better 3some urls provided by the web datasets have become invalid 4we remove color changes from RandAugment because the text often contains color information
As shown in [48], we can also interpret MLM as maximizing the MI between a masked word token and its masked context (i.e. image + masked text). Specifically, we can re-write the MLM loss with one-hot labels (Equation 3) as
Lmlm = Ep(I,T̂ ) ⇥ log exp( (ymsk)>f(I, T̂ )) P
y2V exp( (y) >f(I, T̂ ))
⇤ (10)
where (y) : V ! Rd is a lookup function in the multimodal encoder’s output layer that maps a word token y into a vector and V is the full vocabulary set, and f(I, T̂ ) is a function that returns the final hidden state of the multimodal encoder corresponding to the masked context. Hence, MLM considers the two views of an image-text pair to be: (1) a randomly selected word token, and (2) the image + the contextual text with that word masked.
Both ITC and MLM generate views by taking partial information from an image-text pair, through either modality separation or word masking. Our momentum distillation can be considered as generating alternative views from the entire proposal distribution. Take ITCMoD in Equation 6 as an example, minimizing KL(pi2t(I), qi2t(I)) is equivalent to minimizing the following objective:
X
m
qi2tm (I) log p i2t m (I) =
X
m exp(s0(I, Tm)/⌧)PM m=1 exp(s 0(I, Tm)/⌧) log exp(s(I, Tm)/⌧)PM m=1 exp(s(I, Tm)/⌧) (11)
It maximizes MI(I, Tm) for texts that share similar semantic meaning with the image I because those texts would have larger qi2tm (I). Similarly, ITCMoD also maximizes MI(Im, T ) for images that are similar to T . We can follow the same method to show that MLMMoD generates alternative views y0 2 V for the masked word ymsk, and maximizes the MI between y0 and (I, T̂ ). Therefore, our momentum distillation can be considered as performing data augmentation to the original views. The momentum model generates a diverse set of views that are absent in the original image-text pairs, and encourages the base model to learn representations that capture view-invariant semantic information.

heading: 5 Downstream V+L Tasks

text:
We adapt the pre-trained model to five downstream V+L tasks. We introduce each task and our fine-tuning strategy below. Details of the datasets and fine-tuning hyperparameters are in Appendix.
Image-Text Retrieval contains two subtasks: image-to-text retrieval (TR) and text-to-image retrieval (IR). We evaluate ALBEF on the Flickr30K [49] and COCO benchmarks, and fine-tune the pretrained model using the training samples from each dataset. For zero-shot retrieval on Flickr30K, we evaluate with the model fine-tuned on COCO. During fine-tuning, we jointly optimize the ITC loss (Equation 2) and the ITM loss (Equation 4). ITC learns an image-text scoring function based on similarity of unimodal features, whereas ITM models the fine-grained interaction between image and text to predict a matching score. Since the downstream datasets contain multiple texts for each image, we change the ground-truth label of ITC to consider multiple positives in the queue, where each positive has a ground-truth probability of 1/#positives. During inference, we first compute the feature similarity score sitc for all image-text pairs. Then we take the top-k candidates and calculate their ITM score sitm for ranking. Because k can be set to be very small, our inference speed is much faster than methods that require computing the ITM score for all image-text pairs [2, 3, 8].
Visual Entailment (SNLI-VE5 [51]) is a fine-grained visual reasoning task to predict whether the relationship between an image and a text is entailment, neutral, or contradictory. We follow UNITER [2] and consider VE as a three-way classification problem, and predict the class probabilities using a multi-layer perceptron (MLP) on the multimodal encoder’s representation of the [CLS] token.
Visual Question Answering (VQA [52]) requires the model to predict an answer given an image and a question. Different from existing methods that formulate VQA as a multi-answer classification problem [53, 2], we consider VQA as an answer generation problem, similar to [54]. Specifically, we use a 6-layer transformer decoder to generate the answer. As shown in Figure 3a, the auto-regressive answer decoder receives the multimodal embeddings through cross attention, and a start-of-sequence token ([CLS]) is used as the decoder’s initial input token. Likewise, an end-of-sequence token ([SEP]) is appended to the end of decoder outputs which indicates the completion of generation.
5results on SNLI-VE should be interpreted with caution because its test data has been reported to be noisy [50]
The answer decoder is initialized using the pre-trained weights from the multimodal encoder, and finetuned with a conditional language-modeling loss. For a fair comparison with existing methods, we constrain the decoder to only generate from the 3,128 candidate answers [55] during inference.
Natural Language for Visual Reasoning (NLVR2 [19]) requires the model to predict whether a text describes a pair of images. We extend our multimodal encoder to enable reasoning over two images. As shown in Figure 3b, each layer of the multimodal encoder is replicated to have two consecutive transformer blocks, where each block contains a self-attention layer, a cross-attention layer, and a feed-forward layer (see Figure 1). The two blocks within each layer are initialized using the same pre-trained weights, and the two cross-attention layers share the same linear projection weights for the keys and values. During training, the two blocks receive two sets of image embeddings for the image pair. We append a MLP classifier on the multimodal encoder’s [CLS] representation for prediction.
For NLVR2, we perform an additional pre-training step to prepare the new multimodal encoder for encoding an image-pair. We design a text-assignment (TA) task as follows: given a pair of images and a text, the model needs to assign the text to either the first image, the second image, or none of them. We consider it as a three-way classification problem, and use a FC layer on the [CLS] representation to predict the assignment. We pre-train with TA for only 1 epoch using the 4M images (Section 3.4).
Visual Grounding aims to localize the region in an image that corresponds to a specific textual description. We study the weakly-supervised setting, where no bounding box annotations are available. We perform experiments on the RefCOCO+ [56] dataset, and fine-tune the model using only imagetext supervision following the same strategy as image-text retrieval. During inference, we extend Grad-CAM [9] to acquire heatmaps, and use them to rank the detected proposals provided by [53].

heading: 6 Experiments

heading: 6.1 Evaluation on the Proposed Methods

text:
First, we evaluate the effectiveness of the proposed methods (i.e. image-text contrastive learning, contrastive hard negative mining, and momentum distillation). Table 1 shows the performance of the downstream tasks with different variants of our method. Compared to the baseline pre-training tasks (MLM+ITM), adding ITC substantially improves the pre-trained model’s performance across
all tasks. The proposed hard negative mining improves ITM by finding more informative training samples. Furthermore, adding momentum distillation improves learning for both ITC (row 4), MLM (row 5), and on all downstream tasks (row 6). In the last row, we show that ALBEF can effectively leverage more noisy web data to improve the pre-training performance.

heading: 6.2 Evaluation on Image-Text Retrieval

text: Table 2 and Table 3 report results on fine-tuned and zero-shot image-text retrieval, respectively. Our ALBEF achieves state-of-the-art performance, outperforming CLIP [6] and ALIGN [7] which are trained on orders of magnitude larger datasets. Given the considerable amount of improvement of ALBEF when the number of training images increases from 4M to 14M, we hypothesize that it has potential to further grow by training on larger-scale web image-text pairs.

heading: 6.3 Evaluation on VQA, NLVR, and VE

text: Table 4 reports the comparison with existing methods on other V+L understanding tasks. With 4M pre-training images, ALBEF already achieves state-of-the-art performance. With 14M pre-training images, ALBEF substantially outperforms existing methods, including methods that additionally use object tags [3] or adversarial data augmentation [8]. Compared to VILLA [8], ALBEF achieves absolute improvements of 2.37% on VQA test-std, 3.84% on NLVR2 test-P, and 1.88% on SNLI-VE test. Because ALBEF is detector-free and requires lower resolution images, it also enjoys much faster inference speed compared to most existing methods (>10 times faster than VILLA on NLVR2).

heading: 6.4 Weakly-supervised Visual Grounding

text:
Table 5 shows the results on RefCOCO+, where ALBEF substantially outperforms existing methods [57, 58] (which use weaker text embeddings). The ALBEFitc variant computes Grad-CAM
visualizations on the self-attention maps in the last layer of the image encoder, where the gradients are acquired by maximizing the image-text similarity sitc. The ALBEFitm variant computes Grad-CAM on the cross-attention maps in the 3rd layer of the multimodal encoder (which is a layer specialized in grounding), where the gradients are acquired by maximizing the image-text matching score sitm. Figure 4 provides a few visualizations. More analysis is in Appendix.
We provide the Grad-CAM visualizations for VQA in Figure 5. As can be seen in Appendix, the Grad-CAM visualizations from ALBEF are highly correlated with where humans would look when making decisions. In Figure 6, we show per-word visualizations for COCO. Notice how our model not only grounds objects, but also their attributes and relationships.
6.5 Ablation Study Flickr30K w/ hard negs w/o hard negs
sitc k = 16 k = 128 k = 256 k = 128
TR 97.30 98.60 98.57 98.57 98.22 ( 0.35) IR 90.95 93.64 93.99 93.95 93.68 ( 0.31)
Table 6: Ablation study on fine-tuned image-text retrieval. The average recall on the test set is reported. We use sitc to filter top-k candidates and calculate their sitm score for ranking.
Table 6 studies the effect of various design choices on image-text retrieval. Since we use sitc to filter top-k candidates during inference, we vary k and report its effect. In general, the ranking result acquired by sitm is not sensitive to changes
in k. We also validate the effect of hard negative mining in the last column.
Table 7 studies the effect of textassignment (TA) pre-training and parameter sharing on NLVR2. We examine three strategies: (1) the two mutimodal blocks share all parameters, (2) only the cross-
attention (CA) layers are shared, (3) no sharing. Without TA, sharing the entire block has better performance. With TA to pre-train the model for image-pair, sharing CA leads to the best performance.

heading: 7 Conclusion and Social Impacts

text:
This paper proposes ALBEF, a new framework for vision-language representation learning. ALBEF first aligns the unimodal image representation and text representation before fusing them with a multimodal encoder. We theoretically and experimentally verify the effectiveness of the proposed
image-text contrastive learning and momentum distillation. Compared to existing methods, ALBEF offers better performance and faster inference speed on multiple downstream V+L tasks.
While our paper shows promising results on vision-language representation learning, additional analysis on the data and the model is necessary before deploying it in practice, because web data may contain unintended private information, unsuitable images, or harmful texts, and only optimizing accuracy may have unwanted social implications.

title: Align before Fuse: Vision and Language Representation Learning with Momentum Distillation


summaries: They analyze the linear DM method in detail. They prove that the estimator has an error form, which is written as an inner product of two residual functions. One is associated with the misspecification of Q-functions. Another is related to the misspecification of W-functions.

summaries: The paper consider off-policy evaluation using linear function approximation under unrealizability setting. Under such more relaxed assumption, they provide characterization of the linear direct method(DM) as an error governed by two approximation residual $\mathcal{R}_B$ and $\mathcal{R}_X$, $$     \hat{J}(\pi) - J(\pi) = \mathbb{E}[\mathcal{R}_B(s,a)\mathcal{R}_X(s,a)] + O(1/\sqrt{n}), $$ with $\mathcal{R}_B$ corresponding to Bellman residual and  $\mathcal{R}_X$ corresponding to residual of marginal density ratio. Leveraing this result, they establish a nonparametric tile-coding estimators  to solve the unrealizability though with a slower convergence.

summaries: This is a theoretical paper which addresses the RL off-policy evaluation with linear function approximation. It proves convergence results of linear function approximations and shows that the direct method (model the dynamics) is asymptotically equivalent to FQE (modeling the value function) and analyzes its convergence properties. Additionally, it proves consistency results for such methods under tile-coding, allowing for consistency (using non-parametric estimation) even under unrealizability of the linear approximators.

summaries: This paper characterizes the offline policy evaluation (OPE) error with linear function approximation in the discounted reward setting. With certain assumptions, this paper proves that the error of Linear Direct OPE algorithm (which is equivalent to the limit of Fitted Q-Evaluation algorithm) converges to the expectation of the product of two residuals. As a corollary, when either the function class is closed or the density ratio is realizable, the asymptotic error is zero. In addition, in the same setting the paper upper bounds the OPE error for tile-coding estimator.

summaries: In this paper, the authors analyze the off-policy evaluation error of a direct estimator with linear function approximation under unrealizability. In Theorem 6, they derive the closed form of the asymptotic bias term as the number of samples approaching \infty. Besides, in section 3.2, they study another method where the feature mappings can be selected adaptively and provide the convergence analysis for their estimation to ground-truth J(\pi).

abstractText: We consider the problem of offline policy evaluation (OPE) with Markov decision processes (MDPs), where the goal is to estimate the utility of given decisionmaking policies based on static datasets. Recently, theoretical understanding of OPE has been rapidly advanced under (approximate) realizability assumptions, i.e., where the environments of interest are well approximated with the given hypothetical models. On the other hand, the OPE under unrealizability has not been well understood as much as in the realizable setting despite its importance in real-world applications. To address this issue, we study the behavior of a simple existing OPE method called the linear direct method (DM) under the unrealizability. Consequently, we obtain an asymptotically exact characterization of the OPE error in a doubly robust form. Leveraging this result, we also establish the nonparametric consistency of the tile-coding estimators under quite mild assumptions.

authors:
P. Amortila
N. Jiang
T. Xie

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

venue: arXiv preprint arXiv:2011.01075

title: Basic properties of strong mixing conditions. a survey and some open questions

venue: arXiv preprint math/0511078

authors:
Y. Duan
Z. Jia
M. Wang

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

venue: In International Conference on Machine Learning,

authors:
M. Dudík
J. Langford
L. Li

title: Doubly robust policy evaluation and learning. arXiv preprint arXiv:1103.4601

authors:
Y. Feng
L. Li
Q. Liu

title: A kernel loss for solving the bellman equation

venue: arXiv preprint arXiv:1905.10506

authors:
Y. Feng
T. Ren
Z. Tang
Q. Liu

title: Accountable off-policy evaluation with kernel bellman statistics

title: On tail probabilities for martingales

venue: Annals of Probability,

authors:
J. Fu
M. Norouzi
O. Nachum
G. Tucker
Z. Wang
A. Novikov
M. Yang
M.R. Zhang
Y. Chen
A Kumar

title: Benchmarks for deep off-policy evaluation

venue: arXiv preprint arXiv:2103.16596

authors:
A. Jacot
F. Gabriel
C. Hongler

title: Neural tangent kernel: Convergence and generalization in neural networks. arXiv preprint arXiv:1806.07572

authors:
C. Jin
Z. Yang
Z. Wang
M.I. Jordan

title: Provably efficient reinforcement learning with linear function approximation

venue: In Conference on Learning Theory,

authors:
N. Kallus
M. Uehara

title: Double reinforcement learning for efficient off-policy evaluation in markov decision processes

venue: J. Mach. Learn. Res.,

authors:
M.G. Lagoudakis
R. Parr

title: Least-squares policy iteration

venue: The Journal of Machine Learning Research,

authors:
H. Le
C. Voloshin
Y. Yue

title: Batch policy learning under constraints

authors:
D.A. Levin
Y. Peres

title: Markov chains and mixing times, volume 107

authors:
S. Levine
A. Kumar
G. Tucker
J. Fu

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

venue: arXiv preprint arXiv:2005.01643

authors:
O. Nachum
Y. Chow
B. Dai
L. Li

title: Dualdice: Behavior-agnostic estimation of discounted stationary distribution corrections

venue: arXiv preprint arXiv:1906.04733

authors:
D. Ormoneit
Ś. Sen

title: Kernel-based reinforcement learning

venue: Machine learning,

title: Eligibility traces for off-policy policy evaluation

venue: Computer Science Department Faculty Publication Series,

authors:
A. Rahimi
B Recht

title: Random features for large-scale kernel machines

authors:
R.S. Sutton
A.G. Barto

title: Reinforcement learning: An introduction

authors:
Z. Tang
Y. Feng
L. Li
D. Zhou
Q. Liu

title: Doubly robust bias reduction in infinite horizon off-policy estimation

venue: arXiv preprint arXiv:1910.07186

authors:
M. Uehara
J. Huang
N. Jiang

title: Minimax weight and q-function learning for off-policy evaluation

authors:
C. Voloshin
H.M. Le
N. Jiang
Y. Yue

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

venue: arXiv preprint arXiv:1911.06854

authors:
R. Wang
D.P. Foster
S.M. Kakade

title: What are the statistical limits of offline rl with linear function approximation? arXiv preprint arXiv:2010.11895

title: Adaptive tile coding for value function approximation

venue: Technical report

authors:
T. Xie
N. Jiang

title: Batch value-function approximation with only realizability

venue: arXiv preprint arXiv:2008.04990

authors:
M. Yin
Wang
Y.-X

title: Asymptotically efficient off-policy evaluation for tabular reinforcement learning

venue: In International Conference on Artificial Intelligence and Statistics,

heading: 1 Introduction

text:
We consider the problem of offline data-driven decision optimization, wherein static records of previous interactions between decision makers and the environmental system of interest are given. The possible application areas include autonomous driving vehicles, natural-language dialogue systems, recommender systems, financial portfolio optimization and healthcare treatment optimization.
The framework of offline reinforcement learning (RL) is one of the promising approaches to this task (Levine et al., 2020). In the standard RL, the environment and the decision-making policy are respectively modeled as Markov decision processes (MDPs) M and conditional distributions of actions π (Sutton and Barto, 2018), where each series of consecutive interactions betweenM and π are abstracted as a stochastic sequence of state s, action a and reward r, called an episode. The objective of the offline RL is then formalized as the maximization of the policy value J(π), the expected value of the total reward obtained from a single episode, given a static dataset of previous interactions.
The crucial part of the problem is that the dataset is static; No additional interaction with the environment is allowed. This constraint poses several unique challenges to the problem. First, the policies we are optimizing, i.e., the target policies, cannot be run in the actual environment. Second, the policies used to generate the dataset, i.e., the behavior policies, are often unknown and may be totally different from the target policies. Consequently, it is even difficult to accurately estimate the value of target policies. This is problematic especially in consideration of real-life applications involving financial costs and healthcare risks.
To address the issue of policy value estimation, the problem of offline policy evaluation (OPE) have been extensively studied in the literature. A class of OPE algorithms are referred as the direct methods (DMs), in which some characteristics ofM are assumed to be realizable under some
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
hypothetical models and J(π) is estimated via a direct estimation of such characteristics. For example, in the fitted Q-evaluation (FQE) algorithm (Le et al., 2019), the policy Q-function is assumed to be well-approximated with a parametric function class and the OPE is reduced to the estimation of its parameters.
DMs are known to be empirically effective (Fu et al., 2021) if such realizability assumptions are satisfied and, more importantly, the converse is also true (Voloshin et al., 2019). However, the theoretical understanding of DMs under unrealizability is still in its active development. For example, several authors have recently studied OPE or offline RL under relatively weak or approximate realizability assumptions (Jin et al., 2020; Xie and Jiang, 2020; Wang et al., 2020) and consequently proposing new algorithms.
In this paper, we approach the problem of unrealizability in the opposite direction; we start with an existing OPE method, study its behavior under complete unrealizability and seek for the possibility of regaining its consistency (i.e., asymptotically achieving zero errors). More specifically, we investigate the properties of a simple DM with linear function approximation, which is equivalent with a number of existing algorithms such as LSTDQ (Lagoudakis and Parr, 2003), FQE (Le et al., 2019) with linear function regressors, the marginalized importance sampling estimator (Yin and Wang, 2020) and DualDICE (Nachum et al., 2019) in tabular settings.
In particular, we first characterize the exact asymptotic error of linear DM under as weak assumptions as possible. It turns out the error is governed by an inner product of two approximation residualsRB andRχ,
Ĵ(π)− J(π) ∝ E [RB(s, a)Rχ(s, a)] +O ( 1/ √ n ) , (informal)
where they are corresponding to the unrealizable components of the value function Qπ and the marginal density ratio ν/µ, respectively. To the best of our knowledge, this is the first to show linear DM is doubly robust against model misspecification, i.e., consistent if either RB = 0 or Rχ = 0 hold (Table 1). Leveraging the above result, we also show that a linear DM with the tile-coding function approximation (Section 8.3.2, Sutton and Barto (2018)) is consistent under surprisingly mild conditions with appropriate tile-size scheduling.
The rest of the paper is organized as follows. In Section 2, we formalize the problem setting as well as the definition of the linear direct estimators. In Section 3, we present the main results, i.e., the asymptotic error analysis of the linear direct estimators and a construction of consistent nonparametric estimators as its application. In Section 4, we discuss related works with comparison to our results. Finally, in Section 5, we present concluding remarks, limitations and future directions. All the proofs of the propositions and the theorem are relegated to the appendix. See Section F for the proofs of the propositions. For the theorem, we present a proof sketch and the pointer to the full proof.

heading: 2 Preliminary

text: In Section 2.1, some notational conventions are introduced. The problem of OPE is then formalized in Section 2.2. Then, Section 2.3, 2.4 and 2.5 respectively introduce assumptions and definitions on the data-collecting processes, the environmental models and the class of estimators we will examine.

heading: 2.1 Basic Notation

text:
We implicitly assume the spaces we encounter in this paper, such as the state space S and the action space A, are equipped with respective metrics and base measures, each of which is a compact subset of either a Euclidean space with the Lebesgue measure, a discrete space with the counting measure or a product of those. We denote by ∫ X f(x) dx the integration of function f with respect to the base measure of X . The subscript X may be omitted if it is obvious from the context. This way we can immediately generalize our results to both continuous and discrete spaces. Also, we denote the expectation of function f with respect to probability density p by ⟨f⟩p := Ex∼p[f(x)].
Let [m] := {1, 2, . . . ,m} denote the set of integers from 1 to m. Let ∥·∥p denote the ℓp-norm for vectors and ∥A∥p→q := supx ̸=0 ∥Ax∥q / ∥x∥p the operator norms for matrices, with the convention ∥A∥p := ∥A∥p→p, for all 1 ≤ p, q ≤ ∞.

heading: 2.2 Problem Setup

text:
The goal of OPE is to estimate the value of decision-making strategy based on a static dataset of interactions with the environment of interest, without directly knowing its mechanism.
The environment is modeled as a Markov decision process (MDP)M≡ (S,A, p0, pT , pr), where S is the state space, A the action space, p0(s) the initial state probability, pT (s′|s, a) the transition probability and pr(r|s, a) the [0, 1]-valued reward probability density function for s, s′ ∈ S, a ∈ A, r ∈ [0, 1]. Here we assume pT and pr are unknown. On the other hand, the decision-making strategy is modeled as a policy, a state-conditional action distribution π(a|s) for s ∈ S, a ∈ A. The value of π is measured with the expected cumulative reward
J(π) := ∞∑ h=0 γh 〈 Phr̄ 〉 pπ0 , (1)
where γ ∈ [0, 1) is the discounting factor, P is the state-transition operator such that (Pf)(s, a) =∫ f(s′, a′)pT (s ′|s, a)π(a′|s′) ds′ da′, r̄(s, a) := ∫ r pr(r|s, a) dr is the expected reward function, and pπ0 (s, a) := p0(s)π(a|s) is the initial state-action distribution. In particular, ⟨Phr̄⟩pπ0 denotes the expected reward after h transitions starting from pπ0 .
The policy value J(π) is estimated based on a collection of transition records ξn ≡ (ξ1, ..., ξn) ∈ Dn called an offline dataset, where D := S ×A× [0, 1]× S is the space of transition records and ξi ≡ (si, ai, ri, s ′ i) ∈ D, i ∈ [n], is a transition record made of a preceding state-action pair (si, ai), the associated reward ri, and the state after transition s′i. The dataset ξ n is assumed to be an instantiation of the random variables Ξn ≡ (Ξ1, ...,Ξn), Ξi ≡ (Si, Ai, Ri, S′i), collected with interactions between the environmentM and a query distribution pquery ≡ {pquery(i)(s, a|ξi−1)}i∈[n] such that its distribution is given in a conditional fashion, p(ξi|ξi−1) = pquery(i)(si, ai|ξi−1) pr(ri|si, ai) pT (s′i|si, ai), i ∈ [n]. Note that the notion of query distribution is so flexible that it admits ξn to be a union of episodes generated with multiple nonstationary policies and even adversaries on the choice of state-action pairs. Definition 1 (OPE problem). An instance of the offline policy evaluation problem is specified with POPE ≡ (M, π, γ, pquery), where the goal is to estimate the policy value J(π) determined by (M, π, γ), given the input data ξn generated with (M, pquery), without knowing any of pT , pr or pquery.

heading: 2.3 Assumptions on Data-Collecting Process

text:
To ensure the existence of reasonable estimators for POPE, we pose a condition on the mixing of data-collecting process, i.e., conditions on pquery. We assume the amounts of mutual dependencies induced by pquery between time-distant transition records are bounded. Assumption 1 (G∗-mixing dataset). There exists a constant G∗ < ∞ such that Ξn is ‘ϕ’-strong mixing with the coefficient g(h) satisfying 1 + 2 ∑n h=1 √ g(h) ≤ G∗.1
1The symbol ‘ϕ’ in the ‘ϕ’-strong mixing has its root in statistics and completely unrelated to the feature mapping. We denote the mixing coefficient by g(h) to avoid confusion with the feature mappings.
See Definition 17 (in the appendix) for the definition of the ‘ϕ’-strong mixing coefficients. Typical examples satisfying Assumption 1 include datasets consisting of multiple short episodes and mixing Markov chains induced by stationary behavior policies.
Proposition 1. The following statements are true.
1. Assume Ξn consists of multiple independently collected episodes with length bounded by H , ordered in a consecutive manner. Then we have G∗ ≤ 2H − 1.
2. Let pquery(i)(s, a|ξi−1) = pT (s|si−1, ai−1)πb(a|s), 1 ≤ i ≤ n, for some stationary behavior policy πb(a|s) and assume the resulting Markov chain has a finite mixing time tmix <∞. Then we have G∗ ≤ 1 + 7tmix.
Note that the definition of G∗-mixing is designed to be more general than these examples. In particular, it is more suitable for our query-distribution framework, which admits adversaries behind the choice of (si, ai)-s or dynamically changing behavior policies.
Under Assumption 1, most properties of pquery is characterized with the marginal data density.
Definition 2 (Marginal data density). Let µ(s, a) be the marginal data density, given by µ(s, a) := 1 n ∑n i=1 E[pquery(i)(s, a |Ξi−1)] for s ∈ S and a ∈ A.
The marginal data density µ quantifies the expected frequency of visitation at each point (s, a) ∈ S×A made by the querying process. Thus, roughly speaking, µ(s, a) indicates that how likely the point (s, a) will be sampled in Ξn.

heading: 2.4 (Possibly Misspecified) Environmental Model: Linear MDPs

text:
We introduce linear MDPs, a simple class of the environmental models denoted by Hϕ.2 We also define the projection ofM ontoHϕ as we are concerned with the unrealizable case,M /∈ Hϕ. A linear MDPHϕ is formally defined via a bounded vector-valued function on the state-action space called a feature mapping, denoted by ϕ : S × A → RK , K ≥ 1. We assume the boundedness and the concentrability of the mapping as follows.
Assumption 2 (Boundedness). sups∈S,a∈A ∥ϕ(s, a)∥2 ≤ 1.
Assumption 3 (Concentrability). Let Σ := ⟨ϕϕ⊤⟩µ be the feature covariance matrix and c∗ := λK(Σ) be its smallest eigenvalue. Then, c∗ > 0.
Note that the concentrability is a standard assumption ensuring all the dimensions of the feature space will be explored in the data-collecting process. A typical example satisfying the above assumptions is the tabular features.
Remark 1. ϕ is said to be tabular if there exits a K-partition of S ×A, {Pk}k∈[K], such that
ϕk(s, a) = I {(s, a) ∈ Pk} , k ∈ [K], s ∈ S, a ∈ A,
where I {·} denotes the indicator function. The tabular features always satisfy Assumption 2. Moreover, it satisfies Assumption 3 if every cell is covered with the data marginal, mink∈[K] Pµ(Pk) > 0, where Pµ denotes the probability measure induced by µ.
Now, the class of ϕ-linear MDPs is defined as follows.
Definition 3 (ϕ-linear MDPs). We sayM is ϕ-linear with respect to π,3 if there exist b ∈ RK and F ∈ RK×K such that
r̄(s, a) = b⊤ϕ(s, a), (Pϕ)(s, a) = Fϕ(s, a) (2)
for almost every s ∈ S and a ∈ A. We refer to the set of all the ϕ-linear MDPs asHϕ.
2We never assume Hϕ contains the true environmental model. It is rather used to facilitate the construction of OPE estimators in Section 2.5.
3The ϕ-linearity is the property of the MDP M and the policy π since the transition operator P depends on π. However, we omit the dependency on π for brevity.
In other words,M is ϕ-linear if both the reward distribution and the transition dynamics are linearly predictable in expectation with respect to ϕ. This definition is motivated by the following proposition; ifM is realizable as a member ofHϕ, the problem of OPE is reduced to the estimation of b and F . Proposition 2. Under Assumption 2 and 3, ifM∈ Hϕ, we have
J(π) = b⊤(I − γF )−1x0, (3)
where x0 := ∫ ϕ(s, a) pπ0 (s, a) dsda.
However, it is impractical to assume we know the mapping ϕ that attains the realizability with the environment of interestM. Thus we introduce the projection ofM ontoHϕ. Definition 4 (Projection of MDP). Let D2(b, F ) be the parameter discrepancy of the ϕ-linearity, given by
D2(b, F ) := E(s,a)∼µ [∣∣r̄(s, a)− b⊤ϕ(s, a)∣∣2 + |(Pϕ)(s, a)− Fϕ(s, a)|2] . (4)
We refer to its minimizer as the projections ofM ontoHϕ, denoted by (b♯, F ♯).
Note that the projection coincides with the true parameter (b, F ) ifM is realizable. Throughout the paper, however, we consider the general case in which the true parameter may not exist, but (b♯, F ♯) always does.

heading: 2.5 Linear Direct Estimators

text:
We finally introduce the linear direct estimator. The idea of the linear direct estimator is twofold. First, we approximately solve the minimization of (4) based on the sample ξn to obtain the estimate of the projection, (b̂, F̂ ) ≈ (b♯, F ♯). Then, we plug the estimate into (3) to get a policy value estimate, which seems reasonable ifM is (approximately) realizable. More precisely, the first step is formalized via the least squares method.
Definition 5 (Empirical projection of MDP). The empirical projection (b̂, F̂ ) is defined as the minimizer of the following cost function,4
C(b, F ; ξn) := 1 n n∑ i=1 [∣∣ri − b⊤ϕ(si, ai)∣∣2 + |ψπ(s′i)− Fϕ(si, ai)|2] . Here, ψπ(s) := ∫ ϕ(s, a)π(a|s) da is the state-marginal feature mapping.
This definition is justified as follows.
Proposition 3. For all b ∈ RK and F ∈ RK×K ,∇b,FE[C(b, F ; Ξn)] = ∇b,FD2(b, F ).
In other words, the gradient of the cost function coincides with that of the parameter discrepancy function in expectation and thus one can expect (b̂, F̂ )→ (b♯, F ♯) in the large sample limit. We have a closed form of the empirical projection.
Proposition 4. Let (Φ,Ψπ, r̂) be given by
Φ := [ϕ(s1, a1), ..., ϕ(sn, an)] ⊤, Ψπ := [ψπ(s ′ 1), ..., ψπ(s ′ n)] ⊤, r̂ := [r1, ..., rn] ⊤.
Then, the empirical projection is given by
b̂ = 1
n Σ̂+Φ⊤r̂, F̂ =
1 n Ψ⊤πΦΣ̂ +, (5)
where Σ̂ := 1nΦ ⊤Φ is the empirical covariance matrix and Σ̂+ is its pseudo-inverse.
4If the sample size n is small, the minimizer may not be unique. In this case, we admit multiple empirical projections.
Algorithm 1 Linear Direct OPE Input: Initial distribution p0, target policy π, data ξn, feature mapping ϕ Output: Policy value estimate Ĵ(π)
1: Compute the empirical projection (b̂, F̂ ) according to Proposition 4. 2: Compute Ĵ(π) = b̂⊤(I − γF̂ )−1x0, where x0 := ∫ ψπ(s)p0(s) ds.
Algorithm 2 Linear Fitted Q-Evaluation Input: Initial distribution p0, target policy π, data ξn, feature mapping ϕ, iteration number H Output: Policy value estimate ĴH(π)
1: Let θ0 := 0 ∈ RK . 2: for h = 1, 2, ...,H do 3: Find θh, the least-norm minimizer of 1n ∑n i=1 ∣∣ri + γθ⊤h−1ψπ(s′i)− θ⊤h ϕ(si, ai)∣∣2. 4: end for 5: Compute ĴH(π) = θ⊤Hx0, where x0 := ∫ ψπ(s)p0(s) ds.
The whole procedure is summarized in Algorithm 1. Note that ψπ(s) in Ψπ and x0 is not necessarily tractable in a closed form. One can always resort to Monte-Carlo estimates ψπ(s) ≈ 1 nψ ∑nψ ℓ=1 ϕ(s, aℓ), where aℓ ∼ π(a|s), ℓ ∈ [nψ], are i.i.d. samples. Proposition 3 still holds under this approximation. Also note that Ĵ(π) is undefined if I − γF̂ is singular. To avoid the undefined behavior and the numerical instability due to near-singularity, we assume ϕ is compatible with POPE in the following sense. Assumption 4 (Compatibility). F ♯γ := (I − γF ♯)−1 exists.
Note that the compatibility implies the well-definedness of Ĵ(π) with high probability for sufficiently large n since F ♯ = limn→∞ F̂ . We also discuss the interpretation, sufficient conditions and a statistical test of the compatibility in Section 3.1.1 and 3.1.2.
Algorithm 1 is equivalent to the LSTDQ (Lagoudakis and Parr, 2003) algorithm and a number of equivalence relationships to recent OPE estimators are drawn in Duan et al. (2020). For the completeness, we show Algorithm 1 is equivalent to the limit of Fitted Q-Evaluation (Le et al., 2019) with linear function approximators, shown in Algorithm 2.
Proposition 5. The output of Algorithm 1 Ĵ(π) is identical to the limit of that of Algorithm 2, limH→∞ ĴH(π), if both exist.

heading: 3 Main Results

text: First, we give an asymptotic characterization of the error Ĵ(π) − J(π), which sheds light on the doubly robust nature of linear DM. Second, leveraging the first result, we show novel consistency properties of a simple tile-coding estimator.

heading: 3.1 Asymptotic Error of Linear DM

text:
As will be shown later, the dominant term of the OPE error is written as an inner product of two functions, namely the χ-residual function and the Bellman residual function. To introduce these residual functions, we begin with the definitions of the ϕ-spanned function space, the ϕ-semi norm and the marginal target density. Definition 6 (ϕ-spanned function space). We denote by Fϕ the normed function space spanned by ϕ1, ..., ϕK , i.e., Fϕ := { (θ⊤ϕ) : S ×A → R
∣∣ θ ∈ RK}. Definition 7 (ϕ-semi norm). For any real-valued functions over the state-action space f : S×A → R, the ϕ-semi norm of f is given by |f |ϕ := ∥ ⟨ϕf⟩µ ∥2. Definition 8 (Marginal target density). Let ν(s, a) be the marginal target density, given by ν(s, a) := (1− γ) ∑∞ h=0 γ h(P †hpπ0 )(s, a), where P † is the adjoint operator of P .
Note that (P †hpπ0 )(s, a) denotes the state-action density after h transitions starting from p0. Thus, ν can be thought of as the relative frequency of the state-action visitations in the target episode with horizon-dependent multiplicative weights γh.
Then, two residual functions are defined as follows. Definition 9 (χ-residual function). The χ-residual function is defined as
Rχ(s, a) := ν(s, a)
µ(s, a) − w♯(s, a),
where w♯ is the minimizer of Lχ(w) := ⟨( νµ − w) 2⟩µ in Fϕ.
Definition 10 (Bellman residual function). The Bellman residual function is defined as RB(s, a) := (BQ♯)(s, a)−Q♯(s, a),
where B : Q 7→ r̄+ γPQ is the Bellman operator and Q♯ is the minimizer of LB(Q) := |BQ−Q|2ϕ in Fϕ.
Note that these functions are ‘residual’ since they are the remainders of the projection of some functions onto Fϕ. Rχ is the residual of the density ratio ν/µ andRB is the residual of the Bellman equation. Also note that the projection of the Bellman equation is coarse-grained as |f |ϕ = 0 does not necessarily imply f = 0 (therefore it is a semi-norm). We will discuss further interpretation of these residual functions in Section 3.1.1.
Now we are ready to state our first result. Theorem 6. Suppose Assumption 1, 2, 3 and 4 hold. Then, we have the almost-sure convergence
Ĵ(π)− J(π) n→∞−→ − 1 1− γ ⟨RBRχ⟩µ (6)
in a poly( 11−γ , 1 n , G ∗, 1c∗ , ∥F ♯ γ∥2) rate, uniformly with respect to the choice of p0. Moreover, the convergence is also uniform with respect to the choice of π, if supπ ∥F ♯γ∥2 <∞.
Proof. (Sketch.) It is directly derived from the non-asymptotic bound (Theorem 13, in the appendix), whose proof strategy is to decompose the error by Ĵ(π)−J(π) = (J♯(π)−J(π))+(Ĵ(π)−J♯(π)), where J♯(π) := ⟨Q♯⟩pπ0 is the projected policy value, and evaluate these terms separately. The limit (6) is obtained by evaluating the first term and the second term vanishes in a rate of O(1/ √ n). In particular, the key step in the evaluation of the first term is the following series of identities,
J♯(π)− J(π) = ... = −⟨RB⟩ν = − 〈 RB ν
µ 〉 µ = − 〈 RB ( ν µ − f )〉 µ , ∀f ∈ Fϕ,
where the last identity is what allows us to fit arbitrary function in Fϕ away from ν/µ, which is made possible with RB being in the orthogonal complement of Fϕ. The full proof is deferred to Section A.

heading: 3.1.1 Implications and Interpretations

text:
Consistency under Q-function realizability (and necessity of the compatibility). Theorem 6 shows the necessary and sufficient condition for the consistency of compatible linear DM. Specifically, J(π) is consistent if eitherRB = 0 orRχ = 0. The first conditionRB = 0 can be interpreted as the so-called Q-function realizability. Proposition 7. Let Qπ := ∑ h≥0 γ
h⟨Phr̄⟩pπ0 be the policy Q-function. Then, under Assumption 2, 3 and 4, we haveRB = 0 if and only if Qπ ∈ Fϕ.
This is interesting sinceRB preserves the full information of Qπ , the unique solution to the Bellman equation, even though it is the result of the coarse-grained projection (Definition 10). Moreover, compared with the existing results on the hardness of OPE under realizability (Wang et al., 2020; Amortila et al., 2020), Proposition 7 suggests the compatibility is the key for the consistency of linear DM. In particular, Amortila et al. (2020) showed there exists a class of hard instances where consistent OPE is impossible if we just assume the Q-function realizability and the concentrability. On the other hand, Theorem 6 and Proposition 7 show we can eliminate such instances if we additionally assume the compatibility (Table 1).
Consistency under density-ratio realizability. Theorem 6 implies another route to achieve the consistency, namelyRχ = 0. By definition, it is trivial thatRχ = 0 is equivalent to ν/µ ∈ Fϕ. Proposition 8. Under Assumption 2 and 3, we haveRχ = 0 if and only if ν/µ ∈ Fϕ.
It suggests we have a consistent estimate of J(π) when the density ratio ν/µ is realizable even if the true value function Qπ is not at all realizable. This is interesting since linear DM is equivalent to linear FQE, which is designed to estimate value function Qπ. In another words, linear FQE is doubly robust in bias without estimating the density ratio. See Section 4 for further comparison with previous double robustness results. Moreover, the density-ratio realizability behaves better than the Q-function realizability. In particular, if we have a non-decreasing sequence of linear function classes {Fϕ(1) ⊂ Fϕ(2) ⊂ · · · }, the corresponding sequence of χ-residuals {R (1) χ ,R(2)χ , · · · } is also non-increasing, i.e., ∥R(m)χ ∥L2(µ) is the non-increasing function of m ≥ 1. This does not hold in general with the Bellman residualRB because the projection metric depends on ϕ.
Convergence without concentrability. A convergence result similar to Theorem 6 can be established without the concentrability condition (Assumption 3), i.e., even if the covariance matrix Σ is singular. In this case, the projections b♯, F ♯, w♯ and Q♯ is modified to the least-norm minimizers and the rate of convergence depends on the minimum nonzero eigenvalue of Σ. See Definition 13 and Theorem 13 in the appendix for the detailed statement.
Linear DM is LB(Q)-minimization. As illustrated in the sketch, the proof of Theorem 6 gives the large sample limit of Ĵ(π), namely Ĵ(π) → J♯(π) = ⟨Q♯⟩pπ0 . Therefore, since Q
♯ is a minimizer of LB(Q) (Definition 10), linear DM is asymptotically equivalent to solving minQ∈Fϕ LB(Q). This observation is closely related to the kernel-loss interpretation of the temporal difference methods (Corollary 3.5 in Feng et al. (2019)).

heading: 3.1.2 Sufficient Conditions for Compatibility and Uniform Boundedness of F ♯γ

text:
In a practical sense, the compatibility is a necessary (not just sufficient) condition for the asymptotic convergence of linear DM; if I − γF ♯ is singular, the smallest singular value of I − γF̂ approaches to zero and hence its inverse (I − γF̂ )−1 is divergent and unstable (if not nonexistent) as well as the estimate Ĵ(π). This is seen from the concentration limn→∞ F̂ = F ♯ (see Proposition 19 in the appendix) and the continuity of singular values.
However, it is difficult to completely characterize when F ♯γ exists or is uniformly bounded. Below, we show a sufficient condition for the uniform boundedness which depends only on µ and Σ.
Proposition 9. Under Assumption 2 and 3, we have supπ ∥F ♯γ∥2 <∞ if
1. There exists v0 ∈ RK such that v⊤0 ϕ(·, ·) ≡ 1, and
2. ϕ(s, a)Σ−1ϕ(s′, a′) ≥ 0 for all (s, a), (s′, a′) ∈ S ×A.
Note that both assumptions hold with the tabular features ϕ, i.e., tabular features are always compatible. In general, the first condition can be satisfied by expanding ϕ with an extra ‘bias’ dimension whose value is always one. On the other hand, the second condition is dependent on ϕ and Σ in a nontrivial manner.
Even if it is difficult to analytically guarantee the compatibility and the uniform boundedness, it is possible to statistically test/bound them by computing a high-probability upper bound on ∥F ♯γ∥2 (cf. Proposition 19 and 20 in the appendix). Moreover, combining it with the non-asymptotic bound (Theorem 13 in the appendix), one can obtain a data-dependent concentration bound. If the resulting concentration rate is not acceptable, then one may change ϕ or fall back on tabular features.

heading: 3.2 Consistency of Tile-Coding Estimators under Unrealizability

text:
As is seen from Theorem 6, not surprisingly, a linear estimator with fixed ϕ is not consistent in general under unrealizability. This motivates us to investigate alternative methods that adaptively selects feature mappings. Such an estimation method is formally defined as follows.
Definition 11 (Nonparametric estimator). We refer to (ϕ, m̂) as a nonparametric estimator if ϕ = {ϕ(m)}∞m=1 is a sequence of feature mappings such that ϕ(m) : S ×A → RKm , Km ≥ 1, and m̂ : N→ N is a model-selecting function such that limn→∞ m̂(n) =∞. The output of the estimator is given as Ĵ(π;ϕ, m̂) := Ĵ(π;ϕ(m̂(n))), where Ĵ(π;ϕ) denotes the linear direct estimate given by Algorithm 1 with a feature mapping ϕ.
In principle, if m̂(n) diverges slowly compared to the convergence (6), the error of (ϕ, m̂) is still characterized by Theorem 6. Thus, if ϕ is such that the asymptotic bias given by (6) goes to zero as m→∞, there exists a consistent nonparametric estimator (ϕ, m̂) with sufficiently slowly diverging function m̂(n).
Below, we show a typical instance of such consistent nonparametric estimators, namely the refining tile-coding estimator. Henceforth, we assume for simplicity S ×A = [0, 1]d, d ≥ 1, i.e., both states and actions are continuous. 5
Definition 12 (Refining tile-coding sequence). We call ϕ as the refining tile-coding sequence if, for all m ≥ 1, ϕ(m) is tabular with respect to themd-partition {P(m)k }k∈[m]d such that P (m) k = ∏d j=1 I (m) kj for all k = (k1, ..., kd) ∈ [m]d, where I(m)k := [ k−1 m , k m ) for all 1 ≤ k < m and I (m) m := [1− 1m , 1].
Leveraging Theorem 13, the non-asymptotic version of Theorem 6, it is shown the nonparametric estimation using the tile-coding scheme is consistent under very mild assumptions.
Proposition 10. For the refining tile-coding sequence ϕ, we have Ĵ(π;ϕ, m̂) n→∞−→ J(π) a.s. if
1. Ξn is G∗-mixing for some G∗ <∞ (Assumption 1).
2. 0 < cµ := infs∈S,a∈A µ(s, a) ≤ Cµ := sups∈S,a∈A µ(s, a) <∞. 3. m̂(n)d/ √ n→ 0 as n→∞.
Note that Proposition 10 assumes nothing on pr, pT , p0 and π other than the implicit well-definedness of their density functions. Because of this, the rate of convergence may be arbitrarily slow. We have a stronger guarantee if some regularities of the density ratio ν/µ is given. A typical example of such regularity is the Lipschitz continuity. Proposition 11. Under the assumptions of Proposition 10, if ν/µ is Lipschitz continuous on S ×A, then we have |Ĵ(π;ϕ, m̂)− J(π)| = O(n− 1 2d+2 ) with m̂(n) = Θ(n 1 2d+1 ).
Note that the stronger convergence result is obtained still without any explicit conditions on the reward and the transition dynamics. This matches the implication of Theorem 6; the error can be controlled with the norm of Rχ, which measures the regularity of ν/µ, without forcing explicit regularities on the Bellman operator.

heading: 4 Related Work

text:
The offline policy evaluation is closely related to the off-policy policy evaluation in the bandit and RL literatures (Precup, 2000; Dudík et al., 2011; Sutton and Barto, 2018), where behavior policies are often assumed to be known. Recently, a number of researchers are focusing on more ‘offline’ settings (Levine et al., 2020) featuring unknown data-collecting policies and relatively large distribution shifts.
The theory of OPE has been often studied under a number of different types of realizability conditions. A common type of realizability is the Bellman-operator realizability (Yin and Wang, 2020; Duan et al., 2020). Jin et al. (2020) also considered the same, but approximate realizability and presented an upper bound with respect to the violation of the realizability. Xie and Jiang (2020) studied offline RL under the Q-function realizability, a relaxation of the Bellman-operator realizability, also allowing small realizability-violation in their analysis. In comparison, we focus on exactly evaluating (dominating term of) the OPE error to understand more about the phenomenon under unrealizability, not just bounding it from above, which allows us to find the double robustness and show the consistency of the nonparametric estimator without realizability.
5It is possible to extend it to allow states and actions being discrete partially or entirely.
Doubly-robust properties similar to Theorem 6 were previously studied in the literature (Kallus and Uehara, 2020; Tang et al., 2019). In particular, Theorem 6 is quite similar to Theorem 3.1 in Tang et al. (2019) as both establish the double robustness of the bias of some OPE methods, although they are orthogonal to one another in the following senses. Theorem 6 shows the DR property of linear DM, while Kallus and Uehara (2020); Tang et al. (2019) establish those of generic meta algorithms based on given (nice) value-function and density-ratio estimators. In particular, Theorem 6 is nontrivial from the context of meta algorithm because linear DM does not perform any density-ratio estimation explicitly. Theorem 6 is also closely related to Example 2 and Example 7 in Uehara et al. (2020). These examples show that linear DM can be interpreted as both value function regression and density ratio regression, but their analysis requires both the Q-function and the density-ratio realizabilities to achieve the consistency (Table 1).
Theories of the kernel-based RL naturally takes into account the function approximation error. The difference between kernel-based methods and linear methods is subtle; Although kernel methods tends to be more expensive in computation, they can be approximated with a finite linear basis (Rahimi et al., 2007). Ormoneit and Sen (2002) shows a kernel-smoothing approach yields a nonparametric convergence rate of O(n− 1 2d+4 ) under different regularity assumptions, including the continuity of r̄. (Feng et al., 2020) studied a kernel-based OPE with confidence error bound, but the error bound is algorithmically determined and not studied analytically.

heading: 5 Concluding Remarks

text:
We have derived an asymptotically exact characterization of the error of the linear direct estimators, one of the most simple and basic OPE methods, under a completely unrealizable setting. As a consequence, we have found that the error matches the inner product of two residual functions implying the double robustness of linear DM, each of which measures the unrealizability of the value function and the marginal density ratio, respectively. We have also found the compatibility of ϕ as a key condition that guarantees the above identity. Finally, we have investigated as its application the error of nonparametric estimators.
Limitation. One limitation of the present work is that we do not have any methods to control ∥F ♯γ∥ other than Proposition 9, which affects the speed of the concentration (6). In particular, this makes it difficult to construct consistent nonparametric estimators with general feature sequences ϕ other than the tabular ones since the norm ∥F ♯γ∥ may depend on n in a nontrivial manner. However, as discussed in Section 3.1.1, controlling ∥F ♯γ∥ is at least equivalent of keeping the hard instances away from the easy instances in the sense of Wang et al. (2020) and Amortila et al. (2020). Thus, we speculate it could be a key question for better understanding of the hardness of OPE problems, rather than just a technical difficulty.
Another limitation is that all the results in this paper are derived under the implicit assumption that the marginal target density ν is well defined with respect to the base measure of S ×A. In particular, generalized functions like Dirac’s delta density function cannot be handled straightforwardly in our framework.
Feature Work. The generalization of the double robustness of linear DM to nonlinear estimators would be an interesting future direction. Studies on the compatibility of the feature mappings ϕ with higher-order smoothness such as Gaussian radial basis functions, spline functions and neural tangent kernels (Jacot et al., 2018) are promising for faster convergence rate of the nonparametric estimator. Another promising direction is to extend the current analysis towards adaptive state-abstraction methods, e.g., Whiteson (2007).

heading: Acknowledgment

text: We deeply thank all the reviewers and the area chair for extensive discussions, which help us greatly improve the manuscript.

title: Asymptotically Exact Error Characterization of Offline Policy Evaluation with Misspecified Linear Models