summaries: This paper proposes a method called Argmax Centroids for learning an approximation to the distribution of the minimizer of a random function. The central idea is to learn a set a particles such that the expected distance between the minimizer of a randomly drawn function and the closest particle is small. The method is shown to be connected theoretically to Wasserstein distance. Experiments on few-shot classification, personalized dialogue modeling, and multi-target domain adaptation demonstrate improvements when the technique is applied to baseline models.

summaries: This paper proposes a natural and simple (yet general) method for approximating the argmax distribution through optimizing a set of centroid points. It is also shown theoretically that under suitable assumptions such an approximation minimizes a bound based on the Wasserstein distance with the actual argmax distribution. Extensive experimentation is carried to support the usefulness of the method. The data include a toy dataset, a few shot learning task, a dialogue system task and a domain adaptation task.

summaries: The paper proposed a method that optimizes a set of centroid points that approximates the argmax distribution p*. Rather than using the Monte Carlo sampling that draws samples randomly, their approach choose the location of each points that approximate target distribution p*.  This approach can be an alternative for bootstrap and can be applied to deep learning applications. The paper showed the effectiveness of the proposed method on few shot image classification, personalized dialogue systems and multi-target domain adaptation. The proposed algorithm boosts the SOTA performance for few-shot classification and meta learning tasks.

summaries: This paper proposes optimizing centroid points to compactly approximate the argmax distribution with a simple objective function. The proposed method is theoretically minimizing a bound of Wasserstein distance between the empirical distribution of the centroids and the ground-truth distribution. Argmax centroids have many applications for machine learning tasks; the author validates the proposed method on multiple meta-learning and mult-task learning tasks.

summaries: The paper proposes a generic method for approximating the argmax distribution of a random function using optimized centroids without explicitly sampling from the argmax distribution. While the closest application for the method is in meta-learning and multi-task learning, the proposed method can find application as an alternative to bootstrap among other applications. In short, for a random function $f_\xi(\theta)$ (think of $\xi$ as data, $\theta$ as parameters, and $f_\xi(\theta)$ as the loss function), the method finds a set of parameters $\boldsymbol{\theta}:=\\{ \theta_i\\}_{i=1}^n$  such that it minimizes  $E_\{\xi\sim\pi\}\[ min_\{i\in\\{1,...,n\\}\} f_\xi(\theta_i)\]$. During inference and for a new task, the authors first find the appropriate parameters for the task (based on a validation set) from the set $\boldsymbol{\theta}$ and then use the corresponding model to solve the task. The method is shown to minimize a bound in Wasserstein distance between the approximated argmax distribution and the real distribution. Finally, the authors show the method's superior performance in various numerical experiments spanning few-shot supervised learning, personalized dialogue systems, and multi-target domain adaptation compared to various baselines.

abstractText: We propose a general method to construct centroid approximation for the distribution of maximum points of a random function (a.k.a. argmax distribution), which finds broad applications in machine learning. Our method optimizes a set of centroid points to compactly approximate the argmax distribution with a simple objective function, without explicitly drawing exact samples from the argmax distribution. Theoretically, the argmax centroid method can be shown to minimize a surrogate of Wasserstein distance between the ground-truth argmax distribution and the centroid approximation under proper conditions. We demonstrate the applicability and effectiveness of our method on a variety of real-world multitask learning applications, including few-shot image classification, personalized dialogue systems and multi-target domain adaptation.

authors: Caruana Rich

title: Multitask learning

venue: Machine learning,

authors: Chen Jianhui Liu Ji Ye Jieping

title: Learning incoherent sparse and low-rank patterns from multiple tasks

venue: ACM Transactions on Knowledge Discovery from Data,

authors: Devlin Jacob Chang Ming-Wei Lee Kenton Toutanova Kristina

title: Bert: Pre-training of deep bidirectional transformers for language understanding

venue: North American Chapter of the Association for Computational Linguistics,

authors:
Dhillon
Guneet S
Chaudhari
Pratik
Ravichandran
Avinash
Soatto
Stefano

title: A baseline for few-shot image classification

venue: International Conference on Learning Representations,

authors:
Efron
Bradley
Tibshirani
Robert J

title: An introduction to the bootstrap

venue: CRC press,

authors: Finn Chelsea Abbeel Pieter Levine Sergey

title: Model-agnostic meta-learning for fast adaptation of deep networks

venue: International Conference on Machine Learning,

authors: Guzman-Rivera Abner Batra Dhruv Kohli Pushmeet

title: Multiple choice learning: Learning to produce multiple structured outputs

venue: In Advances in neural information processing systems,

authors: Hazan Tamir Maji Subhransu Keshet Joseph Jaakkola Tommi

title: Learning efficient random maximum a-posteriori predictors with non-decomposable loss functions

venue: Advances in neural information processing systems,

authors: He Kaiming Zhang Xiangyu Ren Shaoqing Sun Jian

title: Deep residual learning for image recognition

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

authors:
Hendrycks
Dan
Mu
Norman
Cubuk
Ekin D
Zoph
Barret
Gilmer
Justin
Lakshminarayanan
Balaji

title: Augmix: A simple data processing method to improve robustness and uncertainty

authors:
Hu
Shell Xu
Moreno
Pablo G
Xiao
Yang
Shen
Xi
Obozinski
Guillaume
Lawrence
Neil D
Damianou
Andreas

title: Empirical bayes transductive meta-learning with synthetic gradients

authors: Kang Zhuoliang Grauman Kristen Sha Fei

title: Learning with whom to share in multi-task feature learning

venue: In International Conference on Machine Learning,

authors:
Kingma
Diederik P
Ba
Jimmy

title: Adam: A method for stochastic optimization

authors:
Kuo
Frances Y
Sloan
Ian H

title: Lifting the curse of dimensionality

venue: Notices of the AMS,

authors:
Lee
Hae Beom
Nam
Taewook
Yang
Eunho
Hwang
Sung Ju

title: Meta dropout: Learning to perturb latent features for generalization

venue: In International Conference on Learning Representations,

authors: Lee Stefan Purushwalkam Senthil Cogswell Michael Ranjan Viresh Crandall David Batra Dhruv

title: Stochastic multiple choice learning for training diverse deep ensembles

authors: Liu Qiang Wang Dilin

title: Stein variational gradient descent: A general purpose bayesian inference algorithm. Advances in neural information processing systems, 2016

authors: Madotto Andrea Lin Zhaojiang Wu Chien-Sheng Fung Pascale

title: Personalizing dialogue agents via meta-learning

venue: In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics,

authors: Papineni Kishore Roukos Salim Ward Todd Zhu Wei-Jing

title: Bleu: a method for automatic evaluation of machine translation

venue: In Annual Meeting of the Association for Computational Linguistics,

authors: Peng Baolin Zhu Chenguang Li Chunyuan Xiujun Jinchao Zeng Michael Gao Jianfeng

title: Few-shot natural language generation for task-oriented dialog

venue: Conference on Empirical Methods in Natural Language Processing,

authors: Peng Xingchao Bai Qinxun Xia Xide Huang Zijun Saenko Kate Wang Bo

title: Moment matching for multi-source domain adaptation

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

authors: Sun Qianru Liu Yaoyao Chua Tat-Seng Schiele Bernt

title: Meta-transfer learning for few-shot learning

authors: Thrun Sebastian

title: Lifelong learning algorithms

venue: In Learning to learn,

authors: Thrun Sebastian O’Sullivan Joseph

title: Discovering structure in multiple learning tasks: The tc algorithm

authors:
Tian
Yonglong
Wang
Yue
Krishnan
Dilip
Tenenbaum
Joshua B
Isola
Phillip

title: Rethinking few-shot image classification: a good embedding is all you need

venue: Proceedings of the European Conferenceon Computer Vision,

authors: Tzeng Eric Hoffman Judy Saenko Kate Darrell Trevor

title: Adversarial discriminative domain adaptation

authors:
Wang
Yan
Chao
Wei-Lun
Weinberger
Kilian Q
van der Maaten
Laurens

title: Simpleshot: Revisiting nearest-neighbor classification for few-shot learning

authors:
Wu
Zuxuan
Han
Xintong
Lin
Yen-Liang
Gokhan Uzunbas
Mustafa
Goldstein
Tom
Nam Lim
Ser
Davis
Larry S

title: Dcan: Dual channel-wise alignment networks for unsupervised scene adaptation

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

authors: Xue Ya Liao Xuejun Carin Lawrence Krishnapuram Balaji

title: Multi-task learning for classification with dirichlet process priors

authors: Yang Xiaolin Kim Seyoung Xing Eric

title: Heterogeneous multitask learning with joint sparsity constraints

authors: Ye Mao Liu Qiang

title: Centroid approximation for bootstrap

venue: arXiv preprint arXiv:2110.08720,

authors: Yoon Jaesik Kim Taesup Dia Ousmane Sungwoong Bengio Yoshua Ahn Sungjin

title: Bayesian model-agnostic meta-learning

venue: In Proceedings of the 32nd International Conference on Neural Information Processing Systems,

authors: Yu Huanhuan Hu Menglei Chen Songcan

title: Multi-target unsupervised domain adaptation without exactly shared categories. Advances in neural information processing systems, 2018

authors: Yu Kai Tresp Volker Schwaighofer Anton

title: Learning gaussian processes from multiple tasks

venue: In International conference on Machine learning,

authors: Yue Zhongqi Zhang Hanwang Sun Qianru Hua Xian-Sheng

title: Interventional few-shot learning

authors: Zenke Friedemann Poole Ben Ganguli Surya

title: Continual learning through synaptic intelligence

authors: Zhang Saizheng Dinan Emily Urbanek Jack Szlam Arthur Kiela Douwe Weston Jason

title: Personalizing dialogue agents: I have a dog, do you have pets too? Association for Computational Linguistics, 2018

authors: Zhang Yu Yeung Dit-Yan

title: A convex formulation for learning task relationships in multi-task learning

venue: Association for Uncertainty in Artificial Intelligence,

authors: Zhou Jiayu Chen Jianhui Ye Jieping

title: Clustered multi-task learning via alternating structure optimization. Advances in neural information processing

authors: Zhou Qiang Zhao Qi

title: Flexible clustered multi-task learning by learning representative tasks

venue: IEEE transactions on pattern analysis and machine intelligence,

heading: 1 Introduction

text:
Many problems in machine learning and statistics involve optimizing a random function such as the empirical loss. This work focuses on approximating the distribution of the optimum points of a random function of interest. Specifically, we consider the following problem:
The Argmax Centroid Problem Assume we are given a random function f⇠(✓) where ⇠ is a random variable and ✓ is a variable of interest. We are interested in estimating the distribution ⇢⇤
of the minimum points ✓⇠ := argmin✓ f⇠(✓) as we draw ⇠ randomly. In particular, we want to find a set of “centroid points” {✓i}ni=1, whose empirical measure is close to ⇢⇤ in terms of Wasserstein distance. We assume the minimizer of f⇠ is always unique.
This problem can find applications in a variety of machine learning and statistics techniques, including bootstrap (Efron & Tibshirani, 1994), random MAP (Hazan et al., 2013), Thompson sampling (Russo et al., 2017), as well as multi-task learning and meta learning. One naive method to approximate ⇢⇤, which is widely used in the methods above, is to draw an i.i.d. sample of ⇠ and calculate the corresponding argmin points. However, this approach is computationally expensive because calculating each argmin point requires solving an independent optimization problem and the quality of Monte Carlo approximation is poor unless n is very large, especially for large-scale optimization problems in deep learning.
In this work, we propose a more efficient centroid approximation to replace the Monte Carlo sampling, in which we explicitly optimize a set of points ✓ = {✓i}ni=1 to approximate target distribution ⇢⇤. By carefully choosing the location of each point ✓i (rather than drawing them randomly), our method allows us to obtain a set of points ✓ that are well aligned to approximate the overall argmin distribution ⇢⇤. Theoretically, under proper conditions, our method can be viewed as minimizing a surrogate of the Wasserstein distance between the empirical distribution of the centroid approximation and the ground-truth distribution. Therefore, given a small budget on sample size, we can estimate the argmin distribution more accurately than using Monte Carlo estimation.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
Argmax centroids can find applications in a variety of machine learning problems. In the empirical studies of this work, we mainly focus on meta learning and multi-task learning tasks. For these problems, we learn from a distribution of datasets/tasks/domains and ⇠ denotes a random dataset drawn from some population. Using argmax centroids allows us to obtain an ensemble of centroid models that can capture the uncertainty and variation in different datasets and domains. We test our method on multiple tasks, e.g., the few-shot image classification, the personalized dialogue system, and the multi-target domain adaptation. For all the above tasks, our method can be easily implemented and enhance the performance of a number of baseline methods, including but not limited to some of the recent state-of-the-art (SOTA) methods, e.g. IFSL (Yue et al., 2020).

heading: 2 Methodology

text:
We introduce our problem description, propose our algorithm to approximate argmin distributions, and study its properties.
Problem description Many problems in machine learning can be framed as minimizing or maximizing random functions f⇠(✓) where ⇠ is some random variable drawn from a distribution ⇡ on a space ⌅ and ✓ 2 ⇥ ✓ Rd. That is,
✓⇠ = argmin ✓2⇥ f⇠(✓). (1)
We assume the minimum of f⇠(✓) is unique. Denote by ⇢⇤ the distribution of ✓⇠ where ⇠ ⇠ ⇡, which we call the argmin distribution of f . We are interested in approximating ⇢⇤. The problem in (1) finds wide applications in machine learning in various different ways, including random MAP (Hazan et al., 2013), bootstrapping (Efron & Tibshirani, 1994), and multi-domain/meta learning as we elaborate in Section 3.
As mentioned in Section 1, a naive method to approximate ⇢⇤ is to draw an i.i.d. sample {⇠i}ni=1 from ⇡ and calculate the corresponding argmin points ✓⇠i for each particle respectively. However, the quality of Monte Carlo approximation is poor when n is small (Kuo & Sloan, 2005). In practice, it is not affordable to draw a large number of argmin points for large-scale optimization problems in deep learning, both because that it requires to solve an optimization for calculating each ✓⇠i , and it is memory-hungry to store a large number of ✓⇠i when the parameter dimension is high.
Argmax Centroids We propose a more efficient centroid approximation to replace Monte Carlo sampling, where we explicitly optimize a set of points ✓ = {✓i}ni=1 2 ⇥n, associated with a set of weights ⌫ = {⌫i}ni=1 2 Rn, such that the ground-truth target distribution ⇢⇤ can be well approximated by the weighted empirical measure:
⇢̂✓,⌫ = nX
i=1
⌫i ✓i ,
where ✓i is delta measure centered at ✓i, and ⌫ is assumed to take values from the probability simplex on [n]: V = {⌫ : Pn i=1 ⌫i = 1, ⌫i 0, 8i 2 [n]}. Here [n] := {1, 2, · · · , n}. Ideally, we would like to choose ✓,⌫ to minimize certain distance metrics between ⇢̂✓,⌫ and ⇢⇤, a canonical example of which is the p-Wasserstein distance (p > 0), defined as
Wp(⇢̂, ⇢ ⇤) = inf µ2⇧(⇢̂,⇢⇤) E(✓,✓⇠)⇠µ [k✓ ✓⇠k p] 1/p ,
where ⇧(⇢̂, ⇢⇤) denotes the set of probability measures on ⇥⇥⇥ such that its two marginal distributions on ⇥ are ⇢̂ and ⇢⇤. We assume that k·k is the standard Euclidean norm in this paper. However, it is expensive to calculate the Wasserstein distance due to the high computational cost of drawing ✓⇠ ⇠ ⇢⇤, which requires to repetitively solve optimization (1). To improve the computational efficiency, we propose to minimize the following surrogate of Wasserstein distance:
min ✓2⇥n,⌫2V Wf (⇢̂✓,⌫ , ⇡), Wf (⇢̂, ⇡) := inf µ2⇧(⇢̂,⇡) E(✓,⇠)⇠µ [f⇠(✓)] , (2)
where ⇧(⇢̂,⇡) is the set of probability measures on ⇥⇥ ⌅, whose marginal distributions on ⇥ and ⌅ equal ⇢̂ and ⇡, respectively. Here we replace the norm k✓ ✓⇠kp with the function f⇠(✓), so that we
do not need to draw ✓⇠ ⇠ ⇢⇤ and hence solve the expensive optimization in (1). A key property of Wf is that its global minimum in the space of distributions is achieved by the argmin distribution ⇢⇤. Hence, we obtain increasingly accurate estimate of ⇢⇤ as we solve (2) with increasing particle size n.
To introduce the result, we start with a general definition of argmin distributions that works for when the minimum of f⇠ is not necessarily unique.
Definition 2.1. Assume f⇤⇠ := min✓2⇥ f⇠(✓) > 1 for every ⇠ 2 ⌅. We say that a distribution ⇢⇤ on ⇥ is an argmin distribution of f⇠ with ⇠ ⇠ ⇡, if there exist a coupling measure µ⇤ 2 ⇧(⇢⇤,⇡), such that ⇢⇤(✓ 2 argmin f⇠) = 1. Here argmin f⇠ is the set of global minima of f⇠, that is, argmin f⇠ = {# 2 ⇥ : f⇠(#) = f⇤⇠ }.
If the optimum of f⇠ is unique for every ⇠ 2 ⌅, then there is an unique argmin distribution ⇢⇤, which is the distribution of ✓⇠ = argmin✓2⇥ f⇠(✓) when ⇠ ⇠ ⇡.
Theorem 2.2. Assume ⇢⇤ is any argmin distribution of f⇠ with ⇠ ⇠ ⇡. Then the minimum of Wf (⇢,⇡) is achieved by ⇢⇤, that is,
Wf (⇢ ⇤,⇡) = E⇠⇠⇡  min ✓2⇥ f⇠(✓) = min ⇢2P Wf (⇢,⇡),
where P is the space of probability distributions on ⇥.
It is not easy to directly minimize the form of Wf in (2) because it requires to jointly minimize ✓,⌫ and the coupling measure µ. However, the key observation below shows that the optimization in both ⌫ and µ can be solved in closed form, yielding a simple objective function on ✓.
Theorem 2.3. For a fixed ✓ 2 ⇥n, we have
min ⌫2V Wf (⇢̂✓,⌫ , ⇡) = E⇠⇠⇡  min i2[n] f⇠(✓i) ,
where the minimum on the left hand side is achieved by ⌫⇤ = {⌫i}ni=1 with
⌫⇤i = E⇠⇠⇡
" P(i 2 argmin
j2[n] f⇠(✓j))
# , 8i 2 [n], (3)
with P(i 2 argminj2[n] f⇠(✓j)) := 1Z✓,⇠ I(i 2 argminj2[n] f⇠(✓j)) and Z✓,⇠ the number of elements in the argmin set, i.e., Z✓,⇠ = | argminj2[n] f⇠(✓j)|.
Here the ⌫⇤i in (3) is the probability that ✓⇤i achieves the minimum value of minj2[n] f⇠(✓⇤j ), with ties broken randomly with equal probabilities.
Therefore, the optimal centroids ✓⇤ and the weights ⌫⇤ are given by
✓⇤ = argmin {✓i}ni=1
⇢ L(✓) := E⇠⇠⇡  min i2[n] f⇠(✓i) , ⌫⇤i = E⇠⇠⇡  P(i 2 arg min j2[n] f⇠(✓ ⇤ j )) . (4)
Note that objective in (4) reduces to the well known K-means objective function if we take f⇠(✓) = k✓ ✓⇠k2 , in which case ✓ and ⌫ are the centers and the sizes of the clusters, respectively. Intuitively, minimizing L(✓) allows us to ensure that the best function value mini2[n] f⇠(✓i) is small on average.
In practice, we can optimize ✓i using stochastic gradient descent, and update ⌫i recursively. See Algorithm 1 for details. At each iteration, we draw a (set of) ⇠ ⇠ ⇡, find the ✓i that attains i = argminj f⇠(✓j) and update ✓i with gradient descent as displayed in line 4, Algorithm 1. The frequency ⌫i is also updated accordingly when a ✓i is updated, see line 5 in Algorithm 1.
Re-sampling During optimization, it is possible that some ✓i are rarely selected and hence its weight ⌫i becomes small and causes a degeneration problem (i.e., nearly zero important weight). To address this problem, we monitor the effective sample size of the points, defined as neff = ( P i ⌫i) 2/( P i ⌫ 2 i ). If the effective sample size becomes smaller than a threshold, we re-sample a set of new particles ✓i with replacement from ⇢̂✓,⌫ = Pn i=1 ⌫i ✓i and repeat the updates. In practice, we break the ties randomly in argmin to avoid the case when two ✓i remain to be identical throughout the algorithm.
Algorithm 1 Main Algorithm: Argmax Centroids for Approximating ⇢⇤
1: Input: {✓i}ni=1 denotes the learnable centroids, ⌫i denotes the updated frequency of ✓i, ✏ denotes the step size for gradient descent, ↵ 2 [0, 1] denotes a parameter to control the frequency update and ⌘ is a threshold to control the resampling. 2: while not convergence do 3: Find i⇤ = argmini f⇠(✓i) with ⇠ ⇠ ⇡. 4: Update ✓i⇤ ✓i⇤ ✏r✓i⇤ f⇠(✓i⇤), ⌫i⇤ ↵⌫i⇤ + 1, and ⌫i = ↵⌫i for i 6= i⇤. 5: If neff  ⌘, resample {✓i}ni=1 from ⇢̂✓,⌫ / Pn i=1 ⌫i ✓i . 6: end while
Bounds with Wasserstein Because Wf coincides with the Wasserstein distance if f⇠ is a simple quadratic function f⇠(✓) = ||✓ ✓⇠||2, we can provide some simple bounds between Wf and Wasserstein distance by approximating f⇠ with the quadratics using Taylor approximation.
Assumption 2.4. Let ✓⇠ be the minimum of f⇠(✓) as in (1). Assume there exists h1, h2, p1, p2 2 (0,1), such that for any ✓ 2 ⇥ and ⇠ 2 ⌅,
h1 k✓ ✓⇠kp1  f⇠(✓) f⇠(✓⇠)  h2 k✓ ✓⇠kp2 .
This assumption holds with p1 = p2 = 2 if f is strongly convex w.r.t. ✓ and 0 < h1/2  min(f 00⇠ (✓))  max(f 00⇠ (✓))  h2/2 <1 for 8✓ and ⇠, where min and max are the minimum and maximum eigenvalue; it also holds with p2 = 1 if f is Lipschitz w.r.t. ✓ with kfkLip = h2.
Theorem 2.5. Assume Assumption 2.4 holds.
1) We have for any ✓ 2 ⇥n and ⌫ 2 V , h1Wp1(⇢̂✓,⌫ , ⇢
⇤)p1 Wf (⇢̂, ⇡) Wf (⇢⇤,⇡)  h2Wp2(⇢✓,⌫ , ⇢⇤)p2 . 2) For the optimal ✓⇤ and ⌫⇤ in (4), we have
Wp1(⇢̂✓⇤,⌫⇤ , ⇢ ⇤)p1  h2
h1 inf ✓2⇥n,⌫2V Wp2(⇢✓,⌫ , ⇢
⇤)p2 . (5)

heading: 3 Applications and Related Works

text:
Approximating argmax distribution can be found as a key component of many machine learning methods. This includes methods like bootstrap (Ye & Liu, 2021), Thompson sampling, and random MAP, in which the argmax distribution plays a key role by design, and as well as novel applications from meta learning and multi-task learning, which we study extensively in Section 4.
Training Dataset
Models
θ1D1D2 D3 D4 D5 D6
D
Test Dataset
θ*Select Best Align Train Test θ2 θ3
θ4
Figure 1: An illustration of our selection process for both training and evaluation. Test dataset D refers to the training or validation subset of the coming test task D.
Learning with Ensembles of Datasets Approximating the argmax distribution finds a natural application in meta learning and multi-task/multi-domain learning, in which we need to learn from an ensemble or a distribution of datasets. Denote by D a dataset on which we want to learn a model parameter ✓ with a loss function `(✓, D). Instead of having a single dataset, we consider the case when we have a large number of datasets {Di} which we assume is drawn from a distribution P . We aim to find a set of models {✓i}ni=1 where exists at least one good model for every dataset D with small n. Denote by ✓D = argmin✓ `(✓, D) and ⇢⇤ the distribution of ✓D as D ⇠ P . Then the problem can framed as finding {✓i}ni=1 to approximate ⇢⇤, and hence can be framed into
min {✓i}ni=1
⇢ ED⇠P  min i2[n] `(✓i, D) . (6)
In the test phase, given a new coming dataset D, which we assume includes a validation set D̃ with true labels, we select the best model ✓i⇤ among the centroids that minimizes the loss i⇤ = argmini2[n] `(✓i, D̃). The pipeline is shown in Figure 1. The idea here is to prepare a pool of candidate models to best cover all different scenarios (according to probability ✓D ⇠ ⇢⇤), so that we can select the best model for any new random task drawn from ⇢⇤. This is different from typical ensemble learning which averages the output of multiple models during evaluation; instead, we use the best single model ✓i⇤ selected from the pool during evaluation. The objective ` and how to optimize ` is problem-dependent. For example, in meta learning, ` is updated with gradient descent and meta gradient. The details about the formulation of ` and its update rule is shown in Section 4 for different tasks. The method in (6) can also be used in bootstrapping, in which we are given a dataset D0 of true interest and we draw random datasets D ⇠ P by resampling from D0 with replacement. Using the argmax centroids can yield better approximation with small n than naive random sampling that calculates ✓D from randomly drawn D ⇠ P . The theoretical properties and efficient algorithms specified to bootstrap desires an independent treatment, which we explore separately in another work. Another related method is multiple choice learning (MCL) (Guzman-Rivera et al., 2012; Yu et al., 2018; Lee et al., 2016), which is an ensemble learning method using a similar objective function as (6) but with very different motivation and settings. MCL can be viewed as minimizing (6), but assuming each D to be a single data example rather than a dataset, with the goal of learning a set of models and ensemble them for a single dataset. During evaluation, the outputs of the multiple models from MCL are averaged to give the final output, rather than selecting the best one as we suggest above based on the perspective of approximating ⇢⇤ .
Multi-task Learning Jointly learning models from multiple tasks has attracted long-term attention in machine learning community. In multi-task learning (MTL), there are multiple learning tasks and most of them (or all of them) are assumed to be related to each other. MTL algorithms can be grouped into two main approaches: the feature learning methods and task relation learning methods. Since tasks are related, it is intuitive to assume that different tasks share some common feature representation, and thus feature learning approaches focus on learning the common representation with regularizations (Yang et al., 2009), structure designing (Caruana, 1997), etc. The other approach focuses on learning task relations. The task relations are learnt from data automatically with a given prior (Yu et al., 2005; Xue et al., 2007; Zhang & Yeung, 2012), matrix decomposition (Chen et al., 2012) or clustering (Thrun & O’Sullivan, 1996). Recently, meta learning (Finn et al., 2017), lifelong learning (Thrun, 1998) and continual learning (Zenke et al., 2017) are proposed to solve MTL under different conditions.
Our method is similar to learning task relation with clustering. Different from previous works which cluster the tasks with latent representation (Zhou & Zhao, 2015), learnable relation matrix (Zhou et al., 2011; Kang et al., 2011) or side information (Caruana, 1997), we automatically assign a model to a certain domain/task based on its loss.

heading: 4 Experiments

text: In our experiments, we start with a toy example on which we show that our algorithm approximates the argmax distribution better than simple Monte Carlo estimation (Section 4.1). We then apply our method to standard few-shot learning benchmarks, in which parameters are learned on thousands of domains (Section 4.2). We further apply our method to personalized dialogue systems (Peng et al., 2020) (Section 4.3) and multiple target domain adaptation (Yu et al., 2018) (Section 4.4) to verify whether our proposed method can be applied to different real-world applications. In all experiments, we set the replacement controller ⌘ = 1.2 and ↵ = 0.5 for Algorithm 1.

heading: 4.1 Toy Examples

text:
We start with a toy example to verify that our method can provide a better approximation of ⇢⇤ than Monte Carlo estimation with the same number of samples. We set f⇠(✓) = k✓ ⇠k2, so that ✓⇠ = ⇠ and ⇢⇤ = ⇡. We set ⇡ to be d-dimension Gaussian mixture model with five modes. Note that our method is equivalent to a gradient descent variant of K-means in this case. Figure 2 demonstrates the two-dimension case, from which we can see that argmax centroids captures the different modes in the distribution and are aligned optimally to get better approximation then random sampling.
Figure 2(d) shows the 2-Wasserstein distance (p = 2) from the empirical measure ⇢̂✓⇤,⌫⇤ of the centroids and the true distribution ⇢⇤ (calculated by drawing a large sample from ⇢⇤), when the dimension d of ✓ varies. We can see that for both 100-dimension and 10-dimension cases, our method yields lower Wasserstein distance than random sampling for different n.

heading: 4.2 Few-Shot Supervised Learning

text:
We now apply our method to few-shot image classification using the formulation in (6), in combination with model agnostic meta learning (MAML) (Finn et al., 2017).
To introduce the setting, let D = {DTrainj , Dtestj } be a random dataset (or task) drawn P , which includes a training and test set. Let ✓0 = A(✓, Dtrain) be the result of training the parameter on Dtrain starting from ✓, where A denotes the training algorithm, which is typically one step or few steps of stochastic gradient descent with the training set. In MAML, we optimize ✓ so that the peformance of ✓0 = A(✓, Dtrain) is maximized on Dtest. The MAML loss is `(✓, D) = L(A(✓, Dtrain), Dtest), with the hope to rapidly solve a new coming task after learning several other similar tasks.
Standard MAML learns a single model ✓, which may not work well for all the tasks D when the discrepancy between tasks is large. By plugging the MAML loss into (6), we obtain a new generalization of MAML with which we can prepare a pool of candidate models {✓i}ni=1 (the argmax centroids), out of which we can select the best one during testing. Note that this is different from the
existing ensemble MAML methods such as (e.g., Lee et al., 2019; Yoon et al., 2018), which averages (instead of selecting the best among) the outputs of multiple models.
Baselines We compare and implement our method based on the recent state-of-the-art few-shot learning methods (e.g Hu et al., 2020; Yue et al., 2020; Wang et al., 2019). These methods train a network consisting of a backbone network shared by all the datasets (tasks), which is fed into classification heads specialized to individual datasets. During training, we first train a backbone network on all the training datasets in the training tasks using typical method, and then use metalearning style training to tune the classification heads while keeping the backbone frozen.
We implement our proposed argmax centroids upon two recently proposed few-learning methods, SIB and IFSL. These recently proposed methods achieve state-of-the-art results on supervised few-shot image classification benchmarks 1. SIB (Hu et al., 2020) proposes to learn synthetic gradient for new coming tasks, and IFSL (Yue et al., 2020) finds out that pre-trained knowledge is essentially a confounder that causes spurious correlations between the sample features and class labels in support set. They further propose regularization terms to eliminate the mismatch.
All these baselines and other recent works (e.g. Hu et al., 2020; Yue et al., 2020; Wang et al., 2019; Dhillon et al., 2020) focus on learning a better single model by introducing strong regularization methods. For the baselines, we focus on, a clear disadvantage of SIB and IFSL is that they share one single ✓ for all the datasets and may not work well once the discrepancy between task is large. By applying our method, we train a fixed number of classification heads, which are treated as the argmax centroids. This allows us to pick the best head ✓ and further finetune it on the training set for each test task during testing. We simply combine these baseline approaches with our algorithm to obtain further improvements. To save computation cost in practice, we evaluate A(✓, DTrain) by one-step gradient descent and then select ✓i with lowest loss among ✓.
Datasets Standard benchmarks of few-shot classification are chosen for experiments. We evaluate all the baselines and our algorithms on two subsets of ImageNet, Mini-ImageNet and TieredImageNet (Sun et al., 2019). MiniImageNet contains 64 classes for training, 16 for validation and 20 for test. Training/validation/test tasks are sampled from the 64/16/20 classes. TieredImageNet (Sun et al., 2019) is much larger compared to miniImageNet and other benchmarks, with 608 classes and 1300 samples per class. These classes are partitioned into 351/97/160 disjoint sets for train/val/test to achieve a larger domain difference between training and testing During train-
ing, the images in Mini-ImageNet and tieredImageNet are resized to 80⇥80 and 84⇥84, respectively. Each sampled dataset D is a 5-class classification, with 1-shot/5-shot images per class for training and 15 images per class for test. When evaluating the trained models, 2000 test tasks are sampled from the test set, and the accuracy on Dtest of all the test tasks are reported for comparison.
1https://few-shot.yyliu.net
Implementation Details For each baseline method, we create a small number of additional parameters. During the second training stage, given a backbone, e.g., Wide-ResNet-28-10 (Zagoruyko & Komodakis, 2016), we use additional parameters {✓i}ni to re-weight the final-layer features. In the experiments, for few-shot learning based on SIB and IFSL, we set n = 16. We only introduce a small number of additional parameters (0.01M parameters) compared to the model size (22M parameters).
For both the training and testing, we keep all the settings (e.g. optimizer, learning rate, number of tasks) the same for each baseline method. We first train the feature extractors using the standard crossentropy loss on the base classes (i.e., the classes in the training set in all training tasks). Secondly, training the heads following the standard meta learning pipeline. Finally, we test the trained models on sampled test tasks. For each test task, we do a few gradient descent steps on the training set. The number of iterations follows the baselines.
Results Table 3 shows the comparison between our proposed method and standard ensemble MAML methods. We implement our method upon several recently proposed strong baselines. As demonstrated in Table 1 and 2, our algorithm consistently improves all the baseline methods in all settings, which suggests that our proposed algorithm is a general method for few-shot image classification. For example, on Mini-ImageNet, we improve the accuracy of SIB by a large margin for both 1-shot (70.0% to 71.2%) and 5-shot (80.0% to 81.1%) classification. For IFSL, we can also boost the performance under most of the settings.
Comparison to Ensemble Methods Here, we follow the setting in and ensemble MAML (Yoon et al., 2018) where the backbone is not pretrained on all the training images and is jointly training during the meta learning step. We compare two popular ensemble baselines, ensemble MAML and Bayesian MAML (Yoon et al., 2018). Ensemble MAML trains n models independently and take an average of the outputs of all the models during evaluation. Bayesian MAML (Yoon et al., 2018) uses SVGD (Liu & Wang, 2016) to jointly update n models during training and ensemble them during evaluation. Instead of choosing the best model for a test domain like our method, the ensemble methods average the outputs of all the models. From Table 3, we can see that our method is better than both ensemble approaches on one-shot classification on Mini-ImageNet with different neural architectures. On ResNet-18 and WRN-28-10, our method achieves better results than ensemble methods.
Ablation Study In Figure 3, we change n and make a selection based on training/test/validation loss to have a deeper understanding of our algorithm. We notice that, if we do not have a separate validation set, we may need to select the best model on the training set during evaluation, which cause overfitting. We investigate this issue in Figure 3, in which we show the results when we select the best models using training, validation and, test set, respectively. In order to do the selection on the validation set, we additionally draw 5 images per class for each test task. The result shows that, in our case, both selecting on training and validation set is worse than the “oracle” way (i.e., selecting on the test set and evaluating on the test set). When the number of heads increases, the performance of selecting on training set drops and over-fitting happens. However, in practice, one cannot get access to the test set during training. Therefore, selecting on the validation set is an alternative choice.

heading: 4.3 Personalized Dialogue System

text:
Problem Set We consider learning personalized chit-chat dialogue agents for making chat-bots more consistent for each user (e.g. Zhang et al., 2018; Madotto et al., 2019b; Tian et al., 2020).
Previous approaches usually learning persona similarity from persona descriptions (Zhang et al., 2018). Different from these methods, current personalized dialogue systems focus on learning to quickly adapt to new personas by using few samples. In this problem, each dataset D = (DTrain, DTest) ⇠ P contains several dialogues of a user. A dialogue contains a set of utterances, and the objective is to predict the
next utterance given previous utterances. We use the MAML objective for training.
Baselines We use a recently-proposed meta learning dialogue system (Madotto et al., 2019b) as the baseline. We measure the difference between the ground-truth output and model output to evaluate the model performance by PPL (Perplexity) and case-insensitive BLEU score (Papineni et al., 2002).
Implementation Details Before training, the datasets sampled from P is split into meta-training, meta-validation and meta-test dataset. The meta-learner learns how to learn by training and evaluating on the meta-training set. Meta-learning hyper-parameters are tuned on the meta-validation set. The meta-test set measures generalization on new, unseen tasks. We use the BERT-base (Devlin et al., 2019) model as the backbone and tune the parameters in the backbone together with the final softmax layer. For meta training, we use Adam (Kingma & Ba, 2014) with learning rate 10 3, 10 2 for inner and outer loop training, respectively. During the evaluation, for all the models, we used beam search with beam size 4 and length penalty 1.2. These hyper-parameters are selected based on the performance of the meta-validation dataset.
For our method, we create n = 16 softmax head (i.e. a linear transform followed by a softmax layer), share the backbone parameters and select one head for each persona with the lowest loss on the test set for this persona during training, and select the softmax head with the lowest loss on the training set during evaluation.
Result Table 4 shows that our proposed algorithm beats the meta-learning baseline on both the PPL and BLEU measure. We improve the BLEU from 0.77 to 0.91 and PPL from 46.35 to 43.94, respectively.
4.4 Multi-Target Domain Adaptation
Domain adaptation is a powerful approach for learning under distributional shift between training and test data (e.g. Wu et al., 2018; Tzeng et al., 2017). Here, we show that our proposed algorithm can also be applied to multitarget domain adaptation (Yu et al., 2018) using the dataset proposed in Peng et al. (2019). For multi-target domain adaptation, one source domain and m multi-target domain is given. In this experiment, we use the classical domain adaptation method proposed by Tzeng et al. (2017), in which an adversarial net is used to learn the adaptation from the latent space in the source domain.
We first pretrain a CNN using labeled image examples from the source domain and denote the backbone as g. Next, for the target domain, we perform adversarial adaptation by learning a map after g such that a discriminator that sees source examples g(·) and target examples (g(·)) cannot reliably predict their domain label. During the evaluation, target images are mapped with backbone g followed by the learned map to the shared feature space
and classified by the final-layer classifier trained on the source domain.
Our Method After pretraining a backbone on the source domain, We consider to use n adversarial nets {✓i}ni=1 as domain adaptors to match the representation of the source domain and target domains. Each ✓i = ( i, i) contains two part of parameters where i is a feature map and i is a discriminator. i is an MLP whose input and output have the same dimension and i maps the input to a onedimension scalar followed by a sigmoid function.
Denote z = g(x) the features extracted by the backbone and S the source domain, `(✓i, D) equals to
Ez=g(x),x⇠D ⇢ log i( i(z))+ log(1 i( i(z))
Ez=g(x),x⇠S ⇢ log i(z)+ log(1 i(z)) ,
(7) is an adversarial loss which forces the discriminator to make uniform prediction.
Baselines We compare our method with three simple baselines. One is using a shared adversarial domain adaptors for all the target domains. Another is using n different domain adaptors for m target domains. The third baseline is randomly assigning domains with models for each iteration during training and average all the outputs for all models during evaluation.
Experiment Settings We use the DomainNet dataset proposed by Peng et al. (2019). DomainNet contains 6 styles, 345 classes and 569,010 images. We create a subset of DomainNet to do experiments. We sample 25 classes in the same style and sample 300 images for each class. For each sample subset (domain), we use 5 different data shifts (e.g. brightness, fog, snow, MotionBlur, Gaussian noise) (Hendrycks et al., 2019) to create new domains. Finally, we obtain 30 different domains. We randomly select one domain data as the source domain and the rest as target domains during experiments. For the neural architecture, we use a standard ResNet-18 (He et al., 2016) to train on the source domain, a three-layer MLP as i and another three-layer MLP as i. During training and testing, we resize the image into 64⇥ 64 size. During training, we use standard data augmentation (mirror and flip).
Results As demonstrated in Table 5, compared to sharing one domain adaptor for all the domains, using a domain-specific domain adaptor improves the accuracy from 39.5% to 41.8%. With our proposed method, we can further improve the 41.8% accuracy to 44.3%. In Table 5, we also demonstrate that randomly aligning different domains hurts the performance. It indicates that in this setting our method is much better than ensemble multiple models. We further set up an ablation study on the number of heads. As shown in Figure 4, similar to the results in Figure 3, increasing the number of heads can always improve the training loss (i.e., discriminator loss in (7)). Here, increasing n makes the negative discriminator loss higher indicates that it mixes the two domains successfully. However, the test loss increases once n is too large. It demonstrates that our argmax centroids method implicitly serves as a regularization by sharing the same linear map for multiple similar domains. Sharing the same linear map increases the number of training data for each ✓, and therefore avoids overfitting.

heading: 5 Conclusion

text:
In this work, we propose a method to estimate the argmax distribution. It can be an alternative for related methods, and we further apply it to many multi-domain and multi-task learning tasks. Aligning similar domains into a same model, the proposed algorithm boost the SOTA performance on several few-shot classification and meta learning tasks. In the concurrent work (Ye & Liu, 2021) we use the centroid learning idea to improve the bootstrap for data uncertainty quantification, in which we establish a rigorous theoretically result showing that the centroid objective function is uniformly close to Wasserstein distance through the whole optimization trajectory induced by a modified gradient descent algorithm. For the next step, we will consider the connection with diversifying models and other topics. We will also apply our method to more meaningful and challenging tasks, e.g. lifelong learning, continual learning.
Acknowledgements The work is conducted in the statistical learning and AI group in computer science department at UT Austin, which is supported in part by CAREER-1846421, SenSE-2037267, EAGER-2041327, and Office of Navy Research, and NSF AI Institute for Foundations of Machine Learning (IFML). We would like to thank the anonymous reviewers for their thoughtful comments and efforts towards improving our manuscript.

title: Argmax Centroids: with Applications to Multi-domain Learning


summaries: This paper investigates multi-objective reinforcement learning (MORL) in the online setting and the so-called preference-free setting, where the preference vector is given by an adversary. It proposes a model-based algorithms for each setting under tabular episodic MDPs, respectively. Both algorithms are shown to attain nearly optimal regret or sample complexity bound.

summaries: The authors propose to study an multi-objective RL in an online, episodic and tabular setting. In each episode, there is an adversarial chosen weight vector $w^k$  revealed to the agent, whose aim is to achieve a sublinear-time regret compared to an oracle who uses the optimal policy every episode. The authors propose the MO-UCBVI algorithm, which incorporate the adversarial chosen weight vectors with the learning approach by the classical UCBVI. Then the authors harness their framework on a recent proposed reward-free exploration problem, and they show that their algorithm's performance is superior to the state-of-the-art.

summaries: This paper studies the multi-objective reinforcement learning (MORL) problem where the reward function is an inner product of two d-dimensional vectors, an objective vector and a preference vector. Two algorithms have been proposed for known and not known preference vectors. Both algorithms are proved to achieve sub-linear regrets.

summaries: This work studies the multi-objective RL (MORL) with unknown transition, where the reward function can be parameterized with d-dimensional preference vectors. In the beginning of each episode, an adversary selects the weight vector and reveals it to the learner, the learner then selects corresponding policy and suffers a regret comparing with the optimal policies with respect to the given preference vector.   Besides this online MORL setting, the authors further study a preference-free exploration (PFE) setting where the learner manually separates the learning and planning phases and her performance is measured by the number of samples that are required to ensure PAC-bound. Then, the authors introduce a lower bound for PFE, which shows there is only an H factor loose.

summaries: This paper tackles the reinforcement learning problem in a multi-objective and online setting. Two different cases are considered: (i) when preferences over the multiple objectives are given at the start of each episode and (ii) when preferences are unknown and the environment needs to be explored in preparation for any arbitrary preferences. For both cases, the paper proposes optimal solutions (up to logarithmic factors, and a factor of $H$ in the second case).

abstractText: In this paper we consider multi-objective reinforcement learning where the objectives are balanced using preferences. In practice, the preferences are often given in an adversarial manner, e.g., customers can be picky in many applications. We formalize this problem as an episodic learning problem on a Markov decision process, where transitions are unknown and a reward function is the inner product of a preference vector with pre-specified multi-objective reward functions. We consider two settings. In the online setting, the agent receives a (adversarial) preference every episode and proposes policies to interact with the environment. We provide a model-based algorithm that achieves a nearly minimax optimal regret bound Õ (√ min{d, S} ·H2SAK ) , where d is the number of objectives, S is the number of states, A is the number of actions, H is the length of the horizon, and K is the number of episodes. Furthermore, we consider preference-free exploration, i.e., the agent first interacts with the environment without specifying any preference and then is able to accommodate arbitrary preference vector up to error. Our proposed algorithm is provably efficient with a nearly optimal trajectory complexity Õ ( min{d, S} ·HSA/ 2 ) . This result partly resolves an open problem raised by Jin et al. [2020].

authors:
Axel Abels
Diederik M Roijers
Tom Lenaerts
Ann Nowé
Denis Steckelmacher

title: Dynamic weights in multi-objective deep reinforcement learning

venue: arXiv preprint arXiv:1809.07803,

authors:
Joshua Achiam
David Held
Aviv Tamar
Pieter Abbeel

title: Constrained policy optimization

authors:
Mohammad Gheshlaghi Azar
Ian Osband
Rémi Munos

title: Minimax regret bounds for reinforcement learning

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

authors:
Kianté Brantley
Miroslav Dudik
Thodoris Lykouris
Sobhan Miryoosefi
Max Simchowitz
Aleksandrs Slivkins
Wen Sun

title: Constrained episodic reinforcement learning in concave-convex and knapsack settings

title: Exploration-exploitation trade-off in reinforcement learning on online markov decision processes with global concave rewards

venue: arXiv preprint arXiv:1905.06466,

authors:
Christoph Dann
Tor Lattimore
Emma Brunskill

title: Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning

venue: arXiv preprint arXiv:1703.07710,

authors:
Yonathan Efroni
Shie Mannor
Matteo Pirotta

title: Exploration-exploitation in constrained mdps

venue: arXiv preprint arXiv:2003.02189,

authors:
Mahmoud El Chamie
Yue Yu
Behçet Açıkmeşe
Masahiro Ono

title: Controlled markov processes with safety state constraints

venue: IEEE Transactions on Automatic Control,

authors:
Jaime F Fisac
Anayo K Akametalu
Melanie N Zeilinger
Shahab Kaynama
Jeremy Gillula
Claire J Tomlin

title: A general safety framework for learning-based control in uncertain robotic systems

authors:
Javier Garcıa
Fernando Fernández

title: A comprehensive survey on safe reinforcement learning

venue: Journal of Machine Learning Research,

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

title: Is q-learning provably efficient

venue: In Advances in Neural Information Processing Systems,

authors:
Chi Jin
Tiancheng Jin
Haipeng Luo
Suvrit Sra
Tiancheng Yu

title: Learning adversarial mdps with bandit feedback and unknown transition, 2019

authors:
Chi Jin
Akshay Krishnamurthy
Max Simchowitz
Tiancheng Yu

title: Reward-free exploration for reinforcement learning

venue: arXiv preprint arXiv:2002.02794,

authors:
William B Johnson
Joram Lindenstrauss

title: Extensions of lipschitz mappings into a hilbert space

venue: Contemporary mathematics,

authors:
Emilie Kaufmann
Pierre Ménard
Omar Darwiche Domingues
Anders Jonsson
Edouard Leurent
Michal Valko

title: Adaptive reward-free exploration

venue: arXiv preprint arXiv:2006.06294,

authors:
Andreas Maurer
Massimiliano Pontil

title: Empirical bernstein bounds and sample variance penalization

venue: arXiv preprint arXiv:0907.3740,

authors:
Pierre Ménard
Omar Darwiche Domingues
Anders Jonsson
Emilie Kaufmann
Edouard Leurent
Michal Valko

title: Fast active learning for pure exploration in reinforcement learning

venue: arXiv preprint arXiv:2007.13442,

authors:
Hossam Mossalam
Yannis M Assael
Diederik M Roijers
Shimon Whiteson

title: Multi-objective deep reinforcement learning

venue: arXiv preprint arXiv:1610.02707,

authors:
Sriraam Natarajan
Prasad Tadepalli

title: Dynamic preferences in multi-criteria reinforcement learning

venue: In Proceedings of the 22nd international conference on Machine learning,

authors:
Gergely Neu
Andras Gyorgy
Csaba Szepesvári

title: The adversarial stochastic shortest path problem with unknown transition probabilities

venue: In Artificial Intelligence and Statistics,

authors:
Diederik M Roijers
Peter Vamplew
Shimon Whiteson
Richard Dazeley

title: A survey of multiobjective sequential decision-making

venue: Journal of Artificial Intelligence Research,

authors:
Aviv Rosenberg
Yishay Mansour

title: Online convex optimization in adversarial markov decision processes

venue: arXiv preprint arXiv:1905.07773,

authors:
Richard S Sutton
Andrew G Barto

title: Reinforcement learning: An introduction

venue: MIT press,

authors:
Akifumi Wachi
Yanan Sui

title: Safe reinforcement learning in constrained markov decision processes

authors:
Ruosong Wang
Simon S Du
Lin F Yang
Ruslan Salakhutdinov

title: On reward-free reinforcement learning with linear function approximation

venue: arXiv preprint arXiv:2006.11274,

authors:
Runzhe Yang
Xingyuan Sun
Karthik Narasimhan

title: A generalized algorithm for multi-objective reinforcement learning and policy adaptation

authors:
Andrea Zanette
Emma Brunskill

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

authors:
Xuezhou Zhang
Yuzhe Ma
Adish Singla

title: Task-agnostic exploration in reinforcement learning, 2020a

authors:
Zihan Zhang
Simon S Du
Xiangyang Ji

title: Nearly minimax optimal reward-free reinforcement learning

venue: arXiv preprint arXiv:2010.05901,

text:
min{d, S} ·H2SAK ) , where d is the number of objectives, S is the number
of states, A is the number of actions, H is the length of the horizon, and K is the number of episodes. Furthermore, we consider preference-free exploration, i.e., the agent first interacts with the environment without specifying any preference and then is able to accommodate arbitrary preference vector up to error. Our proposed algorithm is provably efficient with a nearly optimal trajectory complexity Õ ( min{d, S} ·H3SA/ 2 ) . This result partly resolves an open problem raised by Jin et al. [2020].

heading: 1 Introduction

text:
In single-objective reinforcement learning (RL), a scalar reward is pre-specified and an agent learns a policy to maximize the long-term cumulative reward [Sutton and Barto, 2018]. However, in many real-world applications, we need to optimize multiple objectives for the same (unknown) environment, even when these objectives are possibly contradicting [Roijers et al., 2013]. For example, in an autonomous driving application, each passenger may have a different preference of driving styles: some of the passengers prefer a very steady riding experience while other passengers enjoy the fast acceleration of the car. Therefore, traditional single-objective RL approach may fail to be applied in such scenarios. One way to tackle this issue is the multi-objective reinforcement learning (MORL) [Roijers et al., 2013, Yang et al., 2019, Natarajan and Tadepalli, 2005, Abels et al., 2018]
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
method, which models the multiple objectives by a vectorized reward, and an additional preference vector to specify the relative importance of each objective. The agent of MORL needs to find policies to optimize the cumulative preference-weighted rewards.
If the preference vector is fixed or drawn from a fixed distribution, MORL is no more challenging than single-objective RL, as we can predict the objective to be optimized and apply (variants of) single-objective RL algorithms (e.g., [Azar et al., 2017]). However, more often in practice, the preference vector (under which the weighted objective needs to be optimized) is:
(i) adversarially provided, (ii) or even not available in the learning phase.
Once more taking the autonomous driving application as example: (i) the intelligent system needs to adapt driving configurations to accommodate every customer, even though the next customer can have picky preference that is unpredictable; (ii) when the intelligent system is under development, the future customer cannot be known in advance, nonetheless, when the system is deployed, it has to be capable to accommodate any potential customer who rides the car. Such MORL examples are common, to name a few beyond the autonomous driving one: medical treatment must take care of every patient even in very rare health conditions; an education system should accommodate every student according to his/her own characteristics; and emergency response systems have to be responsible in all extreme cases. Due to these exclusive challenges that have not appeared in single-objective RL, new sample-efficient algorithms for MORL need to be developed, as well as their theoretical grounds need to be established.
In this work, we study provable sample-efficient algorithms for MORL that resolve the aforementioned issues. Specifically, we consider MORL on a finite-horizon Markov decision process (MDP) with an unknown transition kernel, S states, A actions, H steps, and d reward functions that represent the d difference objectives. We investigate MORL problems in two paradigms: (i) online MORL (where the preferences are adversarially presented), and (ii) preference-free exploration (where the preferences are not available in the learning/exploration phase). The two settings and our contributions are explained respectively in the following.
Setting (i): Online MORL. We first consider an online learning problem to capture the challenge that preference vectors could be adversarially provided in MORL. In the beginning of each episode, the MORL agent is provided (potentially adversarially) with a preference vector, and the agent interacts with the unknown environment to collect data and rewards (that is specified by the provided preference). The performance of an algorithm is measured by the regret, i.e., the difference between the rewards collected by the agent and those would be collected by a theoretically optimal agent (who could use varying policies that adapt to the preferences). This setting generalizes the classical online single-objective RL problem [Azar et al., 2017] (where d = 1).
Contribution (i). For online MORL, we provide a provably efficient algorithm with a regret upper bound Õ (√ min{d, S} ·H2SAK ) 1, where K is the number of episodes for interacting with the en-
vironment. Furthermore, we show an information-theoretic lower bound Ω (√ min{d, S} ·H2SAK ) for online MORL. These bounds together show that, ignoring logarithmic factors, our algorithm resolves the online MORL problems optimally.
Setting (ii): Preference-Free Exploration. We further consider an unsupervised MORL problem to capture the issue that preferences could be hard to obtain in the training phase. The MORL agent first interacts with the unknown environment in the absence of preference vectors; afterwards, the agent is required to use the collected data to compute near-optimal policies for an arbitrarily specified preference vector. The performance is measured by the sample complexity, i.e., the minimum amount of trajectories that an MORL agent needs to collect during exploration in order to be near-optimal during planning. This setting extends the recent proposed reward-free exploration problem [Jin et al., 2020] to MORL.
Contribution (ii). For preference-free exploration, we show that a simple variant of the proposed online algorithm can achieve nearly optimal sample complexity. In particular, the algorithm achieves a sample complexity upper bound Õ ( min{d, S} ·H3SA/ 2 ) where is the tolerance of the planning
error; and we also show a sample complexity lower bound, Ω ( min{d, S} ·H2SA/ 2 ) , for any
1We use Õ(·) to hide (potential) polylogarithmic factors in O(·), i.e., Õ(n) := O(n logk n) for sufficiently large n and some absolute constant k > 0.
algorithm. These bounds suggest that our algorithm is optimal in terms of d, S, A, up to logarithmic factors. It is also worth noting that our results for preference-free exploration partly answer an open question raised by Jin et al. [2020]: reward-free RL is easier when the unknown reward functions enjoy low-dimensional representations (as in MORL).
Paper Layout. The remaining paper is organized as follows: the preliminaries are summarized in Section 2; then in Section 3, we formally introduce the problem of online MORL, our algorithm and its regret upper and lower bounds; then in Section 4, we turn to study the preference-free exploration problem in MORL, where we present an exploration algorithm with sample complexity analysis (with both upper bound and lower bound), and compare our results with existing results for related problems; finally, the related literature is reviewed in Section 5 and the paper is concluded by Section 6.

heading: 2 Preliminaries

text:
We specify a finite-horizon Markov decision process (MDP) by a tuple of (S,A, H,P, r,W). S is a finite state set where |S| = S. A is a finite action set where |A| = A. H is the length of the horizon. P(· | x, a) is a stationary, unknown transition probability to a new state for taking action a at state x. r = {r1, . . . , rH}, where rh : S ×A → [0, 1]d represents a d-dimensional vector rewards function that captures the d objectives2. W := { w ∈ [0, 1]d, ‖w‖1 = 1 } specifies the set of all possible preference vectors3, where each preference vector w ∈ W induces a scalar reward function by4 rh(·, ·) = 〈w, rh(·, ·)〉 for h = 1, . . . ,H . A policy is represented by π := {π1, . . . , πH}, where each πh(·) maps a state to a distribution over the action set. Fixing a policy π, we will consider the following generalized Q-value function and generalized value function:
Qπh(x, a;w) := E [∑H j=h〈w, rj(xj , aj)〉 ∣∣xh = x, ah = a], V πh (x;w) := Qπh(x, πh(x);w),
where xj ∼ P (· | xj−1, aj−1) and aj ∼ πj(xj) for j > h. Note that compared with the typical Q-value function (or the value function) used in single-objective RL, here the generalized Q-value function (or the generalized value function) takes the preference vector as an additional input, besides the state-action pair. Fixing a preference w ∈ W , the optimal policy under w is defined as π∗w := arg maxπ V π 1 (x1;w). For simplicity, we denote
Q∗h(x, a;w) := Q π∗w h (x, a;w), V ∗ h (x;w) := V π∗w h (x;w) = maxa Q∗h(x, a;w).
The following abbreviation is adopted for simplicity: PV πh |x,a,w := ∑ y∈SP(y|x, a)V πh (y;w),
and similar abbreviations will be adopted for variants of probability transition (e.g., the empirical transition probability) and variants of value function (e.g., the estimated value function). Finally, we remark that the following Bellman equations hold for the generalized Q-value functions{ Qπh(x, a;w) = 〈w, rh(x, a)〉+ PV πh+1 ∣∣ x,a,w ,
V πh (x;w) = Q π h(x, πh(x);w);
{ Q∗h(x, a;w) = 〈w, rh(x, a)〉+ PV ∗h+1 ∣∣ x,a,w ,
V ∗h (x;w) = maxaQ ∗ h(x, a;w).
With the above preparations, we are ready to discuss our algorithms and theory for online MORL (Section 3) and preference-free exploration (Section 4).

heading: 3 Online MORL

text:
Problem Setups. The online setting captures the first difficulty in MORL, where the preference vectors can be adversarially provided to the MORL agent. Formally, the MORL agent interacts with
2For the sake of presentation, we discuss bounded deterministic reward functions in this work. The techniques can be readily extended to stochastic reward settings.
3The condition that w ∈ [0, 1]d is only assumed for convenience. Our results naturally generalize to preference vectors that are entry-wisely bounded by absolute constants.
4The linear scalarization method can be generalized. See more discussions in Section 3.2, Remark 2.
an unknown environment through Protocol 1: at the beginning of the k-th episode, an adversary selects a preference vector wk and reveals it to the agent; then starting from a fixed initial state5 x1, the agent draws a trajectory from the environment by recursively taking an action and observing a new state, and collects rewards from the trajectory, where the rewards are scalarized from the vector rewards by the given preference. The agent’s goal is to find the policies that maximize the cumulative rewards. Its performance will be measured by the following regret: suppose the MORL agent has interacted with the environment through Protocol 1 for K episodes, where the provided preferences are {wk}Kk=1 and the adopted policies are {πk}Kk=1 correspondingly, we consider the regret of the collected rewards (in expectation) competing with the theoretically maximum collected rewards (in expectation):
regret(K) := ∑K k=1V ∗ 1 (x1;w
k)− V πk1 (x1;wk). (1) Clearly, the regret (1) is always non-negative, and a smaller regret implies a better online performance. We would like to highlight that the regret (1) allows the theoretically optimal agent to adopt varying policies that adapt to the preferences.
Protocol 1 Environment Interaction Protocol Require: MDP(S,A, H,P, r,W) and online agent
1: agent observes (S,A, H, r,W) 2: for episode k = 1, 2, . . . ,K do 3: agent receives an initial state xk1 = x1, and a preference w
k (from an adversary) 4: for step h = 1, 2, . . . ,H do 5: agent chooses an action akh, and collects reward 〈wk, rh(xkh, akh)〉 6: agent transits to a new state xkh+1 ∼ P(· | xkh, akh) 7: end for 8: end for
Connections to Online Single-Objective RL. The online regret minimization problems are well investigated in the context of single-objective RL (see, e.g., [Azar et al., 2017, Jin et al., 2018]). In both online single-objective RL and our studied online MORL, it is typical to assume that the transition probability P is the only unknown information about the environment since estimating a stochastic reward is relatively easy (see, e.g., [Azar et al., 2017, Jin et al., 2018]). In particular, single-objective RL is a special case of MORL in the online setting, where the preference is fixed during the entire learning process (i.e., wk := w for all k) — therefore an online MORL algorithm naturally applies to single-objective RL. However, the reverse is not true as that in MORL the preference vectors can change over time and are potentially adversarial.
Comparison with Single-Objective Stochastic and Adversarial Reward Setting. The essential difficulty of MORL is further reflected in the regret (1). Specifically, the regret (1) compares the perfor-
mance of the agent’s policies to a sequence of optimal policy under each given preference, which could vary over time. However, in online single-objective RL, either with known/stochastic rewards [Azar et al., 2017, Jin et al., 2018] or adversarial rewards [Rosenberg and Mansour, 2019, Jin et al., 2019], the benchmark policy is supposed to be fixed over time (the best policy in the hindsight). This difference suggests that online MORL could be more challenging than online single-objective RL, as a harder performance measurement is adopted. More specifically, when measured by regret
5Without loss of generality, we fix the initial state; otherwise we may as well consider an MDP with an external initial state x0 with zero reward for all actions, and a transition P0(· | x0, a) = P0(·) for all action a. This is equivalent to our setting by letting the horizon length H be H + 1.
(1), existing algorithms for single-objective RL (e.g., [Azar et al., 2017]) easily suffer a ∝ Θ(K) regret when the sequence of preferences is adversarially designed; in contrast, we will show an MORL algorithm that experiences at most ∝ Õ( √ K) regret under any sequence of preferences. A numerical simulation of this issue is presented in Figure 1.

heading: 3.1 A Sample-Efficient Online Algorithm

text:
In this part we introduce an algorithm for online MORL, called multi-objective upper confidence bound value iteration (MO-UCBVI). A simplified verison of MO-UCBVI is presented as Algorithm 1, and a more advanced version (Algorithm 4) can be found in Appendix B. Our algorithm is inspired by UCBVI [Azar et al., 2017] that achieves minimax regret bound in online single-objective RL.
Algorithm 1 MO-UCBVI 1: initialize historyH0 = ∅ 2: for episode k = 1, 2, . . . ,K do 3: Nk(x, a), P̂k(y | x, a)← Empi-Prob(Hk−1) 4: compute bonus bk(x, a) := c · √ min{d,S}H2ι Nk(x,a) , where ι = log(HSAK/δ) and c is a constant
5: receive a preference wk
6: {Qkh(x, a;wk)}Hh=1 ← UCB-Q-Value(P̂k, wk, bk) 7: receive initial state xk1 = x1 8: for step h = 1, 2, . . . ,H do 9: take action akh = arg maxaQ k h(x k h, a;w
k), and obtain a new state xkh+1 10: end for 11: update historyHk = Hk−1 ∪ {xkh, akh}Hh=1 12: end for
13: Function Empi-Prob 14: Require: historyHk−1 15: for (x, a, y) ∈ S ×A× S do 16: Nk(x, a, y) := #{(x, a, y) ∈ Hk−1}, and Nk(x, a) := ∑ y N k(x, a, y) 17: if Nk(x, a) > 0 then 18: P̂k(y | x, a) = Nk(x, a, y)/Nk(x, a) 19: else 20: P̂k(y | x, a) = 1/S 21: end if 22: end for 23: return Nk(x, a) and P̂k(y | x, a)
24: Function UCB-Q-Value 25: Require: empirical transition P̂k, preference wk, and bonus bk(x, a) 26: set V kH+1(x;w
k) = 0 27: for step h = H,H − 1, . . . , 1 do 28: for (x, a) ∈ S ×A do 29: Qkh(x, a;w k) = min { H, 〈wk, rh(x, a)〉+ bk(x, a) + P̂khV kh+1 ∣∣ x,a,wk
} 30: V kh (x;w k) = maxa∈AQ k h(x, a;w
k) 31: end for 32: end for 33: return { Qkh(x, a;w k) }H h=1
In Algorithm 1, the agent interacts with the environment according to Protocol 1, and use an optimistic policy to explore the unknown environment and collect rewards. The optimistic policy is a greedy policy with respect to an optimistic estimation to the value function, UCB-Q-Value (lines 6 and 9). Specifically, UCB-Q-Value is constructed to maximize the cumulative reward, which is scalarized by the current preference, through dynamic programming over an empirical transition probability (line 24). The empirical transition probability is inferred from the data collected so far (lines 3 and
13), which might not be accurate if a state-action pair has not yet been visited for sufficient times. To mitigate this inaccuracy, UCB-Q-Value utilizes an extra exploration bonus (lines 4 and 29) so that: (i) UCB-Q-Value never under-estimates the optimal true value function, for whatever preference vector (and with high probability); and (ii) the added bonus shrinks quickly enough (as the corresponding state-action pair continuously being visited) so that the over-estimation is under control. The overall consequence is that: MO-UCBVI explores the environment via a sequence of optimistic policies, in order to collect rewards under a sequence of adversarially provided preferences; since the policies are optimistic for any preference, the incurred regret would not exceed the total amount of added bonus; and since the bonus decays fast, their sum up would be sublinear (with respect to the number of episodes played). Therefore MO-UCBVI only suffers a sublinear regret, even when the preferences are adversarially presented. The above intuition is formalized in the next part.

heading: 3.2 Theoretical Analysis

text:
The next two theorems justify regret upper bounds for MO-UCBVI and a regret lower bound for online MORL problems, respectively. Theorem 1 (Regret bounds for MO-UCBVI). Suppose K is sufficiently large. Then for any sequence of the incoming preferences {wk}Kk=1, with probability at least 1− δ: • the regret (1) of MO-UCBVI (see Algorithm 1) satisfies
regret(K) ≤ O (√ min{d, S} ·H3SAK log(HSAK/δ) ) ;
• and the regret (1) of a Bernstein-variant MO-UCBVI (see Algorithm 4 in Appendix B) satisfies regret(K) ≤ O (√ min{d, S} ·H2SAK log2(HSAK/δ) ) .
Theorem 2 (A regret lower bound for MORL). There exist some absolute constants c,K0 > 0, such that for any K > K0, any MORL algorithm that runs K episodes, there is a set of MOMDPs and a sequence of (necessarily adversarially chosen) preferences vectors such that
E[regret(K)] ≥ c · √
min {d, S} ·H2SAK, where the expectation is taken with respect to the randomness of choosing MOMDPs and the randomness of the algorithm for collecting dataset. Remark 1. When d = 1, MORL recovers the single-objective RL setting, and Theorem 1 recovers existing nearly minimax regret bounds for single-objective RL [Azar et al., 2017, Zanette and Brunskill, 2019]. Moreover, the lower bound in Theorem 2 implies that our upper bound in Theorem 1 is tight ignoring logarithm terms. Interestingly, the lower bound suggests MORL with d > 2 is truly harder than single objective RL (corresponding to d = 1) as the sequence of preferences can be adversarially chosen. Remark 2. Theorem 1 (as well as our other theorems) applies to general scalarization methods besides the linear one as adopted by Algorithm 1 and many other MORL papers [Yang et al., 2019, Roijers et al., 2013, Natarajan and Tadepalli, 2005, Abels et al., 2018]. In particular, our results apply to scalarization functions rh(·, ·) = f(rh(·, ·);w) that are (1) deterministic, (2) Lipschitz continuous for w, and (3) bounded between [0, 1] (which can be relaxed). This will be clear from proofs in Appendix B, where we treat the potentially adversarially given preferences by a covering argument and union bound, and these techniques are not dedicated to linear scalarization function and can be easily extended to more general cases.
The proof of Theorem 1 leverages standard analysis procedures for single-objective RL [Azar et al., 2017, Zanette and Brunskill, 2019], and a covering argument with an union bound to tackle the challenge of adversarial preferences. Th rigorous proof is included in Appendix B.
Specifying an adversarial process of providing preferences is the key challenge for proving Theorem 2. To handle this issue, we use reduction techniques and utilize a lower bound that we will show shortly for preference-free exploration problems. We refer the readers to Theorem 4 and Appendix E for more details.

heading: 4 Preference-Free Exploration

text:
Problem Setups. Preference-free exploration (PFE) captures the second difficulty in MORL: the preference vector might not be observable when the agent explores the environment. Specifically, PFE
consists of an exploration phase and a planning phase. Similarly as in the online setting, the transition probability is hidden from the MORL agent. In the exploration phase, the agent interacts with the unknown environment to collect samples, however the agent has no information about the preference vectors at this point. Afterwards PFE switches to the planning phase, where the agent is prohibited to obtain new data, and is required to compute near-optimal policy for any preference-weighted reward functions. Since this task is no longer in an online fashion, we turn to measure the performance of a PFE algorithm by the minimum number of required trajectories (in the exploration phase) so that the algorithm can behave near-optimally in the planning phase. This is made formal as follows: a PFE algorithm is called ( , δ)-PAC (Probably Approximately Correct), if
P { ∀w ∈ W, V ∗1 (x1;w)− V πw 1 (x1;w) ≤ } ≥ 1− δ,
where πw is the policy outputted by the PFE algorithm for input preference w, then the sample complexity of a PFE algorithm is defined by the least amount of trajectories it needs to collect in the exploration phase for being ( , δ)-PAC in the planning phase.
Connections to Reward-Free Exploration. PFE problem is a natural extension to the recent proposed reward-free exploration (RFE) problem [Jin et al., 2020, Kaufmann et al., 2020, Wang et al., 2020, Ménard et al., 2020, Zhang et al., 2020b]. Both problems consist of an exploration phase and a planning phase; the difference is in the planning phase: in RFE, the agent needs to be able to compute near-optimal policies for all reward functions, while in PFE, the agent only needs to achieve that for all preference-weighted reward functions, i.e., the reward functions that can be represented as the inner product of a d-dimensional preference vectors and the d-dimensional vector rewards functions (i.e., the d objectives in MORL). A PFE problem reduces to a RFE problem if d = SA such that every reward function can be represented as a preference-weighted reward function. However, if d SA, it is conjectured by Jin et al. [2020] that PFE can be solved with a much smaller sample complexity than RFE. Indeed, in the following part we show an algorithm that improves a ∝ Õ(S2) dependence for RFE to ∝ Õ(min{d, S} · S) dependence for PFE, in terms of sample complexity.

heading: 4.1 A Sample-Efficient Exploration Algorithm

text:
We now present a simple variant of MO-UCBVI that is sample-efficient for PFE. The algorithm is called preference-free upper confidence bound exploration (PF-UCB), and is discussed separately as in the exploration phase (Algorithm 2) and in the planning phase (Algorithm 3) in below.
Algorithm 2 PF-UCB (Exploration) 1: initialize historyH0 = ∅ 2: for episode k = 1, 2, . . . ,K do 3: Nk(x, a), P̂k(y | x, a)← Empi-Prob(Hk−1) 4: compute bonus ck(x, a) := H
2S 2Nk(x,a) + 2bk(x, a) for bk(x, a) defined in Algorithms 1 or 3
5: {Qkh(x, a)}Hh=1 ← UCB-Q-Value(P̂k, w = 0, ck) 6: receive initial state xk1 = x1 7: for step h = 1, 2, . . . ,H do 8: take action akh = arg maxaQ k h(x k h, a), and obtain a new state x k h+1
9: end for 10: update historyHk = Hk−1 ∪ {xkh, akh}Hh=1 11: end for
Algorithm 2 presents our PFE algorithm in the exploration phase. Indeed, Algorithm 2 is a modified MO-UCBVI (Algorithm 1) by setting the preference to be zero (Algorithm 2, line 5), and slightly enlarging the exploration bonus (Algorithm 2, line 4). The intention of an increased exploration bonus will be made clear later when we discuss the planning phase. With a zero preference vector, the UCB-Q-Value in Algorithm 2 will identify a trajectory along which the cumulative bonus (instead of the cumulative rewards) is maximized (with respect to the empirical transition probability). Also note that the bonus function (Algorithm 2, line 4) is negatively correlated with the number of visits to a state-action pair. Hence the greedy policy with respect to the zero-preference UCB-Q-Value tends to visit the state-actions pairs that are associated with large bonus, i.e., those that have been visited
Algorithm 3 PF-UCB (Planning) Require: historyHK , preference vector w
1: for k = 1, 2, . . . ,K do 2: Nk(x, a), P̂k(y|x, a)← Empi-Prob(Hk−1) 3: compute bonus bk(x, a) := c · √ min{d,S}H2ι Nk(x,a) where ι = log(HSAK/δ) and c is a constant
4: {Qkh(·, ·;w)}Hh=1 ← UCB-Q-Value(P̂k, w, bk) 5: infer greedy policy πkh(x) = arg maxaQ k h(x, a;w) 6: end for 7: return π drawn uniformly from {πk}Kk=1
for less times. In sum, Algorithm 2 explores the unknown environment “uniformly”, without the guidance of preference vectors.
Then Algorithm 3 shows our PFE algorithm in the planning phase. Given any preference vector, Algorithm 3 computes a sequence of optimistically estimated value functions based on the data collected from the exploration phase, and then outputs a greedy policy with respect to a randomly drawn optimistic value estimation. Note that the bonus in Algorithm 3 is set as the one in Algorithm 1, and recall that the bonus in Algorithm 2 is an enlarged one. The relatively large bonus in the exploration phase guarantees that the regret in the planning phase never exceeds that in the exploration phase. On the other hand, based on Theorem 1 for MO-UCBVI (Algorithm 1), we have already known that the exploration algorithm (Algorithm 2), a modified Algorithm 1, suffers at most Õ( √ K) regret, hence the planning algorithm (Algorithm 3) experiences at most Õ(1/ √ K) error. The next part rigorously justifies these discussions.

heading: 4.2 Theoretic Analysis

text:
We first provide Theorem 3 to justify the trajectory complexity of Algorithms 2 and 3 in the PFE setting; then we present Theorem 4 that gives an information-theoretic lower bound on the trajectory complexity for any PFE algorithm. Theorem 3 (A trajectory complexity of PF-UCB). Suppose > 0 is sufficiently small. Then for PF-UCB (Algorithm 2) run for
K = O ( min{d, S} ·H3SAι/ 2 ) , where ι := log(HSA/(δ )),
episodes, PF-UCB (Algorithm 3) is ( , δ)-PAC.
Theorem 4 (A lower bound for PFE). There exist absolute constants c, 0 > 0, such that for any 0 < < 0, there exists a set of MOMDPs such that any PFE algorithm that is ( , 0.1)-PAC on them, it needs to collect at least
K ≥ Ω ( min {d, S} ·H2SA/ 2 ) trajectories in expectation (with respect to the randomness of choosing MOMDPs and the exploration algorithm).
Remark 3. According to Theorems 3 and 4, the trajectory complexity of PF-UCB is optimal for d, S,A, ignoring logarithmic factors, but is an H factor loose compared with the lower bound. This is because the current Algorithm 2 utilizes a preference-independent, Hoeffding-type bonus since the preference vector is not available during exploration. We leave it as an open problem to further remove this gap about H .
Proof Sketch of Theorem 3. Theorem 3 is obtained in three procedures. (1) We first observe the total regret incurred by Algorithm 2 is Õ (√ min {d, S}H3SAK ) according to Theorem 1. (2) Then utilizing the enlarged exploration bonus, we show that in each episode, the planning error is at most constant times of the incurred exploration error. (3) Thus the averaged planning error is at most Õ (√ min {d, S}H3SA/K ) as claimed. A complete proof is deferred to Appendix C.
Note that the second argument is motivated by [Zhang et al., 2020a, Wang et al., 2020]. However in their original paper, a brute-force union bound over all possible value functions are required to obtain similar effect, due to the limitation of model-free algorithm [Zhang et al., 2020a] (see Appendix F
for more details) or linear function approximation [Wang et al., 2020]. This will cause a loose, ∝ Õ(S2) complexity in the obtained bound. Different from their approach, we carefully manipulate a lower order term to avoid union bounding all value functions during the second argument. As a consequence we obtain a near-tight ∝ Õ(min{d, S} · S) dependence in the final bound. We believe this observation has broader application in the analysis of similar RL problems.
Proof Sketch of Theorem 4. We next introduce the idea of constructing the hard instance that witnesses the lower bound in Theorem 4. A basic ingredient is the hard instance given by Jin et al. [2020]. However, this hard instance is invented for RFE, where the corresponding lower bound is K ≥ Ω ( H2S2A/ 2 ) . Note this lower bound cannot match the upper bound in Theorem 3 in terms of d and S. In order to develop a dedicated lower bound for PFE, we utilize Johnson–Lindenstrauss Lemma [Johnson and Lindenstrauss, 1984] to refine the hard instance in [Jin et al., 2020], and successfully reduce a factor S to min {d, S} in their lower bound, which gives the result in Theorem 4. We believe that the idea to refine RL hard instance by Johnson–Lindenstrauss Lemma is of broader interests. A rigorous proof is deferred to Appendix D.
Application in Reward-Free Exploration. By setting d = SA and allowing arbitrary reward functions, PFE problems reduce to RFE problems. Therefore as a side product, Theorem 3 implies the following results for RFE problems on stationary or non-stationary MDPs6:
Corollary 5. Suppose > 0 is sufficiently small. Consider the reward-free exploration problems on a stationary MDP. Suppose PF-UCB (Algorithm 2) is run for
K = O ( H3S2Aι/ 2 ) , where ι := log(HSA/(δ )),
episodes, then PF-UCB (Algorithm 3) is ( , δ)-PAC. Moreover, if the MDP is non-stationary, the above bound will be revised to K = O ( H4S2Aι/ 2 ) .
Remark 4. When applied to RFE, PF-UCB matches the rate shown in [Kaufmann et al., 2020] and improves an H factor compared with [Jin et al., 2020] (for both stationary and non-stationary MDPs), but is anH factor loose compared with the current best rates, [Ménard et al., 2020] (for non-stationary MDPs) and [Zhang et al., 2020b] (for stationary MDPs). However we highlight that our results are superior in the context of PFE, since PF-UCB adapts with the structure of the rewards. In specific, if rewards admit a d-dimensional feature for d < S, PF-UCB only needs ∝ Õ(min{d, S} · S) samples, but the above methods must explore the whole environment with a high precision which consumes ∝ Õ(S2) samples.
Application in Task-Agnostic Exploration. PFE is also related to task-agnostic exploration (TAE) [Zhang et al., 2020a]: in PFE, the agent needs to plan for an arbitrary reward function from a fixed and bounded d-dimensional space; and in TAE, the agent needs to plan for N fixed reward functions. Due to the nature of the problem setups, PFE algorithms (that do not exploit the given reward basis r during exploration, e.g., ours) and TAE algorithms can be easily applied to solve the other problem through a covering argument and a union bound, and with a modification of min{d, S} ↔ log(N) in the obtained trajectory complexity bounds. For TAE on a non-stationary MDP, Zhang et al. [2020a] show an algorithm which takes Õ ( log(N) ·H5SA/ 2 ) episodes for TAE7. In comparison, when applied to TAE on a non-stationary MDP, Theorem 3 implies PF-UCB only takes Õ ( log(N) ·H4SA/ 2 ) episodes8, which improves [Zhang et al., 2020a].
6Our considered MDP is stationary as the transition probability P is fixed (across different steps). An MDP is called non-stationary, if the transition probability varies at different steps, i.e., replacing P by {Ph}Hh=1.
7This bound is copied from [Zhang et al., 2020a], which is erroneously stated due to a technical issue in the proof of Lemma 2 in their original paper. The issue can be fixed by a covering argument and union bound on the value functions, but then the obtained bound should be Õ ( log(N)H5S2A/ 2 ) . See Appendix F for details.
8The conversion holds as follows. First set d = 1 in our algorithm to yield an algorithm for TAE with a single agnostic task, where we have min{d, S} = 1. Then one can extend this algorithm to TAE with N agnostic tasks using a union bound to have the algorithm succeed simultaneously for all N tasks, which adds a logN multiplicative factor in the sample complexity bound. In this way, we obtain a TAE algorithm with a sample complexity bound in Theorem 3 where min{d, S} is replaced with logN .

heading: 5 Related Works

text:
MORL. MORL receives extensive attention from RL applications [Yang et al., 2019, Natarajan and Tadepalli, 2005, Mossalam et al., 2016, Abels et al., 2018, Roijers et al., 2013]. However, little theoretical results are known, especially in terms of the sample efficiency and adversarial preference settings. A large amount of MORL works focus on identifying (a cover for) the policies belonging to the Pareto front [Yang et al., 2019, Roijers et al., 2013, Cheung, 2019], but the correspondence between a preference and an optimal policy is ignored. Hence they cannot “accommodate picky customers” as our algorithms do. To our knowledge, this paper initiates the theoretical study of the sample efficiency for MORL in the setting of adversarial preferences.
Adversarial MDP. Similarly to the online MORL problem studied in this paper, the adversarial MDP problem [Neu et al., 2012, Rosenberg and Mansour, 2019, Jin et al., 2019] also allows the reward function to change adversarially over time. However, we study a totally different regret (see (1)). In the adversarial MDP problem, the regret is measured against a fixed policy that is best in the hindsight; but in online MORL problem, we study a regret against a sequence of optimal policies with respect to the sequence of incoming preferences, i.e., our benchmark policy may vary over time. Therefore our regret bound for online MORL problems is orthogonal to those for adversarial MDP problems [Neu et al., 2012, Rosenberg and Mansour, 2019, Jin et al., 2019].
Constrained MDP. In the problem of the constrained MDP, d constraints are enforced to restrict the policy domain, and the agent aims to find a policy that belongs to the domain and maximizes the cumulative rewards [Achiam et al., 2017, Efroni et al., 2020, El Chamie et al., 2018, Fisac et al., 2018, Wachi and Sui, 2020, Garcıa and Fernández, 2015, Brantley et al., 2020]. Constrained MDP is related to MORL as when the constraints are soft, they can be formulated as “objectives” with negative weights. However, there is a fundamental difference: constrained MDP aims to optimize only one (and known) objective, where in MORL studied in this paper, we aim to be able to find near optimal policies for any preference-weighted objective (to accommodate picky customers).
Reward-Free Exploration. The proposed preference-free exploration problem generalizes the problems of reward-free exploration [Jin et al., 2020]. Compared with existing works for RFE [Jin et al., 2020, Kaufmann et al., 2020, Ménard et al., 2020, Zhang et al., 2020b], our method has the advantage of adapting with rewards that admit low-dimensional structure — this partly answers an open question raised by Jin et al. [2020]. We also note that Wang et al. [2020] study RFE with linear function approximation on the value functions; in contrast our setting can be interpreted as RFE with linear function approximation on the reward functions, which is orthogonal to their setting.

heading: 6 Conclusion

text: In this paper we study provably sample-efficient algorithms for multi-objective reinforcement learning in both online and preference-free exploration settings. For both settings, sample-efficient algorithms are proposed and their sample complexity analysis is provided; moreover, two information-theoretic lower bounds are proved to justify the near-tightness of the proposed algorithms, respectively. Our results extend existing theory for single-objective RL and reward-free exploration, and resolve an open question raised by Jin et al. [2020].

heading: Acknowledgement

text: This research was supported in part by NSF CAREER grant 1652257, ONR Award N00014-18-12364, the Lifelong Learning Machines program from DARPA/MTO, and NSF HDR TRIPODS grant 1934979.

title: Accommodating Picky Customers: Regret Bound and Exploration Complexity for Multi-Objective Reinforcement Learning