Reinforcement learning for personalization: A systematic literature review

Abstract

The major application areas of reinforcement learning (RL) have traditionally been game playing and continuous control. In recent years, however, RL has been increasingly applied in systems that interact with humans. RL can personalize digital systems to make them more relevant to individual users. Challenges in personalization settings may be different from challenges found in traditional application areas of RL. An overview of work that uses RL for personalization, however, is lacking. In this work, we introduce a framework of personalization settings and use it in a systematic literature review. Besides setting, we review solutions and evaluation strategies. Results show that RL has been increasingly applied to personalization problems and realistic evaluations have become more prevalent. RL has become sufficiently robust to apply in contexts that involve humans and the field as a whole is growing. However, it seems not to be maturing: the ratios of studies that include a comparison or a realistic evaluation are not showing upward trends and the vast majority of algorithms are used only once. This review can be used to find related work across domains, provides insights into the state of the field and identifies opportunities for future work.

1. Introduction

For several decades, both academia and commerce have sought to develop tailored products and services at low cost in various application domains. These reach far and wide, including medicine [5,71,77,84,178,179], human-computer interaction [61,100,118], product, news, music and video recommendations [163,164,217] and even manufacturing [39,154]. When products and services are adapted to individual tastes, they become more appealing, desirable, informative, e.g. relevant to the intended user than one-size-fits all alternatives. Such adaptation is referred to as personalization [55].

Digital systems enable personalization on a grand scale. The key enabler is data. While the software on these systems is identical for all users, the behavior of these systems can be tailored based on experiences with individual users. For example, Netflix’s1

¹

https://www.netflix.com

digital video delivery mechanism includes tracking of views and ratings. These ease the gratification of diverse entertainment needs as they enable Netflix to offer instantaneous personalized content recommendations. The ability to adapt system behavior to individual tastes is becoming increasingly valuable as digital systems permeate our society.

Recently, reinforcement learning (RL) has been attracting substantial attention as an elegant paradigm for personalization based on data. For any particular environment or user state, this technique strives to determine the sequence of actions to maximize a reward. These actions are not necessarily selected to yield the highest reward now, but are typically selected to achieve a high reward in the long term. Returning to the Netflix example, the company may not be interested in having a user watch a single recommended video instantly, but rather aim for users to prolong their subscription after having enjoyed many recommended videos. Besides the focus on long-term goals in RL, rewards can be formulated in terms of user feedback so that no explicit definition of desired behavior is required [12,79].

RL has seen successful applications to personalization in a wide variety of domains. Some of the earliest work, such as [122,174,175] and [231] focused on web services. More recently, [107] showed that adding personalization to an existing online news recommendation engine increased click-through rates by 12.5%. Applications are not limited to web services, however. As an example from the health domain, [234] achieve optimal per-patient treatment plans to address advanced metastatic stage IIIB/IV non-small cell lung cancer in simulation. They state that ‘there is significant potential of the proposed methodology for developing personalized treatment strategies in other cancers, in cystic fibrosis, and in other life-threatening diseases’. An early example of tailoring intelligent tutor behavior using RL can be found in [124]. A more recent example in this domain, [74], compared the effect of personalized and non-personalized affective feedback in language learning with a social robot for children and found that personalization significantly impacts psychological valence.

Although the aforementioned applications span various domains, they are similar in solution: they all use traits of users to achieve personalization, and all rely on implicit feedback from users. Furthermore, the use of RL in contexts that involve humans poses challenges unique to this setting. In traditional RL subfields such as game-playing and robotics, for example, simulators can be used for rapid prototyping and in-silico benchmarks are well established [14,21,50,97]. Contexts with humans, however, may be much harder to simulate and the deployment of autonomous agents in these contexts may come with different concerns regarding for example safety. When using RL for a personalization problem, similar issues may arise across different application domains. An overview of RL for personalization across domains, however, is lacking. We believe this is not to be attributed to fundamental differences in setting, solution or methodology, but stems from application domains working in isolation for cultural and historical reasons.

This paper provides an overview and categorization of RL applications for personalization across a variety of application domains. It thus aids researchers and practictioners in identifying related work relevant to a specific personalization setting, promotes the understanding of how RL is used for personalization and identifies challenges across domains. We first provide a brief introduction of the RL framework and formally introduce how it can be used for personalization. We then present a framework to classify personalization settings by. The purpose of this framework is for researchers with a specific setting to identify relevant related work across domains. We then use this framework in a systematic literature review (SLR). We investigate in which settings RL is used, which solutions are common and how they are evaluated: Section 5 details the SLR protocol, results and analysis are described in Section 6. All data collected has been made available digitally [46]. Finally, we conclude with current trends challenges in Section 7.

2. Reinforcement learning for personalization

RL considers problems in the framework of Markov decision processes or MDPs. In this framework, an agent collects rewards over time by performing actions in an environment as depicted in Fig. 1. The goal of the agent is to maximize the total amount of collected rewards over time. In this section, we formally introduce the core concepts of MDPs and RL and include some strategies to personalization without aiming to provide an in depth introduction to RL. Following [188], we consider the related multi-armed and contextual bandit problems as special cases of the full RL problem where actions do not affect the environment and where observations of the environment are absent or present respectively. We refer the reader to [188,220] and [190] for a full introduction.

Fig. 1.

The agent-environment in RL for personalization from [188].

An MDP is defined as a tuple $⟨\mathit{S}\mathrm{,}\mathit{A}\mathrm{,}\mathit{T}\mathrm{,}\mathit{R}\mathrm{,}\mathit{\gamma }⟩$ where $\mathit{S}\in \{{\mathit{s}}_1\mathrm{,}\dots \mathrm{,}{\mathit{s}}_{\mathit{n}}\}$ is a finite set of states, $\mathit{A}\in \{{\mathit{a}}_1\mathrm{,}\dots \mathrm{,}{\mathit{a}}_{\mathit{m}}\}$ a finite set of system actions, $\mathit{T}:\mathit{S}\times \mathit{A}\times \mathit{S}\to [0\mathrm{,}1]$ a probabilistic transition function, $\mathit{R}:\mathit{S}\times \mathit{A}\to \mathbb{R}$ a reward function and $\mathit{\gamma }\in [0\mathrm{,}1]$ a factor to discount future rewards. At each time step t, the system is confronted with some state ${\mathit{s}}_{\mathit{t}}$ , performs some action ${\mathit{a}}_{\mathit{t}}$ which yields a reward ${\mathit{r}}_{\mathit{t}+1}:\mathit{R}\mathrm{(}{\mathit{s}}_{\mathit{t}}\mathrm{,}{\mathit{a}}_{\mathit{t}}\mathrm{)}$ and some state ${\mathit{s}}_{\mathit{t}+1}$ following the probability distribution $\mathit{T}\mathrm{(}{\mathit{s}}_{\mathit{t}}\mathrm{,}{\mathit{a}}_{\mathit{t}}\mathrm{)}$ . A series of these states, actions and rewards from the onset to some terminal state T is called a trajectory $\mathit{t}\mathit{r}:⟨{\mathit{s}}_{{\mathit{t}}_0}\mathrm{,}{\mathit{a}}_{{\mathit{t}}_0}\mathrm{,}{\mathit{r}}_{{\mathit{t}}_1}\mathrm{,}{\mathit{s}}_{{\mathit{t}}_1}\mathrm{,}\dots \mathrm{,}{\mathit{s}}_{\mathit{T}-1}\mathrm{,}{\mathit{a}}_{\mathit{T}-1}\mathrm{,}{\mathit{r}}_{\mathit{T}}\mathrm{,}{\mathit{s}}_{\mathit{T}}⟩$ . These trajectories typically contain the interaction histories for users with the system. A single trajectory can describe a single session of the user interacting with the system or can contain many different separate sessions. Multiple trajectories may be available in a data set $\mathit{D}\in \{\mathit{t}{\mathit{r}}_1\mathrm{,}\dots \mathrm{,}\mathit{t}{\mathit{r}}_{\ell }\}$ . The goal is to find a policy ${\mathit{\pi }}^{\ast }$ out of all $\mathrm{\Pi }:\mathit{S}\times \mathit{A}\to [0\mathrm{,}1]$ that maximizes the sum of future rewards at any t, given an end time T: $$\begin{array}{}\text{(1)}& {\mathit{G}}_{\mathit{t}}:{\displaystyle \sum }_{\mathit{k}=\mathit{t}}^{\mathit{T}-1}{\mathit{\gamma }}^{\mathit{k}-\mathit{t}}{\mathit{r}}_{\mathit{k}+1}.\end{array}$$ If some expectation ${\mathbb{E}}_{\mathit{\pi }}$ over the future reward for some policy π can be formulated, a value can be assigned to some state s given that policy: $$\begin{array}{}\text{(2)}& {\mathit{V}}_{\mathit{\pi }}\mathrm{(}\mathit{s}\mathrm{)}={\mathbb{E}}_{\mathit{\pi }}[{\mathit{G}}_{\mathit{t}}|{\mathit{s}}_{\mathit{t}}=\mathit{s}].\end{array}$$ Similarly, a value can be assigned to an action a in a state s: $$\begin{array}{}\text{(3)}& {\mathit{Q}}_{\mathit{\pi }}\mathrm{(}\mathit{s}\mathrm{,}\mathit{a}\mathrm{)}={\mathbb{E}}_{\mathit{\pi }}[{\mathit{G}}_{\mathit{t}}|{\mathit{s}}_{\mathit{t}}=\mathit{s}\mathrm{,}{\mathit{a}}_{\mathit{t}}=\mathit{a}].\end{array}$$ Now the optimal policy ${\mathit{\pi }}^{\ast }$ should satisfy $\forall \mathit{s}\in \mathit{S}\mathrm{,}\forall \mathit{\pi }\in \mathrm{\Pi }:{\mathit{V}}_{{\mathit{\pi }}^{\ast }}\mathrm{(}\mathit{s}\mathrm{)}⩾{\mathit{V}}_{\mathit{\pi }}\mathrm{(}\mathit{s}\mathrm{)}$ and $\forall \mathit{s}\in \mathit{S}\mathrm{,}\mathit{a}\in \mathit{A}\mathrm{,}\forall \mathit{\pi }\in \mathrm{\Pi }:{\mathit{Q}}_{{\mathit{\pi }}^{\ast }}\mathrm{(}\mathit{s}\mathrm{,}\mathit{a}\mathrm{)}⩾{\mathit{Q}}_{\mathit{\pi }}\mathrm{(}\mathit{s}\mathrm{,}\mathit{a}\mathrm{)}$ . Assuming a suitable ${\mathbb{E}}_{{\mathit{\pi }}^{\ast }}[\mathit{G}]$ , ${\mathit{\pi }}^{\ast }$ consists of selecting the action that is expected to yield the highest sum of rewards: $$\begin{array}{}\text{(4)}& {\mathit{\pi }}^{\ast }\mathrm{(}\mathit{s}\mathrm{)}=\underset{\mathit{a}}{argmax}{\mathit{Q}}_{{\mathit{\pi }}^{\ast }}\mathrm{(}\mathit{s}\mathrm{,}\mathit{a}\mathrm{)}\mathrm{,}\forall \mathit{s}\in \mathit{S}\mathrm{,}\mathit{a}\in \mathit{A}.\end{array}$$

With these definitions in place, we now turn to methods of finding ${\mathit{\pi }}^{\ast }$ . Such methods can be categorized by considering which elements of the MDP are known. Generally, S, A and γ are determined upfront and known. T and R, on the other hand, may or may not be known. If they are both known, the expectation ${\mathbb{E}}_{\mathit{\pi }}[\mathit{G}]$ is directly available and a corresponding ${\mathit{\pi }}^{\ast }$ can be found analytically. In some settings, however, T and R may be unknown and ${\mathit{\pi }}^{\ast }$ must be found empirically. This can be done by estimating T, R, V, Q and finally ${\mathit{\pi }}^{\ast }$ or a combination thereof using data set D. Thus, if we include approximations in Eq. (4), we get: $$\begin{array}{}\text{(5)}& \widehat{{\mathit{\pi }}^{\ast }}\mathrm{(}\mathit{s}\mathrm{)}|\mathit{D}=\underset{\mathit{a}}{argmax}{\hat{\mathit{Q}}}_{\widehat{{\mathit{\pi }}^{\ast }}}\mathrm{(}\mathit{s}\mathrm{,}\mathit{a}\mathrm{)}|\mathit{D}\mathrm{,}\forall \mathit{s}\in \mathit{S}\mathrm{,}\mathit{a}\in \mathit{A}.\end{array}$$ As D may lack the required trajectories for a reasonable ${\mathbb{E}}_{\widehat{{\mathit{\pi }}^{\ast }}}[\mathit{G}]$ and may even be empty initially, exploratory actions can be selected to enrich D. Such actions need not follow $\widehat{{\mathit{\pi }}^{\ast }}$ as in Eq. (5) but may be selected through some other mechanism such as sampling from the full action set A randomly.

Having introduced RL briefly, we continue by exploring some strategies in applying this framework to the problem of personalizing systems. We return to our earlier example of a video recommendation task and consider a set of n users $\mathit{U}\in \{{\mathit{u}}_1\mathrm{,}\dots \mathrm{,}{\mathit{u}}_{\mathit{n}}\}$ . A first way to adapt software systems to an individual users’ needs is to define a separate environment, corresponding MDP and RL agent for each user. The overall goal becomes to find a set of optimal policies $\{{\mathit{\pi }}_1^{\ast }\mathrm{,}\dots \mathrm{,}{\mathit{\pi }}_{\mathit{n}}^{\ast }\}$ for a set of environments formalized as MDPs $\mathit{M}:\{{\mathit{M}}_1:⟨{\mathit{S}}_1\mathrm{,}{\mathit{A}}_1\mathrm{,}{\mathit{T}}_1\mathrm{,}{\mathit{R}}_1\mathrm{,}{\mathit{\gamma }}_1⟩\mathrm{,}\dots \mathrm{,}{\mathit{M}}_{\mathit{n}}:⟨{\mathit{S}}_{\mathit{n}}\mathrm{,}{\mathit{A}}_{\mathit{n}}\mathrm{,}{\mathit{T}}_{\mathit{n}}\mathrm{,}{\mathit{R}}_{\mathit{n}}\mathrm{,}{\mathit{\gamma }}_{\mathit{n}}⟩\}$ . In the case of approximations as in Eq. (5), these are made per MDP based on data set ${\mathit{D}}_{\mathit{i}}$ with trajectories only involving that environment. In the running example, videos would be recommended to a user based on previous video recommendations and selections of that particular user. The benefit of isolated MDPs is that differences between ${\mathit{T}}_{\mathit{i}}$ and ${\mathit{T}}_{\mathit{j}}$ or between ${\mathit{R}}_{\mathit{i}}$ and ${\mathit{R}}_{\mathit{j}}$ for MDPs ${\mathit{M}}_{\mathit{i}}\ne {\mathit{M}}_{\mathit{j}}$ are handled naturally, e.g. such differences do not make ${\mathbb{E}}_{{\mathit{\pi }}_{\mathit{i}}}[\mathit{G}]$ incorrect. On the other hand, similarities between ${\mathit{T}}_{\mathit{i}}\mathrm{,}{\mathit{T}}_{\mathit{j}}$ and ${\mathit{R}}_{\mathit{i}}\mathrm{,}{\mathit{R}}_{\mathit{j}}$ cannot be used. For example, consider a video recommendation task with ${\mathit{S}}_{\mathit{i}\mathit{j}}=\{\mathit{morning}\mathrm{,}\mathit{afternoon}\mathrm{,}\mathit{night}\}$ . If two users ${\mathit{u}}_{\mathit{i}}\ne {\mathit{u}}_{\mathit{j}}$ are both using a video service in the $\mathit{morning}$ state, they may both like to watch a breakfast news broadcast whereas in the $\mathit{night}$ state they may both prefer a talk show. Learning such patterns for each environment individually may require a substantial number of trajectories and may be infeasible in some settings, such as those where users cannot be identified across trajectories or those where each user is expected to contribute only one trajectory to ${\mathit{D}}_{\mathit{i}}$ .

An alternative approach is to define is a single agent and MDP with user-specific information in the state space S and learn a single ${\mathit{\pi }}^{\ast }$ for all users [47]. In some settings, users can be described using a function that returns a vector representation of the l features that characterize a user $\mathit{\varphi }:\mathit{U}\to ⟨{\mathit{\varphi }}_1\mathrm{(}\mathit{U}\mathrm{)}\mathrm{,}\dots \mathrm{,}{\mathit{\varphi }}_{\mathit{l}}\mathrm{(}\mathit{U}\mathrm{)}⟩$ . Such a vector could for example contain age, favourite genre and viewing history. If two users ${\mathit{u}}_{\mathit{j}}\ne {\mathit{u}}_{\mathit{i}}$ have both enjoyed the first “Lord of the Rings” movie and viewer ${\mathit{u}}_{\mathit{j}}$ has followed up on a recommendation of its sequel by the system then this sequel may be a suitable recommendation for the other viewer ${\mathit{u}}_{\mathit{i}}$ as well. Generally, this approach can be valuable when it is unclear which elements of trajectories of users ${\mathit{u}}_{\mathit{j}}$ should be used in determining ${\mathit{\pi }}_{\mathit{i}}^{\ast }$ . Conceptually, finding ${\mathit{\pi }}^{\ast }$ now includes determining ${\mathit{u}}_{\mathit{i}}$ ’s preference for actions given a state and determining the relationship between user preferences. This approach should therefore be able to overcome the negative transfer problem described below when enough trajectories are available. The growth in state space size, on the other hand, may require an exorbitant number of trajectories in D due to the curse of dimensionality [15]. Thus, ϕ is to be carefully designed or dimensionality reduction techniques are to be used in approaches following this strategy. As a closing remark on this approach to personalization, we note that the distinction between task-related and user-specific information is somewhat artificial as S may already contain $\mathit{\varphi }\mathrm{(}\mathit{U}\mathrm{)}$ in many practical settings and we stress that the distinction is made for illustrative purposes here.

A third category of approaches can be considered as a middle ground between learning a single ${\mathit{\pi }}^{\ast }$ and learning a ${\mathit{\pi }}_{\mathit{i}}^{\ast }$ per user. It is motivated by the idea that users and corresponding environments may be similar. If this is the case, then trajectories ${\mathit{D}}_{\mathit{j}}$ from some similar environment ${\mathit{M}}_{\mathit{j}}\ne {\mathit{M}}_{\mathit{i}}$ may prove useful in estimating ${\mathbb{E}}_{{\mathit{\pi }}_{\mathit{i}}}[\mathit{G}]$ . One such an approach is based on clustering [54,75,124,191]. Formally, it requires $\mathit{q}⩽\mathit{n}$ groups $\mathit{G}\in \{{\mathit{g}}_1\mathrm{,}\dots \mathrm{,}{\mathit{g}}_{\mathit{q}}\}$ and a mapping function $\mathrm{\Phi }:\mathit{M}\to \mathit{G}$ . In practice, this mapping function is typically defined on the level of users U or the feature representation $\mathit{\varphi }\mathrm{(}\mathit{U}\mathrm{)}$ . An RL agent is defined for every ${\mathit{g}}_{\mathit{p}}$ and interacts with all environments ${\mathit{M}}_{\mathit{i}}\mathrm{,}{\mathit{M}}_{\mathit{j}}\mathrm{,}\mathrm{\Phi }\mathrm{(}{\mathit{M}}_{\mathit{i}}\mathrm{)}=\mathrm{\Phi }\mathrm{(}{\mathit{M}}_{\mathit{j}}\mathrm{)}={\mathit{g}}_{\mathit{p}}$ . Trajectories in ${\mathit{D}}_{\mathit{i}}$ and ${\mathit{D}}_{\mathit{j}}$ are concatenated or pooled to form a single ${\mathit{D}}_{\mathit{p}}$ which is used to approximate ${\mathbb{E}}_{\widehat{{\mathit{\pi }}_{\mathit{p}}}}[\mathit{G}]$ for all ${\mathit{M}}_{\mathit{i}}\mathrm{,}{\mathit{M}}_{\mathit{j}}$ . A combined ${\mathit{D}}_{\mathit{p}}$ may be orders of magnitude bigger than an isolated ${\mathit{D}}_{\mathit{i}}$ , which may result in a much better approximation ${\mathbb{E}}_{\widehat{{\mathit{\pi }}_{\mathit{p}}}}[\mathit{G}]|{\mathit{D}}_{\mathit{p}}$ and a resulting $\widehat{{\mathit{\pi }}_{\mathit{p}}^{\ast }}\mathrm{(}\mathit{s}\mathrm{)}|{\mathit{D}}_{\mathit{p}}$ that yields a higher reward in all environments. For example, users of the video recommendation service may be clustered by age and users in the ‘infant’ cluster may generally prefer children’s movies over history documentaries. A related approach similarly uses trajectories ${\mathit{D}}_{\mathit{j}}$ of other environments ${\mathit{M}}_{\mathit{j}}\ne {\mathit{M}}_{\mathit{i}}$ but still aims to find environment-specific ${\mathit{\pi }}_{\mathit{i}}^{\ast }$ . Trajectories in ${\mathit{D}}_{\mathit{j}}$ are weighted during estimation of ${\mathbb{E}}_{{\mathit{\pi }}_{\mathit{i}}}[\mathit{G}]$ using some weighting scheme. This can be understood as a generalization of the pooling approach. First, recall that $\mathrm{\Phi }:\mathit{M}\to \mathit{G}$ for the pooling approach and note that it can be rewritten to $\mathrm{\Phi }:\mathit{M}\times \mathit{M}\to \{0\mathrm{,}1\}$ . The weighting scheme, now, is a generalization where $\mathrm{\Phi }:\mathit{M}\times \mathit{M}\to \mathbb{R}$ . Finding a suitable Φ can be challenging in itself and depends on the availability of user features, trajectories and the task at hand. Typical strategies are to define Φ in terms of similarity of feature representations of users $[\mathit{\varphi }\mathrm{(}{\mathit{u}}_{\mathit{i}}\mathrm{)}\mathrm{,}\mathit{\varphi }\mathrm{(}{\mathit{u}}_{\mathit{j}}\mathrm{)}]$ or similarity of ${\mathit{D}}_{\mathit{i}}\mathrm{,}{\mathit{D}}_{\mathit{j}}$ . The two previous approaches work under the assumption that ${\mathit{T}}_{\mathit{i}}\mathrm{,}{\mathit{T}}_{\mathit{j}}$ and ${\mathit{R}}_{\mathit{i}}\mathrm{,}{\mathit{R}}_{\mathit{j}}$ are similar and that Φ is suitable. If either of these assumptions is not met, pooling data may result in a policy that is suboptimal for both ${\mathit{M}}_{\mathit{i}}$ and ${\mathit{M}}_{\mathit{j}}$ . This phenomenon is typically referred to as the negative transfer problem [146].

3. Algorithms

In this section we provide an overview of specific RL techniques and algorithms used for personalization. This overview is the result of our systematic literature review as can be seen in Table 4. Figure 2 contains a diagram of the discussed techniques. We start with a subset of the full RL problem known as k-armed bandits. We bridge the gap towards the full RL setting with contextual bandits approaches. Then, value-based and policy-gradient RL methods are discussed.

Fig. 2.

Overview of types of RL algorithms discussed in this section and the number of uses in publications included in this survey. See Table 4 for a list of all (families of) algorithms used by more than one publication.

3.1. Multi-armed bandits

Multi-armed bandits is a simplified setting of RL. As a result, it is often used to introduce basic learning methods that can be extended to full RL algorithms [188]. In the non-associative setting, the objective is to learn how to act optimally in a single situation. Formally, this setting is equivalent to an MDP with a single state. In the associative or contextual version of this setting, actions are taken in more than one situation. This setting is closer to the full RL problem yet it lacks an important trait of full RL, namely that the selected action affects the situation. Both associative and non-associative multi-armed bandit approaches do not take into account temporal separation of actions and related rewards.

In general, multi-armed bandit solutions are not suitable when success is achieved by sequences of actions. Non-associative k-armed bandits solutions are only applicable when context is not important. This makes them generally unsuitable for personalizaton as it typically utilizes different personal contexts for different users by offering a different functionality. In some niche areas, however, k-armed bandits are applicable and can be very attractive due to formal guarantees on their performance. If context is of importance, contextual bandit approaches provide a good starting point for personalizing an application. These approaches hold a middle ground between non-associative multi-armed bandits and full RL solutions in terms of modeling power and ease of implementation. Their theoretical guarantees on optimality are less strong than their k-armed counterparts but they are easier to implement, evaluate and maintain than full RL solutions.

3.1.1. k-Armed bandits

In a k-armed bandit setting, one is constantly faced with the choice between k different actions [188]. Depending on the selected action, a scalar reward is obtained. This reward is drawn from a stationary probability distribution. It is assumed that an independent probability distribution exists for every action. The goal is to maximize the expected total reward over a certain period of time. Still considering the k-armed bandit setting, we assign a value $\mathit{Q}\mathrm{(}\mathit{a}\mathrm{)}$ to each of the k actions and define this value as the expected reward given that the action was selected. The expected reward given that an action a is selected is defined as follows: $$\begin{array}{}\text{(6)}& \mathit{Q}\mathrm{(}\mathit{a}\mathrm{)}=\mathbb{E}[{\mathit{r}}_{\mathit{t}}|{\mathit{a}}_{\mathit{t}}=\mathit{a}].\end{array}$$

In a trivial problem setting, one knows the exact value of each action and selecting the action with the highest value would constitute the optimal policy. In more realistic problems, it is fair to assume that one cannot know the values of the actions exactly. In this case, one can estimate the value of an action. We denote this estimated value with $\hat{\mathit{Q}}\mathrm{(}\mathit{a}\mathrm{)}$ and our goal is to have estimate $\hat{\mathit{Q}}\mathrm{(}\mathit{a}\mathrm{)}$ as close to the true $\mathit{Q}\mathrm{(}\mathit{a}\mathrm{)}$ as possible.

At each time step t, estimates of the values of actions are obtained. Always selecting the actions with the highest estimated value is called greedy action selection. In this case we are exploiting the knowledge we have built about the values of the actions. When we select actions with a lower expected value, we say we are exploring. In this case we are improving the estimates of values for these actions. In the balancing act of exploration and exploitation, we opt for exploitation to maximize the expected total reward for the next step, while opting for exploration could results in higher expected total reward in the long run.

3.1.2. Action-value methods for multi-armed bandits

Action-value methods [188] denote a collections of methods used for estimating the values of actions. The most natural way of estimating the action-values is to average the rewards that were observed. This method is called the sample-average method. The value estimate ${\hat{\mathit{Q}}}_{\mathit{\pi }}\mathrm{(}\mathit{a}\mathrm{)}$ is then defined as: $$\begin{array}{}\text{(7)}& \hat{\mathit{Q}}\mathrm{(}\mathit{a}\mathrm{)}={\displaystyle \frac{{\sum }_{\mathit{i}=1}^{\mathit{t}-1}{\mathit{r}}_{\mathit{i}}·{\mathbb{1}}_{{\mathit{a}}_{\mathit{i}}=\mathit{a}}}{{\sum }_{\mathit{i}=1}^{\mathit{t}-1}{\mathbb{1}}_{{\mathit{a}}_{\mathit{i}}=\mathit{a}}}}\mathrm{,}\end{array}$$ where ${\mathbb{1}}_{{\mathit{a}}_{\mathit{i}}=\mathit{a}}$ is 1 when ${\mathit{a}}_{\mathit{i}}=\mathit{a}$ is true and 0 otherwise. A default value is assigned to $\hat{\mathit{Q}}\mathrm{(}\mathit{a}\mathrm{)}$ when the denominator is zero. As the denominator approaches infinity, the estimate $\hat{\mathit{Q}}\mathrm{(}\mathit{a}\mathrm{)}$ converges to the true $\mathit{Q}\mathrm{(}\mathit{a}\mathrm{)}$ . Again, the most basic way of selecting actions is the greedy action selection method. Here the action with the highest value is selected. In the case of a tie, one action is selected using tie-breaking methods such as random selection. Greedy action selection is defined as follows for any time point t: $$\begin{array}{}\text{(8)}& {\mathit{a}}_{\mathit{t}}=\underset{\mathit{a}}{argmax}\hat{\mathit{Q}}\mathrm{(}\mathit{a}\mathrm{)}.\end{array}$$

Greedy action selection only exploits knowledge built up using the action-value method and only maximizes the immediate reward. This can lead to incorrect action-value approximations because actions with e.g. low estimated but high actual values are not sampled. An improvement over this greedy action selection is to randomly explore with a small probability ϵ. This method is named the ϵ-greedy action selection. A benefit of this method is that, while it is relatively simple, in the limit $\hat{\mathit{Q}}\mathrm{(}\mathit{a}\mathrm{)}$ will converge to $\mathit{Q}\mathrm{(}\mathit{a}\mathrm{)}$ [188]. This indicates that the probability of selecting the optimal action is then greater than $1-\mathit{ϵ}$ which is near certainty.

3.1.3. Incremental implementation

In Section 3.1.2 we discussed a method to estimate action-values using sample-averaging. To ensure the usability of these method in real-world applications, we need to be able to compute these values in an efficient way. Assume a setting with one action. At each iteration j a reward ${\mathit{r}}_{{\mathit{t}}_{\mathit{j}}}$ is obtained after selecting an action. Let ${\hat{\mathit{Q}}}_{\mathit{n}}\mathrm{(}\mathit{a}\mathrm{)}$ denote the estimate value of the action after $\mathit{n}-1$ iterations. We can then define: $$\begin{array}{}\text{(9)}& {\hat{\mathit{Q}}}_{\mathit{n}}\mathrm{(}\mathit{a}\mathrm{)}={\displaystyle \frac{{\mathit{r}}_{{\mathit{t}}_1}+{\mathit{r}}_{{\mathit{t}}_2}+{\mathit{r}}_{{\mathit{t}}_3}+\cdots +{\mathit{r}}_{{\mathit{t}}_{\mathit{n}-1}}}{\mathit{n}-1}}.\end{array}$$

Using this approach would mean storing the values of all the rewards to recalculate ${\hat{\mathit{Q}}}_{\mathit{n}}\mathrm{(}\mathit{a}\mathrm{)}$ from scratch at every iteration. There is however a more efficient way for calculating ${\hat{\mathit{Q}}}_{\mathit{n}}\mathrm{(}\mathit{a}\mathrm{)}$ that is constant in memory and computation time. Rewriting it yields the following update rule: $$\begin{array}{}\text{(10)}& {\hat{\mathit{Q}}}_{\mathit{n}+1}\mathrm{(}\mathit{a}\mathrm{)}={\hat{\mathit{Q}}}_{\mathit{n}}\mathrm{(}\mathit{a}\mathrm{)}+{\displaystyle \frac{1}{\mathit{n}}}[{\mathit{r}}_{{\mathit{t}}_{\mathit{n}}}-{\hat{\mathit{Q}}}_{\mathit{n}}\mathrm{(}\mathit{a}\mathrm{)}]\mathrm{,}\end{array}$$ where the term ${\hat{\mathit{Q}}}_{\mathit{n}}\mathrm{(}\mathit{a}\mathrm{)}$ represents the old estimate, $[{\mathit{r}}_{\mathit{n}}-{\hat{\mathit{Q}}}_{\mathit{n}}\mathrm{(}\mathit{a}\mathrm{)}]$ the error in the estimate we made of the reward and $\frac{1}{\mathit{n}}$ the learning rate.

3.1.4. UCB: Upper-confidence bound

The greedy and ϵ-greedy action selection methods were discussed in Section 3.1.2 and it was introduced that exploration is required to establish good action-value estimates. Although ϵ-greedy explores all actions eventually, it does so randomly. A better way of exploration would take into account the action-value’s proximity to the optimal value and the uncertainty in the value estimations. Intuitively, we want a selected action a to either provide a good immediate reward or else some very useful information in updating $\hat{\mathit{Q}}\mathrm{(}\mathit{a}\mathrm{)}$ . An approach that uses this idea is the upper confidence bound action selection (UCB) method [7,65,188]. UCB is defined as follows at time step t: $$\begin{array}{}\text{(11)}& {\mathit{a}}_{\mathit{t}}=\underset{\mathit{a}}{argmax}[{\hat{\mathit{Q}}}_{\mathit{n}}\mathrm{(}\mathit{a}\mathrm{)}+\mathit{c}·\sqrt{{\displaystyle \frac{ln\mathit{t}}{{\mathit{N}}_{\mathit{t}}\mathrm{(}\mathit{a}\mathrm{)}}}}]\mathrm{,}\end{array}$$ where ${\mathit{N}}_{\mathit{t}}\mathrm{(}\mathit{a}\mathrm{)}$ is how often action a was chosen up to time t and $\mathit{c}\mathrm{>}0$ is a parameter to control the rate of exploration. The square root term denotes the level of uncertainty in the approximation of the value of action a. Hence, UCB provides an upper bound for the true value of the action a. Here, c is used to define the confidence level. When the action a is selected often, ${\mathit{N}}_{\mathit{t}}\mathrm{(}\mathit{a}\mathrm{)}$ will become larger which leads the uncertainty term to decrease. On the other hand, if the action a is not selected very often, t increases and so does the uncertainty term.

k-Armed bandit approaches address the trade-off between exploitation and exploration directly. It has been shown that the difference between the obtained rewards and optimal rewards, or the regret, is at best logarithmic in the number of iterations n in the absence of prior knowledge of the action value distributions and in the absence of context [102]. UCB algorithms with a regret logarithmic in and uniformly distributed over n exist [7]. This makes them a very interesting choice when strong theoretical guarantees on performance are required.

Whether these algorithms are suitable, however, depends on the setting at hand. If there is a large number of actions to choose from or when the task is not stationary k-armed bandits are typically too simplistic. In a news recommendation task, for example, exploration may take longer than an item stays relevant. Additionally, k-armed bandits are not suitable when action values are conditioned on the situation at hand, that is: when a single action results in a different reward based on e.g. time-of-day or user-specific information such as in Section 2. In these scenarios, the problem formalization of contextual bandits and the use of function approximation are of interest.

3.1.5. Contextual bandits

In the previous sections, action-values where not associated with different situations. In this section we extend the non-associative bandit setting to the associative setting of contextual bandits. Assume a setting with n k-armed bandits problems. At each time step t one encounters a situation with a randomly selected k-armed bandits problem. We can use some of the approaches that were discussed to estimate the action values. However, this is only possible if the true action-values change slowly between the different n problems [188]. Add to this setting the fact that now at each time t a distinctive piece of information is provided about the underlying k-armed bandit which is not the actual action value. Using this information we can now learn a policy that uses the distinctive information to associate the k-armed bandit with the best action to take. This approach is called contextual bandits and uses trial-and-error to search for the optimal actions and associates these actions with situation in which they perform optimally. This type of algorithm is positioned between k-armed bandits and full RL. The similarity with RL lies in the fact that a policy is learned while the association with k-armed bandits stems from the fact that actions only affect immediate rewards. When actions are allowed to affect the next situation as well then we are dealing with RL.

3.1.6. Function approximation: LinUCB and CLUB

Despite the good theoretical characteristics of the UCB algorithm, it is not often used in the contextual setting in practice. The reason is that in practice, state and action spaces may be very large and although UCB is optimal in the uninformed case, we may do better if we use obtained information across actions and situations. Instead of maintaining isolated sample-average estimates per action or per state-action pair such as in Sections 3.1.2 and 3.1.5, we can estimate a parametric payoff function approximated from data. The parametric function takes some feature description of actions for k-armed bandit settings and state-action pairs for the contextual bandit setting and output some estimated $\widehat{{\mathit{Q}}_{\mathit{\theta }}\mathrm{(}\mathit{a}\mathrm{)}}$ . Here, we focus on the contextual-bandit algorithms LinUCB and CLUB.

LinUCB (Linear Upper-Confidence Bound) uses linear function approximation to calculate the confidence interval efficiently in closed form [107]. Define the expected payoff for action a with the d-dimensional featurized state ${\mathit{s}}_{\mathit{t}\mathrm{,}\mathit{a}}$ and ${\mathrm{\Theta }}_{\mathit{a}}^{\ast }$ a vector of unknown parameters as follows: $$\begin{array}{}\text{(12)}& \mathbb{E}[{\mathit{r}}_{\mathit{a}}|{\mathit{s}}_{\mathit{a}}]={\mathit{s}}_{\mathit{a}}^{\mathit{T}}{\mathrm{\Theta }}_{\mathit{a}}^{\ast }.\end{array}$$ Using ridge regression, an estimate of ${\hat{\mathrm{\Theta }}}_{\mathit{a}}$ can be obtained [107]. Consequently, it can be shows that for any $\mathit{\sigma }\mathrm{>}0$ and ${\mathit{s}}_{\mathit{a}}\in {\mathbb{R}}^{\mathit{d}}$ with $\mathit{\alpha }=1+\sqrt{ln\mathrm{(}\frac{2}{\mathit{\sigma }}\mathrm{)}\mathrm{/}2}$ a reasonably tight estimate for the expected payoff of arm a can be obtained as follows: $$\begin{array}{}\text{(13)}& {\mathit{a}}_{\mathit{t}}=\underset{\mathit{a}}{argmax}[{\mathit{s}}_{\mathit{a}}^{\mathit{T}}{\mathrm{\Theta }}_{\mathit{a}}^{\ast }+\mathit{\alpha }\sqrt{{\mathit{s}}_{\mathit{a}}^{\mathit{T}}{\mathit{A}}_{\mathit{a}}^{-1}{\mathit{s}}_{\mathit{a}}}]\mathrm{,}\end{array}$$ where ${\mathit{A}}_{\mathit{a}}^{-1}={\mathit{D}}_{\mathit{a}}^{\mathit{T}}{\mathit{D}}_{\mathit{a}}+{\mathit{I}}_{\mathit{d}}$ and ${\mathit{D}}_{\mathit{a}}$ a design matrix of dimension m x d whose rows are the m contexts that are observed, ${\mathit{b}}_{\mathit{a}}\in {\mathbb{R}}^{\mathit{m}}$ the corresponding response vector and ${\mathit{I}}_{\mathit{d}}$ the d x d identity matrix [107].

Similar to LinUCB, CLUB (Clustering of bandits) utilizes the linear bandit algorithm for payoff estimation [69]. In contrast to LinUCB, CLUB uses adaptive clustering in order to speed up the learning process. The main idea is to use confidence balls of user models estimate user similarity and share feedback across similar users. CLUB can thus be understood as a cluster-based alternative (see Section 2) to LinUCB algorithm.

3.2. Value-based RL

In value based RL, we learn an estimate V of the optimal value function ${\mathit{V}}_{{\mathit{\pi }}^{\ast }}$ for a given policy π. We do this with the aim of finding ${\mathit{\pi }}^{\ast }$ . Temporal-difference (TD) prediction is a method that learns from raw experiences without having to build a model of the environment the policy is interacting with [188,199]. In this section, we discuss various RL algorithms based on TD prediction.

3.2.1. Sarsa: On-policy temporal-difference RL

Sarsa is an on-policy temporal-difference method that learns an action-value function [181,188]. Given the current behaviour policy π, we estimate $\widehat{{\mathit{Q}}_{\mathit{\pi }}}\mathrm{(}\mathit{a}\mathrm{)}$ $\forall \mathit{s}$ , and a. This is done using transitions from state-action pair to state-action pair. Events of the form $⟨{\mathit{s}}_{\mathit{t}}\mathrm{,}{\mathit{a}}_{\mathit{t}}\mathrm{,}{\mathit{r}}_{\mathit{t}+1}\mathrm{,}{\mathit{s}}_{\mathit{t}+1}\mathrm{,}{\mathit{a}}_{\mathit{t}+1}⟩$ are used in the following update rule to estimate the state-action values: $$\begin{array}{}\text{(14)}& {\hat{\mathit{Q}}}_{\mathit{\pi }}\mathrm{(}{\mathit{s}}_{\mathit{t}}\mathrm{,}{\mathit{a}}_{\mathit{t}}\mathrm{)}={\hat{\mathit{Q}}}_{\mathit{\pi }}\mathrm{(}{\mathit{s}}_{\mathit{t}}\mathrm{,}{\mathit{a}}_{\mathit{t}}\mathrm{)}+\mathit{\alpha }[{\mathit{r}}_{\mathit{t}+1}+\mathit{\gamma }{\hat{\mathit{Q}}}_{\mathit{\pi }}\mathrm{(}{\mathit{s}}_{\mathit{t}+1}\mathrm{,}{\mathit{a}}_{\mathit{t}+1}\mathrm{)}-{\hat{\mathit{Q}}}_{\mathit{\pi }}\mathrm{(}{\mathit{s}}_{\mathit{t}}\mathrm{,}{\mathit{a}}_{\mathit{t}}\mathrm{)}].\end{array}$$

This update rule is applied after every transition from ${\mathit{s}}_{\mathit{t}}$ to ${\mathit{s}}_{\mathit{t}+1}$ . In case ${\mathit{s}}_{\mathit{t}+1}$ is a terminal state, a value of zero is assigned. By doing this we are ensuring that the estimate $\widehat{{\mathit{Q}}_{\mathit{\pi }}}$ for a behaviour policy π while resulting in changes in π given ${\mathit{Q}}_{\mathit{\pi }}$ . Sarsa will converge to an optimal action-value function ${\mathit{Q}}_{{\mathit{\pi }}^{\ast }}$ and hence an optimal policy ${\mathit{\pi }}^{\ast }$ in the limit given that all possible state-action pairs are visited an infinite amount of time [188]. Consequently, Sarsa converges to the greedy policy in the limit. Algorithm 1 shows Sarsa in more detail.

Algorithm 1:

Sarsa – An on-policy temporal-difference RL algorithm

3.2.2. Q-learning: Off-policy temporal-difference RL

Q-learning was one of the breakthroughs in the field of RL [188,219]. Q-learning is classified as an off-policy temporal-difference algorithm for control. Similar to Sarsa, Q-learning approximates the optimal action-value function ${\mathit{Q}}_{{\mathit{\pi }}^{\ast }}$ by learning $\stackrel{ˆ}{{\mathit{Q}}_{{\mathit{\pi }}^{\ast }}}$ . Differently from Sarsa, Q-learning learns $\stackrel{ˆ}{{\mathit{Q}}_{{\mathit{\pi }}^{\ast }}}$ independently of the policy being followed. The policy being followed still has an effect on the learning process, but only by determining which state-action pairs are visited and consequently updated. Algorithm 2 shows Q-learning in more detail. The update rule for Q-learning is defined as follows: $$\begin{array}{}\text{(15)}& {\hat{\mathit{Q}}}_{\mathit{\pi }}\mathrm{(}{\mathit{s}}_{\mathit{t}}\mathrm{,}{\mathit{a}}_{\mathit{t}}\mathrm{)}={\hat{\mathit{Q}}}_{\mathit{\pi }}\mathrm{(}{\mathit{s}}_{\mathit{t}}\mathrm{,}{\mathit{a}}_{\mathit{t}}\mathrm{)}+\mathit{\alpha }[{\mathit{r}}_{\mathit{t}+1}+\mathit{\gamma }\underset{\mathit{a}}{max}{\hat{\mathit{Q}}}_{\mathit{\pi }}\mathrm{(}{\mathit{s}}_{\mathit{t}+1}\mathrm{,}\mathit{a}\mathrm{)}-{\hat{\mathit{Q}}}_{\mathit{\pi }}\mathrm{(}{\mathit{s}}_{\mathit{t}}\mathrm{,}{\mathit{a}}_{\mathit{t}}\mathrm{)}].\end{array}$$

Algorithm 2:

Q-Learning – An off-policy temporal-difference RL algorithm

3.2.3. Value-function approximation

In Sections 3.2.2 and 3.2.1 we discussed tabular algorithms for value-based RL. In this section we discuss function approximation in RL for estimating state-value functions from a known policy π (i.e. on-policy RL). The difference with the tabular approach is that we represent ${\mathit{v}}_{\mathit{\pi }}$ as a parameterized function with a weight vector $\mathit{w}\in {\mathbb{R}}^{\mathit{d}}$ where $\hat{\mathit{v}}\mathrm{(}\mathit{s}\mathrm{,}\mathit{w}\mathrm{)}\approx {\mathit{v}}_{\mathit{\pi }}\mathrm{(}\mathit{s}\mathrm{)}$ is the approximated value of state s given the learned weights w. Different function approximators can be used to estimate $\hat{\mathit{v}}$ . For instance, $\hat{\mathit{v}}$ can be a deep neural network with w representing the weights of the network. In the tabular version of value-based RL, states and their estimated values are isolated from each other while in function approximation adjusting one weight in the network can lead to changes in the estimated values of many states. This form of learning is powerful due its ability to generalize across different states, but at the same time may lead to more complex models that are harder to understand and to tune. An example of value-function approximation is the deep Q-network (DQN) algorithm [133]. This algorithm combines deep (convolutional) neural network and Q-learning. Using DQN, it was shown that RL agents can achieve state-of-the-art performances on many problems without relying on engineered features. DNQ learns directly from raw (pixel) data instead. The following update rule is an alteration of the Q-learning (semi-gradient of Q-learning [188]) update rule for estimating the weights of the network: $$\begin{array}{}\text{(16)}& {\mathit{w}}_{\mathit{t}+1}={\mathit{w}}_{\mathit{t}}+\mathit{\alpha }[{\mathit{r}}_{\mathit{t}+1}+\mathit{\gamma }·\underset{\mathit{a}}{max}{\hat{\mathit{Q}}}_{\mathit{\pi }}\mathrm{(}{\mathit{s}}_{\mathit{t}+1}\mathrm{,}\mathit{a}\mathrm{,}{\mathit{w}}_{\mathit{t}}\mathrm{)}-{\hat{\mathit{Q}}}_{\mathit{\pi }}\mathrm{(}{\mathit{s}}_{\mathit{t}}\mathrm{,}{\mathit{a}}_{\mathit{t}}\mathrm{,}{\mathit{w}}_{\mathit{t}}\mathrm{)}]{\nabla }_{\mathit{w}\mathit{t}}{\hat{\mathit{Q}}}_{\mathit{\pi }}\mathrm{(}{\mathit{s}}_{\mathit{t}}\mathrm{,}{\mathit{a}}_{\mathit{t}}\mathrm{,}{\mathit{w}}_{\mathit{t}}\mathrm{)}.\end{array}$$

3.3. Policy-gradient RL

In value-based RL values of actions are approximated and then a policy is derived by selecting actions using a certain selection strategy. In policy-gradient RL we learn a parameterized policy directly [188,189]. Consequently, we can select actions without the need for an explicit value function. Let $\mathrm{\Theta }\in {\mathbb{R}}^{\mathit{d}}$ where d is the dimension of the parameter vector Θ. For policy-based methods that also rely on a value function, we denote the function’s weight vector denoted by $\mathit{w}\in {\mathbb{R}}^{{\mathit{d}}^{\prime }}$ as $\hat{\mathit{v}}\mathrm{(}\mathit{s}\mathrm{,}\mathit{w}\mathrm{)}$ . Define the probability of selecting action a at time step t given state s with policy parameters Θ as: $$\begin{array}{}\text{(17)}& \mathit{\pi }\mathrm{(}\mathit{a}|\mathit{s}\mathrm{,}\mathrm{\Theta }\mathrm{)}=\mathit{P}[{\mathit{a}}_{\mathit{t}}=\mathit{a}|{\mathit{s}}_{\mathit{t}}=\mathit{s}\mathrm{,}{\mathrm{\Theta }}_{\mathit{t}}=\mathrm{\Theta }].\end{array}$$

Consider a function $\mathit{J}\mathrm{(}\mathrm{\Theta }\mathrm{)}$ that quantifies the performance of the policy π with respect to parameter vector Θ. The goal is to optimize Θ such that $\mathit{J}\mathrm{(}\mathrm{\Theta }\mathrm{)}$ is maximized. We use the following update rule to approximate gradient ascent in J where the term $\widehat{\nabla \mathit{J}\mathrm{(}{\mathrm{\Theta }}_{\mathit{t}}\mathrm{)}}\in {\mathbb{R}}^{\mathit{d}}$ approximates the gradient of $\mathit{J}\mathrm{(}\mathrm{\Theta }\mathrm{)}$ at t: $$\begin{array}{}\text{(18)}& {\mathrm{\Theta }}_{\mathit{t}+1}={\mathrm{\Theta }}_{\mathit{t}}+\mathit{\alpha }\widehat{\nabla \mathit{J}\mathrm{(}{\mathrm{\Theta }}_{\mathit{t}}\mathrm{)}}.\end{array}$$

Algorithm 3:

One-step episodic actor-critic

3.4. Actor-critic

In actor-critic methods [98,188] both the value and policy functions are approximated. The actor in actor-critic is the learned policy while the critic approximates the value function. Algorithm 3 shows the one-step episodic actor-critic algorithm in more detail. The update rule for the parameter vector Θ is defined as follows: $$\begin{array}{}\text{(19)}& {\mathrm{\Theta }}_{\mathit{t}+1}={\mathrm{\Theta }}_{\mathit{t}}+\mathit{\alpha }{\mathit{\delta }}_{\mathit{t}}{\displaystyle \frac{\nabla \mathit{\pi }\mathrm{(}\mathit{a}|{\mathit{s}}_{\mathit{t}}\mathrm{,}{\mathrm{\Theta }}_{\mathit{t}}\mathrm{)}}{\mathit{\pi }\mathrm{(}\mathit{a}|{\mathit{s}}_{\mathit{t}}\mathrm{,}{\mathrm{\Theta }}_{\mathit{t}}\mathrm{)}}}\mathrm{,}\end{array}$$ where ${\mathit{\delta }}_{\mathit{t}}$ is defined as follows: $$\begin{array}{}\text{(20)}& {\mathit{\delta }}_{\mathit{t}}={\mathit{r}}_{\mathit{t}+1}+\mathit{\gamma }\hat{\mathit{v}}\mathrm{(}{\mathit{s}}_{\mathit{t}+1}\mathrm{,}\mathit{w}\mathrm{)}-\hat{\mathit{v}}\mathrm{(}{\mathit{s}}_{\mathit{t}}\mathrm{,}\mathit{w}\mathrm{)}.\end{array}$$

4. A classification of personalization settings

Personalization has many different definitions [30,55,165]. We adopt the definition proposed in [55] as it is based on 21 existing definitions found in literature and suits a variety of application domains: “personalization is a process that changes the functionality, interface, information access and content, or distinctiveness of a system to increase its personal relevance to an individual or a category of individuals”. This definition identifies personalization as a process and mentions an existing system subject to that process. We include aspects of both the desired process of change and existing system in our framework. Section 5.4 further details how this framework was used in a SLR.

Table 1 provides an overview of the framework. On a high level, we distinguish three categories. The first category contains aspects of suitability of system behavior. We differentiate settings in which suitability of system behavior is determined explicitly by users and settings in which it is inferred by the system after observing user behavior [172]. For example, a user can explicitly rate suitability of a video recommendation; a system can also infer suitability by observing whether the user decides to watch the video. Whether implicit or explicit feedback is preferable depends on availability and quality of feedback signals [89,143,172]. Besides suitability, we consider safety of system behavior. Unaltered RL algorithms use trial-and-error style exploration to optimize their behavior yet this may not suit a particular domain [78,92,136,153]. For example, tailoring the insulin delivery policy of an artificial pancreas to the metabolism of an individual requires trial insulin delivery action but these should only be sampled when their outcome is within safe certainty bounds [44]. If safety is a significant concern in the systems’ application domain, specifically designed safety-aware RL techniques may be required, see [149] and [64] for overviews of such techniques.

Table 1

Framework to categorize personalization setting by

Category	A#	Aspect	Description	Range
Suitability outcome	A1	Control	The extent to which the user defines the suitability of behavior explicitly.	Explicit – implicit
	A2	Safety	The extent to which safety is of importance.	Trivial – critical
Upfront knowledge	A3	User models	The a priori availability of models that describe user responses to system behavior.	Unavailable – unlimited
	A4	Data availability	The a priori availability of human responses to system behavior.	Unavailable – unlimited
New Experiences	A5	Interaction availability	The availability of new samples of interactions with individuals.	Unavailable – unlimited
	A6	Privacy sensitivity	The degree to which privacy is a concern.	Trivial – critical
	A7	State observability	The degree to which all information to base personalization can be measured.	Partial – full

Aspects in the second category deal with the availability of upfront knowledge. Firstly, knowledge of how users respond to system actions may be captured in user models. Such models open up a range of RL solutions that require less or no sampling of new interactions with users [81]. As an example, user pain models are used to predict suitability of exercises in an adaptive physical rehabilitation curriculum manager a priori [208]. Models can also be used to interact with the RL agent in simulation. For example, dialogue agent modules may be trained by interacting with a simulated chatbot user [47,95,105]. Secondly, upfront knowledge may be available in the form of data on human responses to system behavior. This data can be used to derive user models and can be used to optimize policies directly and provide high-confidence evaluations of such policies [111,202–204].

The third category details new experiences. Empirical RL approaches have proven capable of modelling extremely complex dynamics, however, this typically requires complex estimators that in turn need substantial amounts of training data. The availability of users to interact with is therefore a major consideration when designing an RL solution. A second aspect that relates to the use of new experiences is privacy sensitivity of the setting. Privacy sensitivity is of importance as it may restrict sharing, pooling or any other specific usage of data [9,76]. Finally, we identify the state observability as a relevant aspect. In some settings, the true environment state cannot be observed directly but must be estimated using available observations. This may be common as personalization exploits differences in mental [22,96,217] and physical state [67,125]. For example, recommending appropriate music during running involves matching songs to the user emotional state and e.g. running pace. Both mental and physical state may be hard to measure accurately [2,17,152].

Although aspects in Table 1 are presented separately, we explicitly note that they are not mutually independent. Settings where privacy is a major concern, for example, are expected to typically have less existing and new interactions available. Similarly, safety requirements will impact new interaction availability. Presence of upfront knowledge is mostly of interest in settings where control lies with the system as it may ease the control task. In contrast, user models may be marginally important if desired behavior is specified by the user in full. Finally, a lack of upfront knowledge and partial observability complicates adhering to safety requirements.

5. A systematic literature review

A SLR is ‘a form of secondary study that uses a well-defined methodology to identify, analyze and interpret all available evidence related to a specific research question in a way that is unbiased and (to a degree) repeatable’ [23]. PRISMA is a standard for reporting on SLRs and details eligibility criteria, article collection, screening process, data extraction and data synthesis [135]. This section contains a report on this SLR according to the PRISMA statement. This SLR was a collaborative work to which all authors contributed. We denote authors by abbreviation of their names, e.g. FDH, EG, AEH and MH.

5.1. Inclusion criteria

Studies in this SLR were included on the basis of three eligibility criteria. To be included, articles had to be published in a peer-reviewed journal or conference proceedings in English. Secondly, the study had to address a problem fitting to our definition of personalization as described in Section 4. Finally, the study had to use a RL algorithm to address such a personalization problem. Here, we view contextual bandit algorithms as a subset of RL algorithms and thus included them in our analysis. Additionally, we excluded studies in which a RL algorithm was used for purposes other than personalization.

5.2. Search strategy

Fig. 3.

Overview of the SLR process.

Figure 3 contains an overview of the SLR process. The first step is to run a query on a set of databases. For this SLR, a query was run on Scopus, IEEE Xplore, ACM’s full-text collection, DBLP and Google Scholar on June 6, 2018. These databases were selected as their combined index spans a wide range, and their combined result set was sufficiently large for this study. Scopus and IEEE Xplore support queries on title, keywords and abstract. ACM’s full-text collection, DBLP and Google scholar do not support queries on keywords and abstract content. We therefore ran two kinds of queries: we queried on title only for ACM’s full-text collection, DBLP and Google Scholar and we extended this query to keywords and abstract content for Scopus and IEEE Xplore. The query was constructed by combining techniques of interest and keywords for the personalization problem. For techniques of interest the terms ‘reinforcement learning’ and ‘contextual bandits’ were used. For the personalization problem, variations on the words ‘personalized’, ‘customized’, ‘individualized’ and ‘tailored’ were included in British and American spelling. All queries are listed in Appendix A. Query results were de-duplicated and stored in a spreadsheet.

5.3. Screening process

In the screening process, all query results are tested against the inclusion criteria from Section 5.1 in two phases. We used all criteria in both phases. In the first phase, we assessed eligibility based on keywords, abstract and title whereas we used full text of the article in the second phase. In the first phase, a spreadsheet with de-duplicated results was shared with all authors via Google Drive. Studies were assigned randomly to authors who scored each study by the eligibility criteria. The results of this screening were verified by one of the other authors, assigned randomly. Disagreements were settled in meetings involving those in disagreement and FDH if necessary. In addition to eligibility results, author preferences for full-text screening were recorded on a three-point scale. Studies that were not considered eligible were not taken into account beyond this point, all other studies were included in the second phase.

In the second phase, data on eligible studies was copied to a new spreadsheet. This sheet was again shared via Google Drive. Full texts were retrieved and evenly divided amongst authors according to preference. For each study, the assigned author then assessed eligibility based on full text and extracted the data items detailed below.

5.4. Data items

Data on setting, solution and methodology were collected. Table 2 contains all data items for this SLR. For data on setting, we operationalized our framework from Table 1 in Section 4. To assess trends in solution, algorithms used, number of MDP models (see Section 2) and training regime were recorded. Specifically, we noted whether training was performed by interacting with actual users (‘live’), using existing data and a simulator of user behavior. For the algorithms, we recorded the name as used by the authors. To gauge maturity of the proposed solutions and the field as a whole, data on the evaluation strategy and baselines used were extracted. Again, we listed whether evaluation included ‘live’ interaction with users, existing interactions between systems and users or using a simulator. Finally, publication year and application domain were registered to enable identification of trends over time and across domains. The list of domains was composed as follows: during phase one of the screening process, all authors recorded a domain for each included paper, yielding a highly inconsistent initial set of domains. This set was simplified into a more consistent set of domains which was used during full-text screening. For papers that did not fall into this consistent set of domains, two categories were added: a ‘Domain Independent’ and an ‘Other’ category. The actual domain was recorded for the five papers in the ‘Other’ category. These domains were not further consolidated as all five papers were assigned to unique domains not encountered before.

Table 2

Data items in SLR. The last column relates data items to aspects of setting from Table 1 where applicable

Category	#	Data item	Values	A#
Setting	1	User defines suitability of system behavior explicitly	Yes, No	A1
	2	Suitability of system behavior is derived	Yes, No	A1
	3	Safety is mentioned as a concern in the article	Yes, No	A2
	4	Privacy is mentioned as a concern in the article	Yes, No	A6
	5	Models of user responses to system behavior are available	Yes, No	A3
	6	Data on user responses to system behavior are available	Yes. No	A4
	7	New interactions with users can be sampled with ease	Yes, No	A5
	8	All information to base personalization on can be measured	Yes, No	A7
Solution	9	Algorithms	N/A	–
	10	Number of learners	1, 1/user, 1/group, multiple	–
	11	Usage of traits of the user	state, other, not used	–
	12	Training mode	online, batch, other, unknown	–
	13	Training in simulation	Yes, No	A3
	14	Training on a real-life dataset	Yes, No	A4
	15	Training in ‘live’ setting	Yes, No	A5
Evaluation	16	Evaluation in simulation	Yes, No	A3
	17	Evaluation on a real-life dataset	Yes, No	A4
	18	Evaluation in ‘live’ setting	Yes, No	A5
	19	Comparison with ‘no personalization’	Yes, No	–
	20	Comparison with non-RL methods	Yes, No	–

5.5. Synthesis and analysis

To facilitate analysis, reported algorithms were normalized using simple text normalization and key-collision methods. The resulting mappings are available in the dataset release [46]. Data was summarized using descriptive statistics and figures with an accompanying narrative to gain insight into trends with respect to settings, solutions and evaluation over time and across domains.

6. Results

The quantitative synthesis and analyses introduced in Section 5.5 were applied to the collected data. In this section, we present insights obtained. We focus on the major insights and encourage the reader to explore the tabular view in Appendix B or the collected data for further analysis [46].

Before diving into the details of the study in light of the classification scheme we have proposed, let us first study some general trends. Figure 4 shows the number of publications addressing personalization using RL techniques over time. A clear increase can be seen. With over forty entries, the health domain contains by far the most articles, followed by entertainment, education and commerce with all approximately just over twenty five entries. Other domains contain less than twelve papers in total. Figure 5(a) shows the popularity of domains for the five most recent years and seems to indicate that the number of articles in the health domain is steadily growing, in contrast with the other domains. Of course, these graphs are based on a limited number of publications, so drawing strong conclusions from these results is difficult. We do need to take into account that the popularity of RL for personalization is increasing in general. Therefore Fig. 5(b) shows the relative distribution of studies over domains for the five most recent years. Now we see that the health domain is just following the overall trend, and is not becoming more popular within studies that use RL for personalization. We fail to identify clear trends for other domains from these figures.

Fig. 4.

Distribution of included papers over time and over domains. Note that only studies published prior to the query date of June 6, 2018 were included.

Fig. 5.

Popularity of domains for the five most recent years.

6.1. Setting

Table 3 provides an overview of the data related to setting in which the studies were conducted. The table shows that user responses to system behavior are present in a minority of cases (66/166). Additionally, models of user behavior are only used in around one quarter of all publications. The suitability of system behavior is much more frequently derived from data (130/166) rather than explicitly collected by users (39/166). Privacy is clearly not within the scope of most articles, only in 9 out of 166 cases do we see this issue explicitly mentioned. Safety concerns, however, are mentioned in a reasonable proportion of studies (30/166). Interactions can generally be sampled with ease and the resulting information is frequently sufficient to base personalization of the system at hand on.

Table 3

Number of publications by aspects of setting

Aspect	#
User defines suitability of system behavior explicitly	39
Suitability of system behavior is derived	130
Safety is mentioned as a concern in the article	30
Privacy is mentioned as a concern in the article	9
Models of user responses to system behavior are available	41
Data on user responses to system behavior are available	66
New interactions with users can be sampled with ease	97
All information to base personalization on can be measured	132

Let us dive into some aspects in a bit more detail. A first trend we anticipate is an increase of the fraction of studies working with real data on human responses over the years, considering the digitization trend and associated data collection. Figure 6(a) shows the fraction of papers for which data on user responses to system behavior is available over time. Surprisingly, we see that this fraction does not show any clear trend over time. Another aspect of interest relates to safety issues in particular domains. We hypothesize that in certain domains, such as health, safety is more frequently mentioned as a concern. Figure 6(b) shows the fraction of papers of the different domains in which safety is mentioned. Indeed, we clearly see that certain domains mention safety much more frequently than other domains. Third, we explore the ease with which interactions with users can be sampled. Again, we expect to see substantial differences between domains. Figure 7 confirms our intuition. Interactions can be sampled with ease more frequently in studies in the commerce, entertainment, energy, and smart homes domains when compared to communication and health domains.

Fig. 6.

Availability of user responses over time (a), and mentions of safety as a concern over domains (b).

Finally, we investigate whether upfront knowledge is available. In our analysis, we explore both real data as well user models being available upfront. One would expect papers to have at least one of these two prior to starting experiments. User models and not real data were reported in 41 studies, while 53 articles used real data but no user model and 12 use both. We see that for 71 studies neither is available. In roughly half of these, simulators were used for both training (38/71) and evaluation (37/71). In a minority, training (15/71) and evaluation (17/71) were performed in a live setting, e.g. while collecting data.

6.2. Solution

In our investigation into solutions, we first explore the algorithms that were used. Figure 8 shows the distribution of usage frequency. A vast majority of the algorithms are used only once, some techniques are used a couple of times and one algorithm is used 60 times. Note again that we use the name of the algorithms used by the authors as a basis for this analysis. Table 4 lists the algorithms that were used more than once. A significant number of studies (60/166) use the Q-learning algorithm. At the same time, a substantial number of articles (18/166) reports the use of RL as the underlying algorithmic framework without specifying an actual algorithm. The contextual bandits, Sarsa, actor-critic and inverse RL (IRL) algorithms are used in respectively (18/166), (12/166), (8/166), (8/166) and (7/166) papers. We also observe some additional algorithms from the contextual bandits family, such as UCB and LinUCB. Furthermore, we find various mentions that indicate the usage of deep neural networks: deep reinforcement learning, DQN and DDQN. In general, we find that some publications refer to a specific algorithm whereas others only report generic techniques or families thereof.

Fig. 7.

New interactions with users can be sampled with ease.

Fig. 8.

Distribution of algorithm usage frequencies.

Table 4

Algorithm usage for all algorithms that were used in more than one publication

Algorithm	# of uses
Q-learning [219]	60
RL, not further specified	18
Contextual bandits	12
Sarsa [187]	8
Actor-critic	8
Inverse reinforcement learning	7
UCB [7]	5
Policy iteration	5
LinUCB [37]	5
Deep reinforcement learning	4
Fitted Q-iteration [166]	3
DQN [133]	3
Interactive reinforcement learning	2
TD-learning	2
DYNA-Q [186]	2
Policy gradient	2
CLUB [69]	2
Monte Carlo	2
Thompson sampling	2
DDQN [212]	2

Fig. 9.

Occurence of different solution architectures (a) and usage of simulators in training (b). For (a), publications that compare architectures are represented in the ‘multiple’ category.

Figure 9(a) lists the number of models used in the included publications. The majority of solutions relies on a single-model architecture. On the other end of the spectrum lies the architecture of using one model per person. This architecture comes second in usage frequency. The architecture that uses one model per group can be considered a middle ground between these former two. In this architecture, only experiences with relevant individuals can be shared. Comparisons between architectures are rare. We continue by investigating whether and where traits of the individual were used in relation to these architectures. Table 5 provides an overview. Out of all papers that use one model, 52.7% did not use the traits of the individuals and 41.7 % included traits in the state space. 47.5% of the papers include the traits of the individuals in the state representation while in 37.3% of the papers the traits were not included. In 15.3% of the cases this was not known.

Figure 9(b) shows the popularity of using a simulator for training per domain. We see that a substantial percentage of publications use a simulator and that simulators are used in all domains. Simulators are used in the majority of publications for the energy, transport, communication and entertainment domains. In publications in the first three out of these domains, we typically find applications that require large-scale implementation and have a big impact on infrastructure, e.g. control of the entire energy grid or a fleet of taxis in a large city. This complicates the collection of useful realistic dataset and training in a live setting. This is not the case for the entertainment domain with 17 works using a simulator for training. Further investigation shows that nine out of these 17 also include training on real data or in a ‘live’ setting. It seems that training on a simulator is part of the validation of the algorithm rather than the prime contribution of the paper in the entertainment domain.

6.3. Evaluation

In investigating evaluation rigor, we first turn to the data on which evaluations are based. Figure 10 shows how many studies include an evaluation in a ‘live’ setting or using existing interactions with users. In the years up to 2007 few studies were done and most of these included realistic evaluations. In more recent years, the absolute number of studies shows a marked upward trend to which the relative number of articles that include a realistic evaluation fails to keep pace. Figure 10 also shows the number of realistic evaluations per domain. Disregarding the smart home domain, as it contains only four studies, the highest ratio of real evaluations can be found in the commerce and entertainment domains, followed by the health domain.

Table 5

Number of models and the inclusion of user traits

Traits of users were used	Number of models
	1	1/group	1/person	Multiple
In state representation	38	8	28	2
Other	5	0	9	3
Not used	48	3	22	0
Total	91	11	59	5

Fig. 10.

Number of papers with a ‘live’ evaluation or evaluation using data on user responses to system behavior.

We look at possible reasons for a lack of realistic evaluation using our categorization of settings from Section 4. Indeed, there are 63 studies with no realistic evaluation versus 104 with a realistic evaluation. Because these group sizes differ, we include ratios with respect to these totals in Table 6. The biggest difference between ratios of studies with and without a realistic evaluation is in the upfront availability of data on interactions with users. This is not surprising, as it is natural to use existing interactions for evaluation when they are available already. The second biggest difference between the groups is whether safety is mentioned as a concern. Relatively, studies that refrain from a realistic evaluation mention safety concerns almost twice as often as studies that do a realistic evaluation. The third biggest difference can be found in availability of user models. If a model is available, user responses can be simulated more easily. Privacy concerns are not mentioned frequently, so little can be said on its contribution to a lacking realistic evaluation. Finally and surprisingly, the ease of sampling interactions is comparable between studies with a realistic and without realistic evaluation.

Table 6

Comparison of settings with realistic and other evaluation

	Real-world evaluation		Other evaluation
	Count	% of column total	Count	% of column total
Total	104	100.0%	63	100.0%
Data on user responses to system behavior are available	57	54.8%	9	14.5%
Safety is mentioned as a concern in the article	14	13.5%	16	25.8%
Models of user responses to system behavior are available	21	20.2%	20	32.3%
Privacy is mentioned as a concern in the article	7	6.7%	2	3.2%
New interactions with users can be sampled with ease	60	57.7%	37	59.7%

Figure 11 describes how many studies include any of the comparisons in scope in this survey, that is: comparisons between solutions with and without personalization, comparisons between RL approaches and other approaches to personalization and comparisons between different RL algorithms. In the first years, no papers includes such a comparison. The period 2000-2010 contains relatively little studies in general and the absolute and relative numbers of studies with a comparison vary. From 2011 to 2018, the absolute number maintains it upward trend. The relative number follows this trend but flattens after 2016.

Fig. 11.

Number of papers that include any comparison between solutions over time.

7. Discussion

The goal of this study was to give an overview and categorization of RL applications for personalization in different application domains which we addressed using a SLR on settings, solution architectures and evaluation strategies. The main result is the marked increase in studies that use RL for personalization problems over time. Additionally, techniques are increasingly evaluated on real-life data. RL has proven a suitable paradigm for adaptation of systems to individual preferences using data.

Results further indicate that this development is driven by various techniques, which we list in no particular order. Firstly, techniques have been developed to estimate the performance of deploying a particular RL model prior to deployment. This helps in communicating risks and benefits of RL solutions with stakeholders and moves RL further into the realm of feasible technologies for high-impact application domains [200]. For single-step decision making problems, contextual bandit algorithms with theoretical bounds on decision-theoretic regret have become available. For multi-step decision making problems, methods that can estimate the performance of some policy based on data generated by another policy have been developed [37,90,204]. Secondly, advances in the field of deep learning have wholly or partly removed the need for feature engineering [53]. This may be especially challenging for sequential decision-making problems as different features may be of importance in different states encountered over time. Finally, research on safe exploration in RL has developed means to avoid harmful actions during exploratory phases of learning [64]. How any these techniques are best applied depends on setting. The collected data can be used to find suitable related work for any particular setting [46].

Since the field of RL for personalization is growing in size, we investigated whether methodological maturity is keeping pace. Results show that the growth in the number of studies with a real-life evaluation is not mirrored by growth of the ratio of studies with such an evaluation. Similarly, results show no increase in the relative number of studies with a comparison of approaches over time. These may be signs that the maturity of the field fails to keep pace with its growth. This is worrisome, since the advantages of RL over other approaches or between RL algorithms cannot be understood properly without such comparisons. Such comparisons benefit from standardized tasks. Developing standardized personalization datasets and simulation environments is an excellent opportunity for future research [87,112].

We found that algorithms presented in literature are reused infrequently. Although this phenomenon may be driven by various different underlying dynamics that cannot be untangled using our data, we propose some possible explanations here without particular order. Firstly, it might be the case that separate applications require tailored algorithms to the extend that these can only be used once. This raises the question on the scientific contribution of such a tailored algorithm and does not fit with the reuse of some well-established algorithms. Another explanation is that top-ranked venues prefer contributions that are theoretical or technical in nature, resulting in minor variations to well-known algorithms being presented as novel. Whether this is the case is out of scope for this research and forms an excellent avenue for future work. A final explanation for us to propose, is the myriad axes along which any RL algorithm can be identified, such as whether and where estimation is involved, which estimation technique is used and how domain knowledge is encoded in the algorithm. This may yield a large number of unique algorithms, constructed out of a relatively small set of core ideas in RL. An overview of these core ideas would be useful in understanding how individual algorithms relate to each other.

On top of algorithm reuse, we analyzed which RL algorithms were used most frequently. Generic and well-established (families of) algorithms such as Q-learning are the most popular. A notable entry in the top six most-used techniques is inverse reinforcement learning (IRL). Its frequent usage is surprising, as the only viable application area of IRL under a decade ago was robotics [97]. Personalization may be one of the other useful application areas of this branch of RL and many existing personalization challenges may still benefit from an IRL approach. Finally, we investigated how many RL models were included in the proposed solutions and found that the majority of studies resorts to using either one RL model in total or one RL model per user. Inspired by common practice of clustering in the related fields such as e.g. recommender systems, we believe that there exists opportunities in pooling data of similar users and training RL models on the pooled data.

Besides these findings, we contribute a categorization of personalization settings in RL. This framework can be used to find related work based on the setting of a problem at hand. In designing such a framework, one has to balance specificity and usefulness of aspects in the framework. We take the aspect of ‘safety’ as an example: any application of RL will imply safety concerns at some level, but they are more prominent in some application areas. The framework intentionally includes a single ambiguous aspect to describe a broad range ‘safety sensitivity levels’ in order for it to suit its purpose of navigating literature. A possibility for future work is to extend the framework with other, more formal, aspects of problem setting such as those identified in [170].