summaries: The paper studies the arm sampling behavior of UCB and Thompson sampling algorithms. For the two-arm case, the asymptotic behavior of arm sampling is characterized for different regimes (small, large, and medium) of suboptimality gap. Using this characterization, the minimax regret of UCB is shown to O(n\logn), where n is the time horizon. They highlight the incomplete learning phenomenon in Thomson sampling where sample-split could be arbitrarily imbalanced along a sample path even when both the arms have the same mean.

summaries: Classical bandit algorithms such as UCB and Thompson Sampling are well-understood in terms of their performance—for example, an upper bound on their regret—but, until recently, little attention has been given to their actual behavior—for example, the rates at which specific arms are sampled. This work seeks to address these questions by analyzing the arm sampling distribution achieved by both UCB and Thompson Sampling. They provide results characterizing these distributions asymptotically and, in addition, characterize the distribution of the rewards obtained by running UCB.

summaries: The authors study the asymptotic behavior of arm-sampling distributions under the UCB and the Thompson sampling. They provide an asymptotic characterization of the distributions, and show the arm sampling rates asymptotically deterministic regardless of the hardness of instances. With this characterization, focused on canonical UCB algorithm, they provides the first algorithm-specific worst case bound and the first diffusion-limit performance.

summaries: The paper studies the asymptotical behaviors (with respect to the suboptimality gap $\Delta$) of key statistics in the standard upper confidence bound (UCB) algorithm in standard multi-armed bandits (MAB). The contributions are as follows.  1. The paper proves that the **asymptotical arm-sampling rate** converges to a constant, and gives its **analytical form** (Eq. 2). In particular, the paper discovers a non-trivial "**moderate gap**" regime for UCB.  2. The paper proves an asymptotic regret lower bound for UCB **up to $(1 + o(1))$**  in two-armed bandits.  3. The paper proves that the **asymptotical empirical sum** converges to a Brownian motion for UCB in two-armed bandits. 4. The paper proves the asymptotical arm-sampling rate for Bernoulli Thompson sampling in two-armed *deterministic* bandits.  5. The authors extend their results to MAB.

abstractText: One of the key drivers of complexity in the classical (stochastic) multi-armed bandit (MAB) problem is the difference between mean rewards in the top two arms, also known as the instance gap. The celebrated Upper Confidence Bound (UCB) policy is among the simplest optimism-based MAB algorithms that naturally adapts to this gap: for a horizon of play n, it achieves optimal O (log n) regret in instances with “large” gaps, and a near-optimal O p n log n minimax regret when the gap can be arbitrarily “small.” This paper provides new results on the arm-sampling behavior of UCB, leading to several important insights. Among these, it is shown that arm-sampling rates under UCB are asymptotically deterministic, regardless of the problem complexity. This discovery facilitates new sharp asymptotics and a novel alternative proof for the O p n log n minimax regret of UCB. Furthermore, the paper also provides the first complete process-level characterization of the MAB problem under UCB in the conventional diffusion scaling. Among other things, the “small” gap worst-case lens adopted in this paper also reveals profound distinctions between the behavior of UCB and Thompson Sampling, such as an incomplete learning phenomenon characteristic of the latter.

authors:
S. AGRAWAL
N. GOYAL

title: Analysis of thompson sampling for the multi-armed bandit problem

venue: In Conference on learning theory

title: Near-optimal regret bounds for thompson sampling

venue: Journal of the ACM (JACM) 64,

authors:
V.F. ARAMAN
R. CALDENTEY

title: Diffusion approximations for a class of sequential testing problems

venue: arXiv preprint

authors:
AUDIBERT
J.-Y
S BUBECK

title: Minimax policies for adversarial and stochastic bandits

authors:
AUDIBERT
J.-Y
S. BUBECK
R. MUNOS

title: Best arm identification in multi-armed bandits

venue: COLT

authors:
AUDIBERT
J.-Y
R. MUNOS
C. SZEPESVÁRI

title: Exploration–exploitation tradeoff using variance estimates in multi-armed bandits

venue: Theoretical Computer Science 410,

authors:
P. AUER
N. CESA-BIANCHI
P. FISCHER

title: Finite-time analysis of the multiarmed bandit problem

venue: Machine learning 47,

title: Convergence of probability measures

authors:
S. BUBECK
N. CESA-BIANCHI

title: Regret analysis of stochastic and nonstochastic multiarmed bandit problems

venue: arXiv preprint arXiv:1204.5721

authors:
Y. DESHPANDE
L. MACKEY
V. SYRGKANIS
M. TADDY

title: Accurate inference for adaptive linear models

venue: arXiv preprint arXiv:1712.06695

authors:
L. FAN
P.W. GLYNN

title: Diffusion approximations for thompson sampling

venue: arXiv preprint arXiv:2105.09232

authors:
A. GARIVIER
O. CAPPÉ

title: The kl-ucb algorithm for bounded stochastic bandits and beyond

venue: In Proceedings of the 24th annual conference on learning theory

authors:
A. GARIVIER
T. LATTIMORE
E. KAUFMANN

title: On explore-then-commit strategies

venue: In Advances in Neural Information Processing Systems

title: Diffusion approximations. Handbooks in Operations research and management

venue: Science

authors:
V. HADAD
D.A. HIRSHBERG
R. ZHAN
S. WAGER
S. ATHEY

title: Confidence intervals for policy evaluation in adaptive experiments

title: Probability inequalities for sums of bounded random variables

venue: Journal of the American Statistical Association

authors:
J. HONDA
A. TAKEMURA

title: An asymptotically optimal bandit algorithm for bounded support models

authors:
C. KALKANLI
A. OZGUR

title: Asymptotic convergence of thompson sampling

venue: arXiv preprint arXiv:2011.03917

authors:
A. KALVIT
A. ZEEVI

title: From finite to countable-armed bandits

authors:
E. KAUFMANN
O. CAPPÉ
A. GARIVIER

title: On the complexity of best-arm identification in multi-armed bandit models

venue: The Journal of Machine Learning Research 17,

authors:
T.L. LAI
H. ROBBINS

title: Asymptotically efficient adaptive allocation rules

venue: Advances in applied mathematics 6,

title: AND SZEPESVÁRI, C. Bandit algorithms

title: Price dispersion and incomplete learning in the long run

venue: Journal of Economic dynamics and control 7,

authors:
N. MEHRABI
F. MORSTATTER
N. SAXENA
K. LERMAN
A. GALSTYAN

title: A survey on bias and fairness in machine learning

title: A two-armed bandit theory of market pricing

venue: Journal of Economic Theory 9,

authors:
J. SHIN
A. RAMDAS
A. RINALDO

title: Are sample means in multi-armed bandits positively or negatively biased

venue: arXiv preprint arXiv:1905.11397

title: On the bias, risk and consistency of sample means in multi-armed bandits

title: On conditional versus marginal bias in multi-armed bandits

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

title: On the likelihood that one unknown probability exceeds another in view of the evidence of two samples

venue: Biometrika 25,

authors:
S.S. VILLAR
J. BOWDEN
J. WASON

title: Multi-armed bandit models for the optimal design of clinical trials: benefits and challenges

venue: Statistical science: a review journal of the Institute of Mathematical Statistics 30,

authors:
WAGER S
XU

title: Diffusion asymptotics for sequential experiments

venue: arXiv preprint arXiv:2101.09855

heading: 1 Introduction

text:
Background and motivation. The MAB paradigm provides a succinct abstraction of the quintessential exploration vs. exploitation trade-offs inherent in many sequential decision making problems. This has origns in clinical trial studies dating back to 1933 [30] which gave rise to the earliest known MAB heuristic, Thompson Sampling [1]. Today, the MAB problem manifests itself in various forms with applications ranging from dynamic pricing and online auctions to packet routing, scheduling, e-commerce and matching markets among others (see [9] for a comprehensive survey of different formulations). In the canonical stochastic MAB problem, a decision maker (DM) pulls one of K arms sequentially at each time t 2 {1, 2, ...}, and receives a random payoff drawn according to an arm-dependent distribution. The DM, oblivious to the statistical properties of the arms, must balance exploring new arms and exploiting the best arm played thus far in order to maximize her cumulative payoff over the horizon of play. This objective is equivalent to minimizing the regret relative to an oracle with perfect ex ante knowledge of the optimal arm (the one with the highest mean reward). The classical stochastic MAB problem is fully specified by the tuple ⇣ (Pi)16i6K , n ⌘ , where Pi denotes the distribution of rewards associated with the ith arm, and n the horizon of play.
The statistical complexity of regret minimization in the stochastic MAB problem is governed by a key primitive called the gap, denoted by , which accounts for the difference between the top two arm mean rewards in the problem. For a “well-separated” or “large gap” instance, i.e., a fixed bounded away from 0, the seminal paper [22] showed that the order of the smallest achievable regret
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
is logarithmic in the horizon. There has been a plethora of subsequent work involving algorithms which can be fine-tuned to achieve a regret arbitrarily close to the optimal rate discovered in [22] (see [6, 14, 13, 2, 4], etc., for a few notable examples). On the other hand, no algorithm can achieve an expected regret smaller than C p n for a fixed n (the constant hides dependence on the number of arms) uniformly over all problem instances (also called minimax regret); see, e.g., [23], Chapter 15. The saddle-point in this minimax formulation occurs at a gap that satisfies ⇣ 1/ p n. This has a natural interpretation: approximately 1/ 2 samples are required to distinguish between two distributions with means separated by ; at the 1/ p n-scale, it becomes statistically impossible to distinguish between samples from the top two arms within n rounds of play. If the gap is smaller, despite the increased difficulty in the hypothesis test, the problem becomes “easier” from a regret perspective. Thus, ⇣ 1/ p n is the statistically “hardest” scale for regret minimization. A number of popular algorithms achieve the p n minimax-optimal rate (modulo constants), see, e.g., [4, 2], and many more do this within poly-logarithmic factors in n. Many of these are variations of the celebrated upper confidence bound algorithms, e.g., UCB1 [7], that achieve a minimax regret of O p n log n , and at the same time also deliver the logarithmic regret achievable in the instance-dependent setting of [22].
A major driver of the regret performance of an algorithm is its arm-sampling characteristics. For example, in the instance-dependent (large gap) setting, optimal regret guarantees imply that the fraction of time the optimal arm(s) are played approaches 1 in probability, as n grows large. However, this fails to provide any meaningful insights as to the distribution of arm-pulls for smaller gaps, e.g., the ⇣ 1/ p n “small gap” that governs the “worst-case” instance-independent setting.
An illustrative numerical example involving “small gap.” Consider an A/B testing problem (e.g., a vaccine clinical trial) where the experimenter is faced with two competing objectives: first, to estimate the efficacy of each alternative with the best possible precision given a budget of samples, and second, keeping the overall cost of the experiment low. This is a fundamentally hard task and algorithms incurring a low cumulative cost typically spend little time exploring sub-optimal alternatives, resulting in a degraded estimation precision (see, e.g., [5]). In other words, algorithms tailored for (cumulative) regret minimization may lack statistical power [31]. While this trade-off is unavoidable in “well-separated” instances, numerical evidence suggests a plausible resolution in instances with “small” gaps as illustrated below. For example, such a situation might arise in trials conducted using two similarly efficacious vaccines (abstracted away as ⇡ 0). To illustrate the point more vividly, consider the case where is exactly 0 (of course, this information is not known to the experimenter). This setting is numerically illustrated in Figure 1, which shows the empirical distribution of N1(n)/n (the fraction of time arm 1 is played until time n) in a two-armed bandit with = 0, under two different algorithms (UCB and Thompson Sampling), and reward configurations.
A desirable property of the outcome in this setting is to have a linear allocation of the sampling budget per arm on almost every sample-path of the algorithm, as this leads to “complete learning:” an algorithm’s ability to discern statistical indistinguishability of the arm-means, and induce a “balanced” allocation in that event. However, despite the simplicity of the zero-gap scenario, it is far from obvious whether the aforementioned property may be satisfied for standard bandit algorithms such as UCB and Thompson Sampling. Indeed, Figure 1 exhibits a striking difference between the two. The concentration around 1/2 observable in Figure 1(a) indicates that UCB results in an approximately “balanced” sample-split, i.e., the allocation is roughly n/2 per arm for large n
(and this is observed for “most” sample-paths). In fact, we will later see that the “bell curve” in Figure 1(a) eventually collapses into the Dirac measure at 1/2 (Theorem 1). On the other hand, under Thompson Sampling, the allocation of samples across arms may be arbitrarily “imbalanced” despite the arms being statistically identical, as seen in Figure 1(b) (see, for contrast, Figure 1(c), where the allocation is perfectly “balanced”). Namely, the distribution of the posterior may be such that arm 1 is allocated anywhere from almost no sampling effort all the way to receiving almost the entire sampling budget, as Figure 1(b) suggests. Non-degeneracy of arm-sampling rates is observable also under the more widely used version of the algorithm that is based on Gaussian priors and Gaussian likelihoods (Algorithm 2 in [2]); see Figure 2(a). Such behavior can be detrimental for ex post causal inference in the general A/B testing context, and the vaccine testing problem referenced earlier. This is demonstrated via an instructional example of a two-armed bandit with one deterministic reference arm (aka the “one-armed” bandit paradigm), illustrated in Figure 2, and discussed below.
A numerical example illustrating inference implications. Consider a model where arm 1 returns a constant reward of 0.5, while arm 2 yields rewards distributed as Bernoulli(0.5). In this setup, the estimate of the gap (average treatment effect in causal inference parlance) after n rounds of play is given by ̂ = X̄2(n) 0.5, where X̄2(n) denotes the empirical mean reward of arm 2 at time n. The Z statistic associated with this gap estimator is given by Z = 2 p N2(n)̂, where N2(n) is the visitation count of arm 2 at time n. In the absence of any sample-adaptivity in the arm 2 data, results from classical statistics such as the Central Limit Theorem (CLT) would posit an asymptotically Normal distribution for Z . However, since the algorithms that play the arms are adaptive in nature, e.g., UCB and Thompson Sampling, asymptotic-normality may no longer be guaranteed. Indeed, the numerical evidence in Figure 2(b) strongly points to a significant departure from asymptotic-normality of the Z statistic associated with the gap estimator under Thompson Sampling (TS). Non-normality of the Z statistic can be problematic for inferential tasks, e.g., it can lead to statistically unsupported inferences in the binary hypothesis test H0 : = 0 vs. H1 : 6= 0 performed using confidence intervals constructed as per the conventional CLT approximation. In sharp contrast, our work shows that UCB satisfies a certain “balanced” sampling property (such as that in Figure 1(a)) in instances with “small” gaps, formally stated as Theorem 1, that drives the Z statistic towards asymptoticnormality in the aforementioned binary hypothesis testing example (asymptotic-normality being a consequence of Theorem 4). Furthermore, since the p n-normalized “stochastic” regret (defined in (1) in §2) equals ⇣p N2(n)/(4n) ⌘ Z , it follows that this too, satisfies asymptotic-normality under
UCB (due to Theorem 4, in conjunction with Theorem 1). These properties are evident in Figure 2(c) below, and signal reliability of ex post causal inference (under classical assumptions like validity of CLT) from “small gap” data collected by UCB vis-à-vis Thompson Sampling (TS). The reliability of inference under TS may be doubtful even in the limit of infinite data, as Figure 2(b) suggests.
While traditional literature on stochastic bandits is dedicated primarily to the regret minimization problem, there has been significant recent interest also in finer-grain properties of popular “adaptive” MAB algorithms such as UCB and Thompson Sampling. For example, a recent line of work ([27, 28, 29]) investigates the “bias” of optimistic algorithms like UCB. The focus of our work is on understanding the distribution of arm-pulls, which as discussed earlier, has significant bearings on
ex post causal inference from data collected adaptively by bandit algorithms (see, e.g., [33, 16, 32], etc., and references therein for recent developments), algorithmic fairness in the broader context of fairness in machine learning (see [25] for a survey), as well as on novel formulations of the MAB problem such as [20]. Below, we discuss extant literature relevant to our line of work.
Previous work. The study of “well-separated” instances, or the large gap regime, is supported by rich literature. For example, [6] provides high-probability bounds on arm-sampling rates under a parametric family of UCB algorithms. However, as the gap diminishes, leading to the so called small gap regime, the aforementioned bounds become vacuous. The understanding of armsampling behavior remains relatively under-studied here even for popular algorithms such as UCB and Thompson Sampling. This regime is of special interest in that it also covers the classical diffusion scaling1, where ⇣ 1/ p n, which as discussed earlier, corresponds to instances that statistically constitute the “worst-case” for hypothesis testing and regret minimization. Recently, a partial diffusion-limit characterization of the arm-sampling distribution under a version of Thompson Sampling with horizon-dependent prior variances2, was provided in [32] as a solution to a certain stochastic differential equation (SDE). The numerical solution to said SDE was observed to have a non-degenerate distribution on [0, 1]. Similar numerical observations on non-degeneracy of the arm-sampling distribution also under standard versions of Thompson Sampling were reported in [10, 20], among others, albeit limited only to the special case of = 0, and absent a theoretical explanation for the aforementioned observations. Thus, outside of the so called “easy” problems, where is bounded away from 0 by an absolute constant, theoretical understanding of the sampling behavior of bandit algorithms remains an open area of research.
Contributions. In this paper, we provide the first complete asymptotic characterization of armsampling distributions under canonical UCB (Algorithm 1) as a function of the gap (Theorem 1). This gives rise to a fundamental insight: arm-sampling rates are asymptotically deterministic under UCB regardless of the hardness of the instance. We also provide the first theoretical explanation for an “incomplete learning” phenomenon under Thompson Sampling (Algorithm 2) alluded to in Figure 1, as well as a sharp dichotomy between Thompson Sampling and UCB evident therein (Theorem 2). This result earmarks an “instability” of Thompson Sampling in terms of the limiting arm-sampling distribution. As a sequel to Theorem 1, we provide the first complete characterization of the worst-case performance of canonical UCB (Theorem 3). One consequence is that the O p n log n minimax regret of UCB is strictly unimprovable in a precise sense. Moreover, our work also leads to the first process-level characterization of the two-armed bandit problem under canonical UCB in the classical diffusion limit, according to which a suitably normalized cumulative reward process converges in law to a Brownian motion with fully characterized drift and infinitesimal variance (Theorem 4). To the best of our knowledge, this is the first such characterization of UCB-type algorithms. Theorem 4 facilitates a complete distribution-level characterization of UCB’s diffusion-limit regret, thereby providing sharp insights as to the problem’s minimax complexity. Such distribution-level information may also be useful for a variety of inferential tasks, e.g., construction of confidence intervals (see the binary hypothesis testing example referenced in Figure 2(c)), among others. We believe our results may also present new design considerations, in particular, how to achieve, loosely speaking, the “best of both worlds” for Thompson Sampling, by addressing its “small gap” instability. Lastly, we note that our proof techniques are markedly different from the conventional methodology adopted in MAB literature ([6, 9, 2]), and may be of independent interest in the study of related learning algorithms.
Organization of the paper. A formal description of the model and the canonical UCB algorithm is provided in §2. All theoretical propositions are stated in §3, along with a high-level overview of their scope and proof sketch; detailed proofs and ancillary results are relegated to the supplementary material. Finally, concluding remarks and open problems are presented in §4.

heading: 2 The model and notation

text:
The technical development in this paper will focus on the two-armed problem purely for expositional reasons; we provide extensions to the general K-armed setting in Appendix B. The restriction to two-armed bandits has precedence also in the literature due to its tractability for sharp asymptotic
1This is a standard technique for performance evaluation of stochastic systems, commonly used in the operations research and mathematics literature, see, e.g., [15].
2Assumed to be vanishing in n; standard versions of the algorithm involve fixed (positive) prior variances.
analyses, see, e.g., [21]. This setting encapsulates the core statistical complexity of the MAB problem in the “small gap” regime, as well as concisely highlighting the key novelties in our approach. Before describing the model formally, we introduce the following asymptotic conventions.
Notation. We say f(n) = o (g(n)) or g(n) = ! (f(n)) if limn!1 f(n)g(n) = 0. Similarly, f(n) =
O (g(n)) or g(n) = ⌦ (f(n)) if lim supn!1 f(n)g(n) 6 C for some constant C. If f(n) = O ((g(n))) and f(n) = ⌦ ((g(n))) hold simultaneously, we say f(n) = ⇥ (g(n)), or f(n) ⇣ g(n), and we write f(n) ⇠ g(n) in the special case where limn!1 f(n)g(n) = 1. If either sequence f(n) or g(n) is random, and one of the aforementioned ratio conditions holds in probability, we use the subscript p with the corresponding Landau symbol. For example, f(n) = op (g(n)) if f(n)/g(n)
p ! 0 as n!1. Lastly, the notation ‘)’ will be used for weak convergence. The model. The arms are indexed by {1, 2}. Each arm i 2 {1, 2} is characterized by a reward distribution Pi supported on [0, 1] with mean µi. The difference between the two mean rewards, aka the gap, is given by = |µ1 µ2|; as discussed earlier, this captures the hardness of an instance. The sequence of rewards associated with the first m pulls of arm i is denoted by (Xi,j)16j6m. The rewards are assumed to be i.i.d. in time, and independent across arms.3 The number of pulls of arm i up to (and including) time t is denoted by Ni(t). A policy ⇡ := (⇡t)t2N is an adapted sequence that prescribes pulling an arm ⇡t 2 S at time t, where S denotes the probability simplex on {1, 2}. The natural filtration at time t is given by Ft := n (⇡s)s6t , ⇣ (Xi,j)j6Ni(t) : i = 1, 2 ⌘o . The stochastic regret of policy ⇡ after n plays, denoted by R⇡n, is given by
R⇡n := nX
t=1
⇥ max (µ1, µ2) X⇡t,N⇡t (t) ⇤ . (1)
The decision maker is interested in the problem of minimizing the expected regret, given by
inf ⇡2⇧
ER⇡n,
where ⇧ is the set of policies satisfying the non-anticipation property ⇡t : Ft 1 ! S, 1 6 t 6 n, and the expectation is w.r.t. the randomness in reward realizations as well as possible randomness in the policy ⇡. In this paper, we will focus primarily on the canonical UCB policy given by Algorithm 1 below. This policy is parameterized by an exploration coefficient ⇢, which controls its arm-exploring rate. The standard UCB1 policy [7] corresponds to Algorithm 1 with ⇢ = 2; the effect of ⇢ on the expected and high-probability regret bounds of the algorithm is well-documented in [6] for problems with a “large gap.” In what follows, X̄i(t 1) denotes the empirical mean reward from arm i 2 {1, 2} at time t 1, i.e., X̄i(t 1) := PNi(t 1)
j=1 Xi,j Ni(t 1) .
Algorithm 1 The canonical UCB policy for two-armed bandits. 1: Input: Exploration coefficient ⇢ 2 R+. 2: At t = 1, 2, play each arm i 2 {1, 2} once. 3: for t 2 {3, 4, ...} do 4: Play arm ⇡t 2 argmaxi2{1,2} ⇣ X̄i(t 1) + q ⇢ log(t 1) Ni(t 1) ⌘ .

heading: 3 Main results

text: Algorithm 1 is known to achieve ER⇡n = O (log n) in the instance-dependent setting, and ER⇡n = O p n log n in the “small gap” minimax setting. The primary focus of this paper is on the distribution of arm-sampling rates, i.e., Ni(n)/n, i 2 {1, 2}. Our main results are split across two sub-sections; §3.1 examines the behavior of UCB (Algorithm 1) as well as another popular bandit algorithm, Thompson Sampling (specified in Algorithm 2). §3.2 is dedicated to results on the (stochastic) regret of Algorithm 1 under the ⇣ p (log n) /n “worst-case” gap and the ⇣ 1/ p n “diffusion-scaled” gap. 3These assumptions can be relaxed in the spirit of [7]; our results also extend to sub-Gaussian rewards.

heading: 3.1 Asymptotics of arm-sampling rates

text:
Theorem 1 (Arm-sampling rates under UCB) Let i⇤ 2 argmax {µi : i = 1, 2} with ties broken arbitrarily. Then, the following results hold for arm i⇤ as n!1 under Algorithm 1 with ⇢ > 1:
(I) “Large gap:” If = ! ✓q
logn n ◆ , then Ni⇤(n)/n p ! 1.
(II) “Small gap:” If = o ✓q
logn n ◆ , then Ni⇤(n)/n p ! 1/2.
(III) “Moderate gap:” If ⇠ q
✓ logn n for some fixed ✓ > 0, then Ni⇤(n)/n p ! ⇤⇢(✓), where the limit is the unique solution (in ) to
1p 1
1p =
s ✓
⇢ , (2)
and is monotone increasing in ✓, with ⇤⇢(0) = 1/2 and ⇤⇢(✓)! 1 as ✓ !1.
Remark 1 (Permissible values of ⇢ in Algorithm 1) For ⇢ > 1, the expected regret of the policy ⇡ given by Algorithm 1 is bounded as ER⇡n 6 C⇢ ⇣ logn +
⇢ 1
⌘ for some absolute constant C > 0;
the upper bound becomes vacuous for ⇢ 6 1 (see [6], Theorem 7). We therefore restrict Theorem 1 to ⇢ > 1 to ensure that ER⇡n remains non-trivially bounded for all .
Discussion and intuition. Theorem 1 essentially asserts that the sampling rates Ni(n)/n, i 2 {1, 2} are asymptotically deterministic in probability under canonical UCB; only serves to determine the value of the limiting constant. The “moderate” gap regime offers a continuous interpolation from instances with zero gaps to instances with “large” gaps as ✓ sweeps over R+ in that ⇤⇢(✓) increases monotonically from 1/2 at ✓ = 0 to 1 at ✓ =1, consistent with intuition. The special case of ✓ = 0 is numerically illustrated in Figure 1(a). The tails of Ni⇤(n)/n decay polynomially fast near the end points of the interval [0, 1] with the best possible rate approaching O n 3 , occurring for ✓ = 0.
However, as Ni⇤(n)/n approaches its limit, convergence becomes slower and is dominated by fatter ⇥ ⇣q
log logn logn
⌘ tails. The behavior in this regime is regulated by the O p n log log n envelope of
the zero-drift random walk process driving the algorithm’s regret (see proof of Theorem 1 for details).
Proof sketch. To provide the most intuitive explanation, we pivot to the special case where the arms have identical reward distributions, and in particular, = 0. The natural candidate then for the limit of the empirical sampling rate is 1/2. On a high level, the proof relies on polynomially decaying bounds in n for ✏-deviations of the form P ⇣ N1(n)n 1 2 > ✏ ⌘
derived using the standard trick for bounding the number of pulls of any arm on a given sample-path, to wit, for any u, n 2 N, N1(n) can be bounded above by u + Pn t=u+1 {⇡t = 1, N1(t 1) > u}, path-wise. Setting u = d(1/2 + ✏)ne in this expression, one can subsequently show via an analysis involving careful use of the policy structure together with appropriate Chernoff bounds that with high probability (approaching 1 as n ! 1), N1(n)/n 6 1/2 + "⇢ for some "⇢ 2 (0, 1/2) that depends only on ⇢. An identical result would naturally hold also for the other arm by symmetry arguments, and therefore we arrive at a meta-conclusion that Ni(n)/n > 1/2 "⇢ > 0 for both arms i 2 {1, 2} with high probability (approaching 1 as n ! 1). It is noteworthy that said conclusion cannot be arrived at for an arbitrary ✏ > 0 (in place of "⇢) since the polynomial upper bounds on P ⇣ N1(n)n 1 2 > ✏ ⌘
derived using the aforementioned path-wise upper bound on N1(n), become vacuous if u is set “too close” to n/2, i.e., if ✏ is “near” 0. Extension to the full generality of ✏ > 0 is achieved via a refined analysis that uses the Law of the Iterated Logarithm (see [11], Theorem 8.5.2), together with the previous meta-conclusion, to obtain fatter O ⇣q log logn logn ⌘ tail bounds when ✏ is near 0. Here, it is imperative to point out that the “log n” appearing in the denominator is essentially from the p ⇢ log t optimistic bias term of UCB (see Algorithm 1), and therefore the convergence will, as such, hold also for other variations of the policy that have “less aggressive” ! (log log t) exploration functions vis-àvis log t. However, this will be achieved at the expense of the policy’s expected regret performance,
as noted in Remark 1. We also note that the extremely slow O ⇣q
log logn logn
⌘ convergence is not an
artifact of our analysis, but in fact, supported by the numerical evidence in Figure 1(a), suggestive of a plausible non-convergence (to 1/2) in the limit. We believe such observations in previous works likely led to incorrect folk conjectures ruling out the existence of a deterministic limit under UCB à la Theorem 1 (see, e.g., [10] and references therein). The proof for a general in the “small” and “moderate” gap regimes is skeletally similar to that for = 0, albeit guessing a candidate limit for Ni⇤(n)/n is non-trivial; a closed-form expression for ⇤⇢(✓) is provided in Appendix A. Full details of the proof of Theorem 1 are provided in Appendix D,E,F. ... ⇤
Remark 2 (Possible generalizations of Theorem 1) A simple extension to the K-armed setting is provided in Appendix B as Theorem 5. The behavior of UCB policies is largely governed by their optimistic bias. While Theorem 1 only covers the generic UCB policy with p ⇢ log t bias, results of the form Ni(n)/n p ! ci for some ci 2 (0, 1) continue to hold also under smaller ! p ⇢ log log t bias (driven by the Law of the Iterated Logarithm). We believe this observation will be useful when examining more complicated UCB-inspired policies such as KL-UCB [13], DMED [18], etc.
What about Thompson Sampling? Results such as those discussed above for other popular adaptive algorithms like Thompson Sampling4 are only arable in “well-separated” instances where Ni⇤(n)/n p ! 1 as n ! 1 follows as a trivial consequence of its O ( p n) minimax regret bound [2]. For smaller gaps, theoretical understanding of the distribution of arm-pulls under Thompson Sampling remains largely absent even for its most widely-studied variants. In this paper, we provide a first result in this direction: Theorem 2 formalizes a revealing observation for classical Thompson Sampling (Algorithm 2) in instances with zero gap, and elucidates its instability in view of the numerical evidence reported in Figure 1(b) and 1(c). This result also offers an explanation for the sharp contrast with the statistical behavior of canonical UCB (Algorithm 1) à la Theorem 1, also evident from Figure 1(a). In what follows, rewards are assumed to be Bernoulli, and Si (respectively Fi) counts the number of successes/1’s (respectively failures/0’s) associated with arm i 2 {1, 2}.
Algorithm 2 Thompson Sampling for the two-armed Bernoulli bandit. 1: Initialize: Number of successes (1’s) and failures (0’s) for each arm i 2 {1, 2}, (Si, Fi) = (0, 0). 2: for t 2 {1, 2, ...} do 3: Sample for each i 2 {1, 2}, Ti ⇠ Beta (Si + 1, Fi + 1). 4: Play arm ⇡t 2 argmaxi2{1,2} Ti and observe reward rt 2 {0, 1}. 5: Update success-failure counts: S⇡t S⇡t + rt, F⇡t F⇡t + 1 rt.
Theorem 2 (Incomplete learning under Thompson Sampling) In a two-armed model where both arms yield rewards distributed as Bernoulli(q), the following holds under Algorithm 2 as n!1:
(I) If q = 0, then N1(n)/n) 1/2.
(II) If q = 1, then N1(n)/n) Uniform distribution on [0, 1].
Proof sketch. The proof of Theorem 2 relies on a careful application of two subtle properties of the Beta distribution (Fact 2 and Fact 3), stated and proved in Appendix C,K. For part (I), we invoke symmetry to deduce EN1(n) = n/2, and use Fact 2 to show that the standard deviation of N1(n) is sub-linear in n, thus proving the stated assertion in (I). More elaborately, Fact 2 states for the reward configuration in (I) that the probability of playing arm 1 after it has already been played n1 times, and arm 2 n2 times, equals (n2 + 1) /(n1 +n2 +2). This probability is smaller than 1/2 if n1 > n2, which provides an intuitive explanation for the fast convergence of N1(n)/n to 1/2 observed in Figure 1(c). In fact, we conjecture that the result in (I) holds also with probability 1 based on the aforementioned “self-balancing” property. The conclusion in part (II) hinges on an application of Fact 3 to show the stronger result: N1(n) is uniformly distributed over {0, 1, ..., n} for any n 2 N. Contrary to Fact 2, Fact 3 states that quite the opposite is true for the reward configuration in (II): the probability of playing arm 1 after it has already been played n1 times, and arm 2 n2 times, equals (n1 + 1) /(n1+n2+2), which is greater than 1/2 when n1 > n2. That is, the posterior distributions
4This is the version based on Gaussian priors and Gaussian likelihoods, not the classical version based on Beta priors and Bernoulli likelihoods which has a minimax regret of O p n log n [2].
evolve in such a way that the algorithm is “deceived” into incorrectly believing one of the arms (arm 2 in this case) to be inferior. This leads to large sojourn times between successive visitations of arm 2 on such a sample-path, thereby resulting in a perpetual “imbalance” in the sample-counts. This provides an intuitive explanation for the non-degeneracy observed in Figure 1(b) and 2(a), which additionally, also indicates that such behavior, in fact, persists also for general (non-deterministic) reward distributions, as well as under the Gaussian prior-based version of the algorithm. Full proof of Theorem 2 is provided in Appendix G. ⇤ More on “incomplete learning.” The zero-gap setting is a special case of the “small gap” regime where canonical UCB guarantees a (1/2, 1/2) sample-split in probability (Theorem 1). On the other hand, Theorem 2 suggests that second order factors such as the mean signal strength (magnitude of the mean reward) could significantly affect the nature of the resulting sample-split under Thompson Sampling. Note that even though the result only presupposes deterministic 0/1 rewards, the aforementioned claim is, in fact, borne out by the numerical evidence in Figure 1(b) and 1(c). The sampling distribution seemingly flattens rapidly from the Dirac measure at 1/2 to the Uniform distribution on [0, 1] as the mean rewards move away from 0. This uncertainty in the limiting sampling behavior has non-trivial implications for a variety of application areas of such learning algorithms. For instance, a uniform distribution of arm-sampling rates on [0, 1] indicates that the sample-split could be arbitrarily imbalanced along a sample-path, despite, as in the setting of Theorem 2, the two arms being statistically identical; this phenomenon is typically referred to as “incomplete learning” (see [26, 24] for the original context). Non-degeneracy in the limiting distribution is also observable numerically up to diffusion-scale gaps of O (1/ p n) under other versions of Thompson Sampling (see [32] for examples); our focus on the more extreme zero-gap setting simplifies the illustration of these effects.
A brief survey of Thompson Sampling. While extant literature does not provide any explicit result for Thompson Sampling characterizing its arm-sampling behavior in instances with “small” and “moderate” gaps, there has been recent work on its analysis in the ⇣ 1/ p n regime under what is known as the diffusion approximation lens (see [32, 12]). Cited works study Thompson Sampling primarily under the assumption that the prior variance associated with the mean reward of any arm vanishes in the horizon of play at an “appropriate” rate.5 Such a scaling, however, is not ideal from a regret standpoint and indeed, the versions of Thompson Sampling optimized for regret performance use fixed (non-vanishing) prior variances, e.g., Algorithm 2 and its Gaussian prior-based counterpart (see [2]). On a high level, [32, 12] establish that as n ! 1, the pre-limit (Ni(nt)/n)t2[0,1] under Thompson Sampling converges weakly to a “diffusion-limit” stochastic process on t 2 [0, 1]. Recall from earlier discussion that ⇣ 1/ p n is covered under the “small gap” regime; consequently, it follows from Theorem 1 that the analogous limit for UCB is, in fact, the deterministic process t/2. In sharp contrast, the diffusion-limit process under Thompson Sampling may at best be characterizable only as a solution (possibly non-unique) to an appropriate stochastic differential equation or ordinary differential equation driven by a suitably (random) time-changed Brownian motion. Consequently, the diffusion limit under Thompson Sampling is more difficult to interpret vis-à-vis UCB (see Theorem 4), and it is much harder to obtain lucid insights as to the nature of the distribution of Ni(n)/n as n ! 1. The asymptotic distribution of Ni(n)/n under Thompson Sampling is also investigated in [19], albeit in a significantly different setting. Cited paper considers the Bayesian setting where a prior distribution exists over problem instances, and the Thompson Sampling algorithm is “well-specified,” i.e., information about said prior is baked into the algorithm. Specifically, a sample path of the algorithm in their model involves a random problem instance from the instance-space. In contrast, the derivation of the asymptotic distribution of arm-pulls in our work is for specific (fixed) problem instances, viz., reward configurations (I) and (II) described in Theorem 2, and under the classical version of Thompson Sampling (Algorithm 2).

heading: 3.2 Beyond arm-sampling rates

text:
This part of the paper is dedicated to a more fine-grained analysis of the “stochastic” regret of UCB (defined in (1) in §2). Results are largely facilitated by insights on the sampling behavior of UCB in instances with “small” gaps, attributable to Theorem 1; however, we believe they are of interest in their own right. We commence with an application of Theorem 1 which provides the first complete characterization of the worst-case (minimax) performance of canonical UCB. A full diffusion-limit characterization of the two-armed bandit problem under UCB is provided thereafter in Theorem 4.
5The only result applicable to the case of non-vanishing prior variances is Theorem 4.2 of [12].
Theorem 3 (Minimax regret complexity of UCB) In the “moderate gap” regime referenced in Theorem 1 where ⇠ q ✓ logn
n , the regret of the policy ⇡ given by Algorithm 1 with ⇢ > 1 satisfies
R⇡np n log n ) p ✓ 1 ⇤⇢(✓) =: h⇢(✓) as n!1, (3)
where ⇤⇢(✓) is the (unique) solution to (2).
To the best of our knowledge, this is the first algorithm-specific result (sharp asymptotic) that is distinct from the general ⌦ ( p n) information-theoretic lower bound by a horizon-dependent factor.6
Discussion. A closed-form expression for ⇤⇢(✓) and h⇢(✓) is provided in Appendix A. The behavior of h⇢(✓) is illustrated below in Figure 3. For a fixed ⇢, the function h⇢(✓) is numerically observed to be uni-modal in ✓ and admit a global maximum at a unique ✓⇤⇢ := arg sup✓>0 h⇢(✓), bounded away from 0. Theorem 3 establishes that the worst-case (instance-independent) regret admits the sharp asymptotic R⇡n ⇠ h⇢ ✓⇤⇢ p n log n. In standard bandit parlance, this substantiates that the
O p n log n
worst-case (minimax) performance guarantee of canonical UCB cannot be improved in terms of its horizon-dependence. In addition, the result also specifies the precise asymptotic constants achievable in the worst-case setting. This can alternately be viewed as a direct approach to proving the O p n log n performance bound for UCB vis-à-vis conventional minimax analyses such as [9]. Proof sketch. On a high level, note that when = p
(✓ log n)/n, it follows from Theorem 1 that ER⇡n = p (✓ log n)/nE [n Ni⇤(n)] ⇠ h⇢(✓) p n log n (convergence in probability implies that in mean since |Ni⇤(n)/n| 6 1). That R⇡n also admits the same sharp asymptotic can be shown via a finer analysis. In other regimes of , viz., “small” and “large” gaps, we already know that R⇡n = op p n log n . This is obvious for “small” since ER⇡n 6 n = o p n log n , while for “large” , we use ER⇡n 6 C⇢ ((log n)/ + 1/(⇢ 1)) for some absolute constant C (given ⇢ > 1, 6 1) [6], followed by Markov’s inequality. Thus, the multiplicative constant sup✓>0 h⇢(✓) obtained in the “moderate” gap regime must correspond to the worst-case performance of the algorithm. ⇤ Towards diffusion asymptotics. Diffusion scaling is a classical stochastic analysis tecnnique widely used in the mathematics and operations research literature, see, e.g., steady-state analyses of queuing systems in [15], and a recent application to certain sequential testing problems in [3]. Under this lens, time is accelerated linearly in n, space contracted by a factor of p n, and a sequence of systems indexed by n is considered. In our problem, the nth such system refers to an instance of the two-armed bandit with: n as the horizon of play; a gap that vanishes in the horizon as = c/ p n for some fixed c; and fixed reward variances given by 21 , 22 . This is a natural scaling for MAB experiments in that it “preserves” the hardness of the learning problem as n sweeps over the sequence of systems. Recall also from previous discussion that the “hardest” information-theoretic instances have a ⇥ (1/ p n) gap; in short, the diffusion limit is an appropriate asymptotic lens for observing interesting process-level behavior in the MAB problem. However, despite the aforementioned reasons, the diffusion limit behavior of bandit algorithms remains poorly understood and largely unexplored. A recent foray
6Previous work establishes matching ⇥ p Kn logK
upper and lower bounds for the minimax expected regret of the Gaussian prior-based Thompson Sampling algorithm in the K-armed problem, see [2].
was made in [32, 12], however, deterministic algorithms like UCB remain outside the ambit of such analysis, on account of discontinuities. Theorem 4 provides a complete characterization of this limit.
Theorem 4 (Diffusion asymptotics for canonical UCB) Suppose that the mean reward of arm i 2 {1, 2} is given by µi = µ + ✓i/ p n, where n is the horizon of play and µ, ✓1, ✓2 > 0 are fixed constants, and reward variances are 21 , 22 . Define 0 := |✓1 ✓2|. Denote the cumulative reward earned from arm i until time m by Si,m := PNi(m) j=1 Xi,j , and let S̃i,m := Si,m µNi(m). Then, the following process-level convergences hold under the policy ⇡ given by Algorithm 1 with ⇢ > 1:
(I) S̃1,bntcp n , S̃2,bntcp n
! ) ✓ ✓1t
2 + 1p 2 B1(t),
✓2t
2 + 2p 2 B2(t)
◆ ,
(II) R⇡bntcp
n ) 0t 2 +
r 21 + 2 2
2 B̃(t),
where the process-level convergence is over t 2 [0, 1], and B1(t) and B2(t) are independent standard Brownian motions in R, and B̃(t) := q 21
21+ 2 2 B1(t)
q 22
21+ 2 2 B2(t).
Proof sketch. Note that if the arms are played bn/2c times each independently over the horizon of play n (resulting in Ni(n) = bn/2c, i 2 {1, 2}), part (I) of the stated assertion would immediately follow from Donsker’s Theorem (see [8], Section 14). However, since the sequence of plays, and hence also the eventual allocation (N1(n), N2(n)), is determined adaptively by the policy, the aforementioned convergence may no longer be true. Here, the result hinges crucially on the observation from Theorem 1 that for any arm i 2 {1, 2} as n ! 1, Ni(n)/n
p ! 1/2 under UCB when ⇣ 1/ p n (diffusion-scaled gaps are covered under the “small gap” regime). This observation facilitates a standard “random time-change” argument t Ni(bntc)/n, i 2 {1, 2}, which followed upon by an application of Donsker’s Theorem, leads to the stated assertion in (I). This has the profound implication that for diffusion-scaled gaps, a two-armed bandit under UCB is, in fact, well-approximated by a classical system with independent samples (sample-interdependence due to the adaptive nature of the policy is washed away in the limit). The conclusion in (II) follows after a direct application of the Continuous Mapping Theorem (see [8], Theorem 2.7) to (I). ⇤ Discussion. An immediate observation following Theorem 4 is that the normalized regret R⇡n/ p n is asymptotically Normal with mean 0/2 and variance 21 + 2 2 /2 under UCB. Apart from aiding in obvious inferential tasks like construction of (asymptotically valid) confidence intervals (see, e.g., the binary hypothesis testing example referenced in Figure 2(c)), etc., such information provides new insights as to the problem’s minimax complexity as well. This is because ⇣ 1/ p n is known to be the information-theoretic “worst-case” for the problem; the smallest achievable regret in this regime must asymptotically be dominated by that under UCB, i.e., 0 p n/2. It is also noteworthy that while the diffusion limit in Theorem 4 does not itself depend on the exploration coefficient ⇢, the rate at which the system converges to said limit indeed depends on ⇢. Theorem 4 will continue to hold only as long as ⇢ = ! ((log log n) / log n); for smaller ⇢, the convergence of Ni(n)/n to 1/2 may no longer be true (refer to the proof of Theorem 1 in the “small” gap regime in Appendix E).

heading: 4 Concluding remarks and open problems

text:
Our results for the two-armed problem under canonical UCB (Algorithm 1) may be generalizable to the K-armed setting, leveraging the observations and insights from Theorem 1 (a simple extension is provided in Appendix B). The K-armed problem under UCB is of interest in its own right: we postulate a division of sampling effort within and across clusters of “similar” and “separated” arms, determined by their relative sub-optimality gaps in the spirit of Theorem 1. We expect that similar generalizations are possible also for Theorem 3 and Theorem 4. For Thompson Sampling, on the other hand, things are less obvious even in the two-armed setting. For example, in spite of compelling numerical evidence (refer, e.g., to Figure 1(b)) suggesting a plausibly non-degenerate distribution of arm-sampling rates for bounded rewards in [0, 1] with means away from 0, the proof of Theorem 2 relies heavily on the rewards being deterministic 0/1, and cannot be extended to the general case. In addition, similar results are conjectured also for the more widely used Gaussian prior-based version of the algorithm. Such results may, in future, shed light on several important diffusion-limit performance metrics of Thompson Sampling, and elucidate its normalized minimax (stochastic) regret behavior.
Acknowledgments and Disclosure of Funding
The authors sincerely thank the anonymous reviewers for their insightful remarks and constructive feedback on the initial submission, and hope that this revision satisfactorily addresses all their points. The authors declare an absence of any competing interests, financial or otherwise.

title: A Closer Look at the Worst-case Behavior of Multi-armed Bandit Algorithms


summaries: This paper proposes a framework for cross-domain item cold-start recommendation. The main idea follows the algorithm of Stein Variational Gradient Descent, by iteratively transporting the auxiliary embeddings of cold items in the target domain to match the embedding distribution of warm items in the source domain. The authors further propose to reduce computational time costs by selecting typical proxies of cold items.

summaries: This paper focuses on solving the cold-start issue in Cross-Domain Recommendation (CDR) setting. For this purpose, the authors propose a DisAlign framework, which mainly has two modules, i.e., rating prediction module and embedding distribution alignment module. The main novelty relies in the embedding distribution alignment module. In it, the authors propose Stein path alignment and proxy Stein path alignment. The experiments on benchmark datasets, compared with six baselines, show the superior of the proposed model. The experimental analysis also shows the effectiveness of the model ability.

summaries: Summary:  The paper addresses the cold-start item recommendation with auxiliary information. To attack the heterogeneity/ domain discrepancy across the source domain and target domain, Stein path is adopted to align the domain distributions. In specific, the distribution of target item auxiliary embedding is to be aligned with both source item auxiliary embedding and source item collaborative embedding. A proxy Stein path is proposed to reduce the cubic time complexity. Good experiments are achieved on real-world datasets by comparing with many SOTA methods.

summaries: In this paper, the authors study a relatively new problem called cross-domain cold-start recommendation (CDCSR), where the goal is to transfer knowledge from a warm source domain with user-item ratings and item descriptions to a cold target domain with item descriptions only (i.e., without any user-item interactions). Notice that the users in two domains are aligned. In particular, the authors propose a novel recommendation framework, i.e., DisAlign, which contains two main modules, i.e., a rating prediction module and an embedding distribution alignment module.

abstractText: Cross-Domain Recommendation (CDR) has been popularly studied to utilize different domain knowledge to solve the cold-start problem in recommender systems. In this paper, we focus on the Cross-Domain Cold-Start Recommendation (CDCSR) problem. That is, how to leverage the information from a source domain, where items are ‘warm’, to improve the recommendation performance of a target domain, where items are ‘cold’. Unfortunately, previous approaches on cold-start and CDR cannot reduce the latent embedding discrepancy across domains efficiently and lead to model degradation. To address this issue, we propose DisAlign, a cross-domain recommendation framework for the CDCSR problem, which utilizes both rating and auxiliary representations from the source domain to improve the recommendation performance of the target domain. Specifically, we first propose Stein path alignment for aligning the latent embedding distributions across domains, and then further propose its improved version, i.e., proxy Stein path, which can reduce the operation consumption and improve efficiency. Our empirical study on Douban and Amazon datasets demonstrates that DisAlign significantly outperforms the state-of-the-art models under the CDCSR setting.

authors:
Liang Bai
Jiye Liang

title: Sparse subspace clustering with entropy-norm

venue: In International Conference on Machine Learning,

title: Book review: Probability and related topics in physical sciences

venue: Bulletin of the American Mathematical Society,

authors:
Karsten M Borgwardt
Arthur Gretton
Malte J Rasch
Hans-Peter Kriegel
Bernhard Schölkopf
Alex J Smola

title: Integrating structured biological data by kernel maximum mean discrepancy

venue: Bioinformatics, 22(14):e49–e57,

authors:
Zhihong Chen
Rong Xiao
Chenliang Li
Gangfeng Ye
Haochuan Sun
Hongbo Deng. Esam

title: Discriminative domain adaptation with non-displayed items to improve long-tail performance

venue: In SIGIR,

authors:
Bharath Bhushan Damodaran
Benjamin Kellenberger
Rémi Flamary
Devis Tuia
Nicolas Courty

title: Deepjdot: Deep joint distribution optimal transport for unsupervised domain adaptation

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

title: Mean field simulation for Monte Carlo integration

venue: CRC press,

authors:
Yaroslav Ganin
Evgeniya Ustinova
Hana Ajakan
Pascal Germain
Hugo Larochelle
François Laviolette
Mario Marchand
Victor Lempitsky

title: Domain-adversarial training of neural networks. The journal of machine learning

authors:
Zeno Gantner
Lucas Drumond
Christoph Freudenthaler
Steffen Rendle
Lars Schmidt- Thieme

title: Learning attribute-to-feature mappings for cold-start recommendations

venue: IEEE International Conference on Data Mining,

authors:
Jacob Goldberger
Geoffrey E Hinton
Sam Roweis
Russ R Salakhutdinov

title: Neighbourhood components analysis

venue: Advances in neural information processing systems,

authors:
Boqing Gong
Kristen Grauman
Fei Sha

title: Connecting the dots with landmarks: Discriminatively learning domain-invariant features for unsupervised domain adaptation

authors:
Jyotirmoy Gope
Sanjay Kumar Jain

title: A survey on solving cold start problem in recommender systems

venue: In 2017 International Conference on Computing, Communication and Automation (ICCCA),

authors:
Jun Han
Qiang Liu

title: Stein variational gradient descent without gradient

authors:
Cheng-Kang Hsieh
Longqi Yang
Yin Cui
Tsung-Yi Lin
Serge Belongie
Deborah Estrin

title: Collaborative metric learning

venue: In WWW,

authors:
Guangneng Hu
Yu Zhang
Qiang Yang

title: Conet: Collaborative cross networks for crossdomain recommendation

venue: In Proceedings of the 27th ACM international conference on information and knowledge management,

authors:
D. Kingma
J. Ba

title: Adam: A method for stochastic optimization

venue: Computer Science,

authors:
Van Der Maaten Laurens
Geoffrey Hinton

title: Visualizing data using t-sne

venue: Journal of Machine Learning Research,

authors:
Jingjing Li
Mengmeng Jing
Ke Lu
Lei Zhu
Yang Yang
Zi Huang

title: From zero-shot learning to cold-start recommendation

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

authors:
Pan Li
Alexander Tuzhilin

title: Ddtcdr: Deep dual transfer cross domain recommendation

venue: In WSDM,

title: Stein variational gradient descent as gradient flow

venue: arXiv preprint arXiv:1704.07520,

authors:
Qiang Liu
Dilin Wang

title: Stein variational gradient descent: A general purpose bayesian inference algorithm

venue: arXiv preprint arXiv:1608.04471,

authors:
Mingsheng Long
Yue Cao
Jianmin Wang
Michael Jordan

title: Learning transferable features with deep adaptation networks

venue: In International conference on machine learning,

authors:
Mingsheng Long
Zhangjie Cao
Jianmin Wang
Michael I Jordan

title: Conditional adversarial domain adaptation

venue: In Advances in Neural Information Processing Systems,

authors:
Qianli Ma
Jiawei Zheng
Sen Li
Gary W Cottrell

title: Learning representations for time series clustering

authors:
Tong Man
Huawei Shen
Xiaolong Jin
Xueqi Cheng

title: Cross-domain recommendation: An embedding and mapping approach

venue: In IJCAI,

authors:
Yitong Meng
Xiao Yan
Weiwen Liu
Huanhuan Wu
James Cheng

title: Wasserstein collaborative filtering for item cold-start recommendation

venue: In Proceedings of the 28th ACM Conference on User Modeling, Adaptation and Personalization,

authors:
Jianmo Ni
Jiacheng Li
Julian McAuley

title: Justifying recommendations using distantlylabeled reviews and fine-grained aspects

venue: In EMNLP-IJCNLP,

authors:
Feiping Nie
Xiaoqian Wang
Heng Huang

title: Clustering and projected clustering with adaptive neighbors

venue: In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,

authors:
Travis A O’Brien
William D Collins
Sara A Rauscher
Todd D Ringler

title: Reducing the computational cost of the ecf using a nufft: A fast and objective probability density estimation method

venue: Computational Statistics & Data Analysis,

authors:
Travis A O’Brien
Karthik Kashinath
Nicholas R Cavanaugh
William D Collins
John P O’Brien

title: A fast and objective multidimensional kernel density estimation method: fastkde

authors:
Jeffrey Pennington
Richard Socher
Christopher Manning

title: Glove: Global vectors for word representation

authors:
Steffen Rendle
Christoph Freudenthaler
Zeno Gantner
Lars Schmidt-Thieme

title: Bpr: Bayesian personalized ranking from implicit feedback

venue: arXiv preprint arXiv:1205.2618,

authors:
Yan Song
Shuming Shi
Jing Li
Haisong Zhang

title: Directional skip-gram: Explicitly distinguishing left and right context for word embeddings. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers)

authors:
Baochen Sun
Kate Saenko

title: Deep coral: Correlation alignment for deep domain adaptation

venue: In European conference on computer vision,

authors:
B. Sun
K. Saenko

authors:
Chuanqi Tan
Fuchun Sun
Tao Kong
Wenchang Zhang
Chao Yang
Chunfang Liu

title: A survey on deep transfer learning

venue: In International conference on artificial neural networks,

authors:
Eric Tzeng
Judy Hoffman
Trevor Darrell
Kate Saenko

title: Simultaneous deep transfer across domains and tasks

venue: In Proceedings of the IEEE international conference on computer vision,

authors:
Eric Tzeng
Judy Hoffman
Kate Saenko
Trevor Darrell

title: Adversarial discriminative domain adaptation

venue: In CVPR,

authors:
Evgeniya Ustinova
Victor Lempitsky

title: Learning deep embeddings with histogram loss

venue: arXiv preprint arXiv:1611.00822,

authors:
Aäron Van Den Oord
Sander Dieleman
Benjamin Schrauwen

title: Deep content-based music recommendation

venue: In NIPS,

authors:
Maksims Volkovs
Guang Wei Yu
Tomi Poutanen

title: Dropoutnet: Addressing cold start in recommender systems

authors:
D. Wang
Z. Tang
C. Bajaj
Q. Liu

title: Stein variational gradient descent with matrix-valued kernels

authors:
Xiang Wang
Xiangnan He
Yixin Cao
Meng Liu
Tat-Seng Chua

title: Kgat: Knowledge graph attention network for recommendation

venue: In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining,

authors:
Yaqing Wang
Chunyan Feng
Caili Guo
Yunfei Chu
Jenq-Neng Hwang

title: Solving the sparsity problem in recommendations via cross-domain item embedding based on co-clustering

venue: In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining,

authors:
Renjun Xu
Pelen Liu
Liyan Wang
Chao Chen
Jindong Wang

title: Reliable weighted optimal transport for unsupervised domain adaptation

authors:
Feng Yuan
Lina Yao
Boualem Benatallah

title: Darec: Deep domain adaptation for crossdomain recommendation via transferring rating patterns

authors:
Werner Zellinger
Thomas Grubinger
Edwin Lughofer
Thomas Natschläger
Susanne Saminger-Platz

title: Central moment discrepancy (cmd) for domain-invariant representation learning

venue: arXiv preprint arXiv:1702.08811,

authors:
Hongyuan Zha
Xiaofeng He
Chris Ding
Ming Gu
Horst D Simon

title: Spectral relaxation for k-means clustering

authors:
Cheng Zhao
Chenliang Li
Rong Xiao
Hongbo Deng
Aixin Sun

title: Catn: Cross-domain recommendation for cold-start users via aspect transfer

venue: network. pages 229–238,

authors:
Feng Zhu
Chaochao Chen
Yan Wang
Guanfeng Liu
Xiaolin Zheng

title: Dtcdr: A framework for dual-target cross-domain recommendation

venue: In CIKM,

authors:
Feng Zhu
Yan Wang
Chaochao Chen
Guanfeng Liu
Xiaolin Zheng

title: A graphical and attentional framework for dual-target cross-domain recommendation

authors:
Feng Zhu
Yan Wang
Chaochao Chen
Jun Zhou
Longfei Li
Guanfeng Liu

title: Cross-domain recommendation: Challenges, progress, and prospects

authors:
Feng Zhu
Yan Wang
Jun Zhou
Chaochao Chen
Longfei Li
Guanfeng Liu

title: A unified framework for cross-domain and cross-system recommendations

venue: IEEE Transactions on Knowledge and Data Engineering,

authors:
Ziwei Zhu
Shahin Sefati
Parsa Saadatpanah
James Caverlee

title: Recommendation for new users and new items via randomized training and mixture-of-experts transformation

authors:
Fuzhen Zhuang
Zhiyuan Qi
Keyu Duan
Dongbo Xi
Yongchun Zhu
Hengshu Zhu
Hui Xiong
Qing He

title: A comprehensive survey on transfer learning

venue: Proceedings of the IEEE,

heading: 1 Introduction

text:
Data sparsity and cold-start are long-standing problems in recommender systems [15, 19]. With the development of internet techniques, most users always participant in many platforms or domains for different purposes. Therefore, Cross-Domain Recommendation (CDR) has emerged to utilise the relatively richer information from a source domain to improve the recommendation accuracy in a target domain [52, 53]. Most existing CDR models can tackle the data sparsity problem in the target domain by assuming the existence of overlapped users or items with similar tastes or attributions across domains [5].
Instead of focusing on solving the data sparsity problem, we consider cold-start item recommendation under the CDR setting. Specifically, we concentrate on the Cross-Domain Cold-Start Recommendation (CDCSR) problem, that is, two domains share the same user set but different items, and both domains have auxiliary representations such as item profiles or descriptions. The prime challenge is how to leverage the information from the source domain, where the items are ‘warm’, to improve the recommendation performance of the target domain, where the items are ‘cold’. The CDCSR problem popularly exists in practice, for instance, a movie marketing platform newly launches a book renting service where there is no user-book interaction yet, as shown in Figure 1.
Existing researches on cold-start recommendation and CDR cannot solve the above problem well. On the one hand, existing cold-start recommendation models assume that the distributions of cold items should be consistent with the warm ones as they are homogeneous [54, 18, 12]. On the other hand,
∗Corresponding Author
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
existing CDR models assume that both source and target domains have user-item interactions for learning the mapping functions [25]. Since the cold and warm items are heterogeneous with different latent embedding distributions in practice, and there is no user-item interaction in the target domain, conventional cold-start and CDR models cannot properly suitable to the CDCSR problem.
Similar to the transfer learning task, the key to the CDCSR problem is to reduce the discrepancy between the latent embedding distributions across domains. However, both the warm and cold item representations are scattered and complicated due to the fact that the latent embeddings may represent diverse information. Thus, existing transfer learning based domain adaptation approaches [23, 45, 37] cannot achieve good alignment results, which limits their performances.
To address the aforementioned issue, in this paper, we propose DisAlign, a cross-domain recommendation framework for the CDCSR problem. In order to better align the complicated latent embedding distributions and make high quality of rating
predictions, we utilize two modules in DisAlign, i.e., rating prediction module and embedding distribution alignment module, as will be shown in Figure 2. The rating prediction module aims to capture user and item collaborative preferences in the source domain, and we propose metric-based contrastive learning for modelling. The goal of distribution alignment module is to properly match the latent embedding distributions across domains, and we propose two techniques for it, i.e., Stein path alignment and its improved version called proxy Stein path alignment. Specifically, inspired by the particle-based inference algorithm Stein Variational Gradient Descent (SVGD) [21, 13, 20], we first propose Stein path alignment to minimize the domain discrepancy through the particle-moving process, which can take both the source probability and target intra-domain structure into account. Although Stein path can obtain satisfying performance, it has to involve all the target samples during the training process, which is time consuming when data size is large. Thus, we further propose proxy Stein path alignment which only needs to exploit typical samples to represent the target data distribution, and thus can accelerate the operation speed. The comparison and visualization results in experiments will show the reliability and efficiency of DisAlign.
We summarize the main contributions of this paper as follows: (1) We propose a novel framework, i.e., DisAlign, for the CDCSR problem, which can utilize both rating and auxiliary representations from the source domain to improve the recommendation performance of the target domain. (2) To our best knowledge, this is the first attempt in literature to propose Stein path alignment for aligning the latent embedding distributions across domains, and we also propose its improved version, i.e., proxy Stein path, for higher efficiency. (3) Empirical studies on Douban and Amazon datasets demonstrate that DisAlign significantly improves the state-of-the-art models under the CDCSR setting.

heading: 2 The proposed model

text:
2.1 Framework of DisAlign
First, we describe notations. We assume there are two domains, i.e., a source domain S and a target domain T . We assume both domains S and T have NU users, S has NS warm items, and T has NT cold items. Let RS ∈ RNU×NS be the warm rating matrix in S and RT ∈ RNU×NT be the cold rating matrix in T . In CDCSR setting, RT is absence during training and will be only used for test, since items are cold in T . We also assume that the warm items and the cold items have auxiliary representations XW ∈ RNS×Z and XV ∈ RNT×Z , respectively, with Z denoting
the dimension of auxiliary representations. The auxiliary representations usually include useful sideinformation, e.g., themes, reviews, profiles in a movie domain. Our purpose is to predict the absent RT in T by leveraging RS in S and the auxiliary representations in both S and T .
Then, we introduce the overview of our proposed DisAlign framework, as is illustrated in Figure 2. DisAlign model mainly has two modules, i.e., rating prediction module and embedding distribution alignment module. To avoid the error superimposition problem [54], the rating prediction module in the source domain mainly provides end-to-end joint training of modelling user and item collaborative embeddings and matching the item collaborative embeddings with item auxiliary embeddings. The embedding distribution alignment module aligns the distributions between the warm and cold items across domains, minimizing the discrepancy between auxiliary latent feature embeddings in the source and target domains sufficiently. We will introduce these two modules in details later.

heading: 2.2 Rating prediction module

text:
We first introduce the rating prediction module of DisAlign. For the i-th user and the j-th item in the source (warm) domain, we define their corresponding one-hot ID vectors as XUi and X V j , respectively. For the j-th warm item, we also define its auxiliary representation as XWj . The rating prediction module mainly has three purposes, including (1) exploiting user and item collaborative embeddings based on ratings, which is the prime purpose; (2) matching the item collaborative embeddings with item auxiliary embeddings; and (3) obtaining more discriminative item collaborative embeddings using unsupervised clustering method.
First, user and item collaborative embeddings should accurately represent the corresponding rating interactions. We obtain the user and item collaborative embeddings by FU (XU ) = U ∈ RN×D and FV (XV ) = V ∈ RN×D, respectively. Here, FU and FV denote the user and item encoding networks respectively, N is batch size, and D is the dimension of collaborative embeddings. After that, we use pairwise ranking loss LBE based on metric-based contrastive learning [10, 14]:
minLBE = − ∑
(Ui,Vj ,Vk)∈D
log exp〈Ui,Vj〉
exp〈Ui,Vj〉+ exp〈Ui,Vk〉 , (1)
where D := {(Ui,Vj ,Vk)|RSij > RSik} denotes the original preference pairs [32], and 〈·, ·〉 denotes the inner product. The loss function LBE can pull the positive items close and push the negative items away for a certain user according to his/her preference.
Second, a item’s collaborative embedding should be similar to its auxiliary embeddings to avoid the error superimposition problem [54]. We utilize a networkGV to translate the auxiliary representations into auxiliary embeddings as GV (XW ) = W ∈ RN×D. After it, the item embedding matching loss is given by LBM = ||W − V ||22. Third, similar item collaborative embeddings should be clustered in order to obtain more discriminative latent features. We adopt deep unsupervised K-Means clustering approach [24, 48] for this, and the corresponding loss is minFFT=I LBK = [ Tr(V V T )− Tr(FV V TF T ) ] , where F ∈ RK×N is the cluster indicator matrix and K denotes the cluster number.
In summary, the loss of the rating prediction module is a combination of the three losses, that is:
min FFT=I LB = LBE + ηLBM + ζLBK , (2)
where ζ and η represent the balance hyper-parameters. The optimization procedure is given as below: (1) Fixing the other variables except F , we update F through minFFT=I Tr(FV V TF T ) with singular value decomposition algorithm; (2) Fixing F , we update other variables through gradient descent methods for several iterations then go back to step (1) until it convergences. For the sake of stability, in practice, we update F every 15 iterations.

heading: 2.3 Embedding distribution alignment module

heading: 2.3.1 Overview

text:
We then introduce the embedding distribution alignment module of DisAlign. We use GV (XCj ) = C ∈ RN×D to denote the auxiliary embeddings of the cold items in the target domain. Specifically, GV (·) is a two-stream siamese network with shared weights for encoding both warm item auxiliary representation XW and cold item auxiliary representation XC . We denote pW and pC as the warm and cold item auxiliary embedding probability distributions, respectively, and denote pV as the warm
item collaborative embedding probability distribution. In CDCSR setting, pW 6= pC and pV 6= pC , because the embeddings generated from the source (warm) domain and the target (cold) domain are heterogeneous, which leads to the domain discrepancy problem. Let us consider a case where the source domain has user-book interactions while the target domain has user-movie interactions. Although books and movies share some similar characteristics, the auxiliary representations of the Book domain usually include authors and writing styles, while the auxiliary representations of the Movie domain include directors and actors, which brings discrepancy. Without embedding distribution alignment, a recommender system may recommend horror books instead of history books to a user who likes history movies rather than horror movies due to domain discrepancy, as illustrated in the left of Figure 3. After alignment, the history movies/books and horror movies/books are aligned, as is shown in the right of Figure 3, and thus the recommender system can provide more reliable results. In order to reduce the distribution discrepancy between the source and target domains, we introduce two approaches, i.e., Stein path alignment and Proxy stein path alignment.
2.3.2 Stein path alignment
As mentioned in Section 1, since the latent embeddings from two domains in CDCSR are scattered and complicated due to the fact that they may represent diverse information, previous domain adaptation methods cannot be effectively utilized to solve the distribution discrepancy problem. Therefore, we propose a new distribution alignment approach, named Stein path alignment. Stein path alignment can prompt the target samples move to the source domain through proper paths, according to the target
intra-domain structure and the probability distribution of the source domain. Stein path alignment relies on Stein Variational Gradient Descent (SVGD) [21, 42], a variational inference method that starts from a set of initial particles and iteratively updates them with an approximate steepest direction, whose main iteration process is:
zi,l = zi,l−1 + φp(zi,l−1), φp(z) = 1
N N∑ j=1 [k(z, zj)∇z log p(z) +∇zk(z, zj)] , (3)
where zi,l denotes the i-th original target sample at the l-th iteration, p(z) denotes the source probability distribution, denotes the step size, and k(x,y) = exp ( −(||x− y||22)/σ2 ) is the Gaussian kernel function with σ denoting the bandwidth. Existing researches [21, 7, 2] have proved that mean field theory can guarantee the rigorous theoretical convergence of SVGD, that is, the gradient dynamics at particle level will approach to zero: limt→+∞(1/N × ∑N i=0 φp(zi,t))→ 0.
Stein path distance. We denote zi,t as the Stein mirror point of zi,0 when SVGD convergences at the t-th iteration. We propose Stein path distance as below:
PT→S(Z) := 1
N N∑ i=0 ||zi,t − zi,0||22 = 1 N N∑ i=0 ||zi,t−1 + φS(zi,t−1)− zi,0||22 . (4)
Stein path distance quantifies the discrepancy between the source domain S and the target domain T by taking the average length of all paths from T to S through the t-th iteration. Stein path considers the source probability distribution and intra-domain structures, and thus can avoid negative transfer arisen from coarsely pairwise matching by traditional methods. Meanwhile Stein path is also explainable. Let zi,0 denote the auxiliary embedding of i-th book in the Book domain, zi,t could be taken as a similar movie in the Movie domain, e.g., the movie is based on the story of the book. The calculation of Stein path distance mainly has three steps. First, adopting kernel density estimation [30, 29, 39] with radial basis function kernel to estimate the probabilities of W and V . Second, finding the Stein mirror point of the cold item auxiliary embeddings through SVGD by Equation (3). Third, calculating the Stein path distance using Equation (4). The calculation details will be given in Appendix A.1.
Stein path loss. In summary, the better the source and target domains are aligned, the smaller the Stein path distance. Therefore, we innovatively propose Stein path loss to align the cold item auxiliary
embedding C with warm item collaborative preference V and auxiliary embedding W as below:
minLSP = PC→W (C) + PC→V (C) + ||PC→W (C)− PC→V (C)||22, (5) where the first two terms denote the Stein path distances from C to W and C to V , respectively, and the third term reinforces that these two distances should be similar.
2.3.3 Proxy Stein path alignment
Although Stein path alignment achieves satisfying performance, it has scalability problem when facing large dataset. Because all the cold items in each batch need to be used for calculating Stein path distance. Therefore, it is urgent to reduce the computation cost to accelerate the optimization process. To do this, we propose proxy Stein path approach which only needs to choose the most typical cold item proxies to represent the global properties in order to speed up the alignment process through SVGD. We now describe the main steps for finding the proxies and the optimization procedure.
Multiple-proxies algorithm. We first introduce a highly efficient multiple-proxies algorithm, which aims to find typical proxy samples in the target domain. Suppose there exists M ∈ RH×D typical proxies for the cold item auxiliary embeddings C, where H denotes the number of proxies. Let Ψ ∈ RN×H be the similarity matrix between the cold items in the target domain and the proxies. Inspired by [1, 28], we formulate the multiple-proxies optimization problem as
min M ,ψi1=1,ψij≥0 N∑ i=1 H∑ j=1 ψij ||ci −mj ||22 + α N∑ i=1 H∑ j=1 ψij logψij , (6)
where ci denotes the i-th cold item auxiliary embedding and mj denotes the j-th corresponding proxy. The entropy norm regularization term ∑N i=1 ∑H j=1 ψij logψij is set to avoid trivial solution with α denoting the regularization strength. Compared with the square norm || · ||2, the entropy norm can not only obtain a nonnegative and nonlinearly representational similarity matrix but also reduce the computational cost [1]. In summary, the multiple-proxies optimization algorithm has two main steps, i.e., (1) updating Ψ, which has closed-form solution, and (2) updating M as mj = ∑N i=1 ψijci/ ∑N i=1 ψij . The optimization could be done by repeating (1) and (2) until Ψ and M convergence. We will present the optimization details in Appendix A.2.
Proxy Stein path distance. After finding the typical proxies M and setting Ψ as a constant, we propose proxy Stein path distance according to the original Stein path as below:
P∗T→S(M) = 1
H H∑ i=0 ||mi,t −mi,0||22 = 1 H H∑ i=0 ||mi,t−1 + φS(mi,t−1)−mi,0||22 , (7)
where mi,t denotes the i-th proxy mi at the t-th iteration. Notably, in each batch, proxy Stein path only needs to move the number of proxy samples (H) in the target domain rather than the total number of samples (N ). Since H < N , proxy Stein path can reduce the time consumption on calculating the Stein path distance.
Proxy Stein path loss. Similarly to the Stein path loss, the proxy Stein path loss is given by: minLPSP = P∗C→W (M) + P∗C→V (M) + ||P∗C→W (M)− P∗C→V (M)||22. (8)
The optimization of proxy Stein path alignment mainly has four steps. The first step is adopting the multiple-proxies algorithm to figure out the typical proxies M in the target domain. The following three steps are similar as Stein path alignment mentioned in the Section 2.3.2, except that we are moving proxies M rather than C. We will present the optimization details in Appendix A.3.
Time complexity analysis. The time complexity of Stein path alignment is O(N3t1), where t1 is the iteration number. The time complexities of the multiple-proxies algorithm and proxy Stein path
alignment are O(NHt2) and O(H2Nt1), respectively, where t2 is the inner-loop iteration number. Therefore, the total time complexity of proxy Stein path alignment is O(NHt2) + O(H2Nt1) = O(NHt2 +H
2Nt1). Since H < N , proxy Stein path alignment is much cheaper than Stein path alignment. Empirically, we set H∗ = [N2 ].

heading: 2.4 Putting together

text:
The total loss of DisAlign could be obtained by combining the losses of the rating prediction module and the embedding distribution alignment module. That is, the losses of DisAlign with Stein Path (DisAlign-SP) and Proxy Stein Path (DisAlign-PSP) are:
minLDisAlign-SP = LB + λSPLSP , minLDisAlign-PSP = LB + λPSPLPSP , (9) where λSP and λPSP are hyper-parameters to balance the two types of losses. In testing phase, one can predict the missing rating in the target domain by taking the inner product of user embeddings U and cold item embeddings C.

heading: 3 Experiments

heading: 3.1 Experimental setup

text:
Datasets and Tasks. We conduct extensive experiments on two popuarly used real-world datasets, i.e., Douban and Amazon. First, the Douban dataset [50, 51] has three domains, i.e., Book, Music, and Movie, which contains ratings, reviews, tags, and item details. There are six CDCSR tasks on Douban by randomly choosing two domains as source domain and target domain respectively. Second, the Amazon dataset [49, 27] has two domains, i.e., Movies and TV (Movie), and CDs and Vinyl (Music). There are two tasks on Amazon, i.e., Amazon Movie→ Amazon Music and Amazon Music→ Amazon Movie. For both datasets, we binarize the ratings to 1 and 0. Specifically, we take the ratings higher or equal to 4 as positive and others as negative. We also filter the users and items with less than 5 interactions, following existing research [46, 51]. We list the detailed information on these datasets and tasks in Section B.1 of the supplementary material.
Baselines. We compare our proposed DisAlign with the following state-of-the-art cold-start and CDR models. (1) DropoutNet [41] inputs both auxiliary representations and collaborative filtering representations and randomly dropouts pre-trained collaborative filtering representations for training.
(2) LLAE [18] introduces semantic auto-encoder using the idea of zero-shot learning to solve the cold-start recommendation problem. (3) Heater [54] is the latest cold-start recommendation model which combines separate-training and joint-training framework to overcome the error superimposition issue. (4) WCF [26] is the first attempt to apply Wasserstein distance optimal transport for item cold-start recommendation. (5) ESAM [4] adopts attribute correlation alignment to improve longtail recommendation performance by suppressing inconsistent distribution between displayed and non-displayed items. (6) DARec [46] adopts adversarial training strategy to extract and transfer knowledge patterns for shared users across domains and achieves the state-of-the-art performance in CDR. For DropoutNet, LLAE, Heater, and WCF, we use the same setting as reported in their original papers. For DARec and ESAM, since they cannot be directly applied to cold-start tasks, we adopt the same rating prediction module as DisAlign. Note that, for a fair comparison, all the models use the same types of data and pre-processing methods during experiments.
Implemented details. We provide the implemented details of our proposed model and baselines. The auxiliary representations for XW and XC across domains include genres, themes, reviews, item profiles, etc. We split auxiliary representations into each word and adopt directional skip-gram [33] on Douban for Chinese words and apply Glove [31] on Amazon for English words to obtain the average feature representations with dimension Z = 200. We use all the user-item rating interactions in the source domain, and all the items auxiliary representations in both the source domain and the target domain for training the model, following standard evaluation for unsupervised adaptation [22, 11]. For all the experiments, we perform five random experiments and report the average results. We choose Adam [16] as optimizer, and adopt Hit Rate@20 (HR@20), Recall@20, and NDCG@20 [43] as the ranking evaluation metrics.
Hyper-parameter settings. We set batch size N = 256 for both the source and target domains. The latent embedding dimension is set to D = 128. For the rating prediction module, we set the balance hyper-parameters as η = 0.01 and ζ = 0.01, and number of cluster K = 5 for item unsupervised clustering. For the stein path alignment module, we set the moving step size as = 0.01 and the kernel bandwidth as σ = 0.5. For the proxy stein path alignment module, we set α = 0.1 and H = 64 according to Section 2.3.3. Finally, for the balance parameters, λSP and λPSP are first selected according to accuracy on Douban Movie→ Douban Book and then fixed as the best values, i.e., λSP = λPSP = 0.5. Although there are many hyper-parameters, we first optimize the hyper-parameters of the rating prediction module, and then optimize the other hyper-parameters.

heading: 3.2 Recommendation performance

text:
Results and discussion. The comparison results on Douban and Amazon datasets are shown in Table 1. From it, we can find that (1) Although Heater can get better results on conventional cold-start problem, it cannot achieve satisfying solutions on CDCSR problem since it cannot reduce the discrepancy across domains. (2) WCF obtains better performance than Heater in some tasks, but optimal transport with Wasserstein distance is easily affected by noisy samples, resulting in the over-adaptation errors in boundaries and limiting the transportation results. (3) ESAM and DARec provide correlated-attribution alignment and adversarial training to match source and target domains, while such coarsely matching methods lead to limited prediction enhancement. (4) DisAlignSP or DisAlign-PSP consistently achieves the best performance, which proves that Stein path alignment strategy can significantly improve the prediction accuracy. (5) DisAlign-PSP outperforms DisAlign-SP on several tasks, e.g., Music and Movie domains on both datasets, which demostrates
that typical proxies can filter out the outliers and improve model robustness. Besides, we further investigate the time consumption of each model on different tasks, and report the results in Figure 6. From it, we find that DisAlign-SP is the slowest, because it has to transport the whole batchsize of samples from the target domain to the source domain. In contrast, DisAlign-PSP is much faster than DisAlign-SP, and also faster than WCF and DARec, since it only needs to transport typical target proxies.
Visualization. To show the feature transferability, we visualize the t-SNE embeddings [17] of the source item auxiliary embeddings (W ) and the target item auxiliary embeddings (C). The results of Douban Movie→Douban Book are shown in Figure 5. From it, we can see that (1) Heater does not has the ability to bridge the gap across different domains, and thus the embeddings are separated in source and target domains, as shown in Figure 5(a); (2) ESAM and DARec have the tendency to draw the source and target embeddings closer, while they still have a certain distance, as shown in Figure 5(b) and Figure 5(c). This indicates that they can only align
the marginal probability distribution; (3) DisAlign-SP in Figure 5(d) depicts that the embeddings trained through Stein path alignment achieves more closer gap between the source and target domains. The visualization on Amazon dataset shows similar result, and we present it in Section B.2 of the supplementary material.

heading: 3.3 Analysis

text:
Ablation study. To study how does each module of DisAlign contribute on the final performance, we compare DisAlign with its several variants, including DisAlign-Base and DisAlign-SP(I). (1) DisAlign-Base only consists of the rating prediction module with collaborative embeddings clustering. (2) DisAlign-SP(I) only aligns the warm item auxiliary embedding W and the cold item auxiliary embedding C. The comparison results are shown in Table 1. From it, we can observe that (1) DisAlign-Base without the Stein path distribution alignment module cannot transfer knowledge from the source domain to the target domain, resulting in poor performance, (2) DisAlign-SP(I) achieves better performance than DisAlign-Base, where we only align the distributions between W and C, and (3) By extra aligning C with V , DisAlign-SP can further promote the performance of DisAlign-SP(I). Overall, the above ablation study demonstrates that our proposed embedding distribution alignment module is effective in solving the CDCSR problem.
Case study. In order to illustrate the domain discrepancy problem mentioned in the Section 2.3 (Figure 3), we visualize the cases on Douban Movie→Douban Book and Douban Book→Douban Movie. Figure 7 shows the recommendation results. The left part is the user-item interactions in the source domain where the blue and red frames indicate users like or dislike the items respectively. The middle part denotes the top-5 recommendation results for the corresponding users based on DisAlign-Base, where we can see that these users will probably dislike the recommended items in the target domain due to the lack of embedding distribution alignment. After applying Stein path alignment on the right part, the recommender system can effectively improve the results. The results indirectly demonstrate that Stein path can properly translate the items across different domains according to the latent probability distribution.
Parameter sensitivity. We finally study the effects of hyper-parameters on model performance. First, we vary λSP and λPSP in {0.1, 0.3, 0.5, 0.7, 1, 3, 5, 10} and report the results in Section B.3 of the supplementary materials. From it, we see that, the embedding distribution alignment module cannot play a central role in the training process when λSP , λPSP → 0, bringing the discrepancy between the source and target domains. When λSP and λPSP become too large, the embedding distribution alignment module will suppress the rating prediction module, which also decreases the recommendation results. The above results indicate that choosing the proper hyper-parameters to balance the embedding distribution alignment loss and rating prediction loss can effectively improve the performance of DisAlign. Then, we study the effect of embedding dimension (D) on DisAlign, and report the results in Section B.4 of the supplementary materials. We find that the recommendation accuracy of DisAlign-SP and DisAlign-PSP increase with D, indicating that larger embedding can represent user and item preferences more precisely.

heading: 4 Related work

text:
Cold-start recommendation. Existing approaches on this are mainly of two types, i.e., separatetraining and joint-training. The former models, e.g., LinMap [9] and DeepMusic [40], separate the learning of the collaborative filtering embeddings and auxiliary embeddings, and thus always lead to error superimposition [54]. The later jointly minimizes the recommendation error on the user-item interaction and transformation function, including DropoutNet [41], LLAE [18], and Heater [54]. Among them, Heater [54] is the state-of-the-art model which integrates randomized training mechanism with mixture-of-experts to provide better performance. However, the above cold-start approaches cannot adjust to the CDCSR problem due to the discrepancy across different domains.
Cross domain recommendation (CDR). According to [52], existing CDR models have three main types, i.e., transfer-based methods, clustered-based methods, and multitask-based methods. Transferbased methods [49, 25] learn a linear or nonlinear mapping function across domains. Some recent method [46] even adopts adversarial learning strategy to obtain more reliable knowledge across domains with shared users. Clustered-based methods [44] adopt co-clustering approach to learn cross-domain comprehensive embeddings by collectively leveraging single-domain and cross-domain information within a unified framework. Multi-task-based methods [15, 50, 51, 53] enable dual knowledge transfer across domains by introducing shared connection modules in neural networks. Nevertheless, conventional CDR approaches cannot solve the CSCDR problem where user-item interaction data in absent in the target domain.
Domain adaptation. Existing works on this are mainly of three types, i.e., discrepancy-based methods, adversarial-based methods, and sample-based matching methods [55, 36]. Discrepancybased methods learn the domain-invariant embeddings by the adaptation layer for moment matching, e.g., Maximum Mean Discrepancy (MMD) [3], Correlation Alignment (CORAL) [34, 35], and Center Moment Discrepancy (CMD) [47]. Recently, ESAM [4] extends CORAL by utilizing attribution alignment for domain adaptation in long-tail item recommendation. Adversarial-based methods integrate a domain discriminator for adversarial training, e.g., Domain Adversarial Neural Network (DANN) [8] and Adversarial Discriminative Domain Adaptation (ADDA) [38]. Sample-based matching methods are mainly based on the optimal transport [6, 45], which have the ability of encoding class-structure in distributions for minimizing the global transportation cost. However, the above approaches cannot work well in CDCSR setting, because the latent representations are always more scattered, complicated, and diverse.

heading: 5 Conclusion

text: In this paper, we propose Distribution Alignment (DisAlign), which includes the rating prediction module and the embedding distribution alignment module, for solving the cross-domain cold-start recommendation problem. We innovatively propose Stein path alignment and proxy Stein path alignment for embedding alignment across domains. We also conducted extensive experiments to demonstrate the superior performance of our DisAlign model. In the future, we plan to extend DisAlign to multi-domain cold-start recommendation tasks and conduct more comprehensive experiments on new datasets. We will also modify our model to adapt to the situation where there are also user-item interactions in the target domain.

heading: 6 Acknowledgments

text: This work was supported in part by the National Key R&D Program of China (No.2018YFB1403001) and sponsored by the CCF-AFSG Research Fund (No.RF20200005).

title: Leveraging Distribution Alignment via Stein Path for Cross-Domain Cold-Start Recommendation