{'fraction_non_alphanumeric': 0.03684868695289704, 'fraction_numerical': 0.011713213839099625, 'mean_word_length': 4.813181487763509, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On the Unreasonable Efficiency of State Space Clustering in Personalization Tasks

In this effort we consider a reinforcement learning (RL) technique for solving personalization tasks with complex reward signals. In particular, our approach is based on state space clustering with the use of a simplistic $k$-means algorithm as well as conventional choices of the network architectures and optimization algorithms. Numerical examples demonstrate the efficiency of different RL procedures and are used to illustrate that this technique accelerates the agent's ability to learn and does not restrict the agent's performance.


I. INTRODUCTION
Conventional personalization focuses on personal, transactional, demographic, and possibly health-related information, such as an individual's name, age, residential location, employment, purchases, medical history, etc. The most basic example of this task involves the inclusion of the customer's name in the subject line and/or the content of an email. This technique relies on generalization and profiling to make specific assumptions about the individual based on their characteristics. Additional applications of personalization include: web content personalization and layout customization [8], [30]; customercentric interaction with their healthcare providers [19], [38]; personalized medical treatments [3], [10]; and music, video, and movie recommender systems [40].
Hyper-personalization, on the other hand, is a more complex and transformative approach that considers behavioral and realtime data produced as the result of user action. Examples of this technique include online browsing behavior, communication history, in-application choices, and other engagement data, which is used to interpret the user's intent. This allows for more personalized experiences in the form of, for instance, adding individualized engaging sections to the body of an email or push notifications at the time when the customer is typically active, which result in more customized communication and thus, ultimately, greater conversion.
Reinforcement learning (RL) approaches have been increasingly applied to personalization tasks [6], [12], [42]- [44], [46], [47]. The combination with clustering techniques has also been studied in the works [20], [28], [45]. Implementation of the clustering methods typically simplifies the problem and allows an RL agent to be trained with fewer data points, which is essential in real-world applications. Nonetheless, utilizing any form of clustering unavoidably leads to a loss of information about the environment, which might prevent an agent from solving the task completely. This trade-off between the environment's complexity and representation gives rise to the immediate question of which RL algorithms and clustering methods lead to a satisfactory performance.
In this paper we explore the unexpected efficiency of a naive approach to state space clustering on complex personalization tasks. For a clearer demonstration of this phenomenon, we consider the most simplistic k-means approach (see e.g. [5], [13] and the references therein) for clustering that does not account for the reward distribution and is based solely on the state representation as a vector in the state space. Our main contributions are: • definition and formalization of the synthetic personalization setting; • development of the framework for constructing a wide range of synthetic personalization environments; and • empirical comparison between the clustering-based and full RL-approaches for solving the personalization tasks.

II. BACKGROUND
In the current work we address a personalization task with a reinforcement learning approach. Specifically, we view the personalization task as a contextual bandit problem, introduced in [18]. For convenience of presentation we use the notational standard MDPNv1 [37]. Namely, S denotes the state (context) space, A denotes the action space, R ⊂ R denotes the reward space, and r : S × A → R denotes the reward function. We assume that the reward space R is bounded and that the reward function r is deterministic.
Though reinforcement learning has been found to be highly successful in games, control, and personalization applications (see e.g. [4], [39]), it suffers from several limitations. In particular, many RL algorithms require samples that are polynomial in the size of the state space [33]. Although the polynomial sample complexity may not be a challenge anymore with advances in computing capabilities, the size of a state space has been a problem for an MDP, as it grows superpolynomially with the number of dimensions (or attributes) [1]. This curse of dimensionality has been addressed in the literature through state space abstraction.
In [11], abstraction is defined as a mapping from one problem representation to a new representation, while preserving some properties of the original representation. Thus, learning a state abstraction involves finding a mapping from the original state space S to another more compact spaceS. Abstraction has been widely studied in the literature to both overcome the curse of dimensionality as well as to exploit the computational advantages it offers for RL algorithms. Abstraction is applicable to both temporal and state space. In this work, we focus mostly on state space abstraction.
Several techniques have been proposed in the literature to find a compact state spaceS, they can be broadly grouped into: (i) feature selection, (ii) unsupervised learning (clustering), and (iii) hierarchical approaches.
Feature selection methods can start from a null set and gradually add relevant state attributes, or start from a complete set of state attributes and gradually remove unnecessary attributes. These methods are computationally expensive and also require huge amounts of data. A more efficient feature selection method is proposed in [17], where the algorithm starts with a fixed number of potential state space abstractions and incrementally selects an abstraction based on an approach similar to model selection using Bayesian Information Criterion (BIC). Several other approaches have been proposed to selectively construct compact and accurate feature spaces [16], [36], [41] in recent years.
On the other hand, clustering based approaches seek to construct a new compact state space that preserves important properties such as topology or the structure of the underlying physical system. When performing clustering, one has to pay attention to the novelty (typically measured in terms of counts, empowerment, agents belief, or prediction error) and quality in the neighboring regions of the current state. This observation is the principle behind the Clustered Reinforcement Learning (CRL) algorithm proposed in [22] to facilitate better exploration by the agent. CRL uses a K-means clustering to divide the collected states into several clusters followed by a novel bonus reward that considers both novelty and quality in the neighboring area, i.e. states which share the same cluster with the current state. Experiments on continuous control tasks and Atari games showed that CRL performed better than the trust region based policy gradient method and locality sensitive hashing based methods [31], [35]. In the recent work [23], the authors argue that speeding up an agent's learning requires generalization of experience across states and propose a Thompson Clustering for Reinforcement Learning (TCRL) framework for reinforcement learning in discrete MDPs with a medium/small state space. TCRL showed better performance on various domains, including the cases where no states are similar.
In recent years, a great deal of hierarchical reinforcement learning (HRL) algorithms (see [2], [7], [9], [14], [15], [24], [29]) were developed to address the challenges posed by huge state spaces and sparse delayed reward feedback. The hierarchical approaches decompose a complex task into a set of sub-tasks (or subgoals) using hierarchical structures. Once useful subgoals are discovered, an HRL agent should be able to learn the skills to attain those subgoals. However, finding a good decomposition and subgoals is still a major challenge. In [2], authors propose an algorithm for automatically building a hierarchy by dividing the state space into clusters and allocating sub-targets by the modified bottleneck method. The states recommended for visiting are called bottlenecks. Some of these challenges were addressed in a model-free HRL [29]. In this model-free HRL framework, subgoals were discovered using unsupervised learning and anomaly detection methods. More detailed approaches can be found in a recent survey paper [27].
A particular instance of state abstraction in the form of sophisticated state space aggregations is considered in [1], [21], where the authors explore the question of learning from such abstractions. In [1], authors investigate several approximate state abstractions and present theoretical guarantees of the quality of behaviors derived from these approximate abstractions. Experimental results show that the approximate abstractions lead to a reduction in task complexity. In [21] the authors study five different abstraction schemes and provide a unified treatment of state abstraction for Markov decision processes. Unlike the clustering considered in this work, these abstractions treat the state space not in isolation but as a part of the environment and in certain cases can be used to learn the optimal policy. On the other hand, our work is focused on building a general purpose simulation and experimentation framework that allows for the empirical comparison of various abstraction strategies using clustering-based methods as well as the exploration of general RL algorithms for solving personalization tasks.

III. SYNTHETIC PERSONALIZATION TASK
We define the synthetic personalization environment as a contextual bandit setting consisting of a continuous state space S ⊂ R d S , a discrete action space A ⊂ R d A ×|A| , and a reward function r : S × A → R such that the value r(s, a) depends on the latent state and action features that are not known to the agent. The observed states are sampled from a distribution T (S) which is also unknown to the agent.
Similarly to a general contextual bandit task, the goal of an agent is to learn a policy π that, for an observed state s ∈ S, selects a relevant action a π ∈ A. The relevance of the selected action a π for the given state s is determined by the value of the reward r(s, a π ) ∈ R. The conventional way of training such an agent is to represent the agent as a neural network parameterized by the vector of weights θ, and to allow the agent π(θ) to interact with the environment and adjust the policy's weights θ based on the received rewards. For a general overview of the problem setting and common approaches, we refer the reader to the book [34].

A. Synthetic Reward Signal
In order to simulate a complex yet realistic personalization task we assume that the reward signal received by the agent is determined by the state and action representations in the latent feature space L. Accordingly, the constructed reward function consists of two latent feature extractors -F S for the state space and F A for the action space -and an intrinsic reward function F L that determines the reward value based on the extracted features. For the purpose of this paper the synthesized latent feature extractors F S , F A consist of randomly generated neural networks of a particular structure described below, and the final reward value is determined by the proximity of the state and action feature vectors in the latent space L, as displayed in Figure 1. Thus the synthetic reward function r : S × A → R consists of the following mappings: • State feature extractor F S : S → L, • Action feature extractor F A : A → L, • Intrinsic reward function F L : L × L → R, and the geometry of the reward function depends on the following parameters: • Dimensionality of the state and action spaces S and A, • Dimensionality of the latent feature space L, • Architecture of the state and action feature extractors, • Structure of the intrinsic reward function. Once the above parameters are specified, we generate a synthetic feature extractor as a feed-forward neural network with the input dimensionality d S := dim(S) (or d A := dim(A)), output dimensionality d L := dim(L), and the selected architecture with the Gaussian activation functions σ(z) = exp(−z 2 ). The network weights are initialized from the standard normal distribution N (0, 1) so that the constructed mapping resembles a fully-trained network between the state space S (or the action space A) and the latent feature space L. We then apply the tanh function to the output of both feature extractors F S and F A before computing the proximity in the latent feature space L. This concludes the construction of the synthetic feature extractors.
Lastly, we need to specify the intrinsic reward function F L : L × L → R that determines the reward value. For simplicity, in this paper we consider the cosine similarity in 2 -norm as a measure of proximity of two feature vectors, i.e. our synthetic reward function r : S × A → R has the form where F S : S → L and F A : A → L are the synthetic state and action feature extractors respectively.

B. Analysis of the Synthetic Reward Signal
In this section we take a closer look at the behavior of the synthetic reward function and demonstrate that, for a given state s ∈ S, the reward values across the action space A are indeed determined by the latent features vector F S (s) ∈ L rather than by the raw coordinates in the state space. Intuitively, this claim is demonstrated in Figure 2, where we set up a synthetic personalization environment, sample states that are close in the state space, and report the corresponding reward values on the action space. We observe that, despite being close in the state space, the reward values for the available actions are distinct, which demonstrates that the simulated reward signal depends on the latent features that an agent has to learn by interacting with the environment. Below we provide the exact details on how the environment and reward signal are set up. Specifically, we generate the synthetic environment with the state space S = [−1, 1] 100 , the action space A = {a 1 , . . . , a 100 } with a j ∼ U([−1, 1] 100 ), and the reward space R = [−1, 1]. The synthetic reward function r : S × A → R is constructed according to (1), where the state and action feature extractors F S and F A are the randomly generated feedforward neural networks with the architecture [100, 100, 100], as described in Section III-A, i.e. F S (s) = tanh(FC100(FC100(FC100(s)))), F A (a) = tanh(FC100(FC100(FC100(a)))), where FC100 denotes a fully-connected layer with 100 nodes and the Gaussian activation function σ(z) = exp(−z 2 ), with the weights sampled from the standard normal distribution N (0, 1). The output of each feature extractor is a vector in the latent feature space L = [− π /2, π /2] 100 , and the value of the reward r(s, a) is the cosine similarity between the feature vectors F S (s) ∈ L and F A (a) ∈ L. Figure 2 is obtained by considering the set of states {s 1 , . . . , s 5 } ∈ S whose coordinates are sampled from the normal distribution N (0, 0.0001) and computing the corresponding reward values on the first ten available actions a 0 , . . . , a 9 ∈ A. We note that, even though the sampled states {s 1 , . . . , s 5 } are close in the state space S, the distribution of the rewards values {r(s 1 , a j ), . . . , r(s 5 , a j )} is not similar for any 0 ≤ j ≤ 9. For a more technical demonstration of the relation between the proximity in the state space and the distribution of the rewards across the action space, we uniformly sample 100, 000 states {s i } 100,000 i=1 from the state space S and then split them into 100 clusters C 1 , . . . , C 100 via the K-means algorithm.
For each cluster C k we compute the vector of reward values r A (s) := {r(s, a 0 ), . . . , r(s, a 99 )} ∈ R 100 for every state s ∈ C k . Then we calculate the Pearson's correlation coefficient between the set of pair-wise differences of the states in the cluster and the corresponding vectors of rewards, i.e.
for each cluster C k , 1 ≤ k ≤ 100. The resulting correlation coefficients are presented in Figure 3. Once again, we observe no correlation between the distance in the state space S and the distance in the reward space R. Given these empirical demonstrations and the overall intuition behind the construction of a synthetic personalization task, one would assume that clustering of the state space with the intent of simplifying the task is a counter-productive effort. However, our extensive numerical results, discussed in the next section, quite unexpectedly show the opposite.

IV. NUMERICAL EXPERIMENTS
In this section we train agents with several commonly-used RL algorithms on the Synthetic Personalization Tasks defined in Section III, and compare their performance. Specifically, we consider the following algorithms: • A2C -Advantage Actor Critic [25]; • DQN -Deep Q Network [26]; • PPO -Proximal Policy Optimization [32]. The presented RL algorithms are implemented through the use of the Stable-Baselines3 1 library with the recommended choice of hyperparameters. Our numerical experiments are performed in Python 3.8 and the source code reproducing the 1 https://stable-baselines3.readthedocs.io/ presented results is publicly available at https://github.com/ sukiboo/hyperpersonalization.
While the conventional way of assessing an agent's performance on a contextual bandit problem is to measure the total regret, it is not the most suitable metric in our setting. First, in real-world personalization applications it is often not feasible to fully learn the environment due to the complexity of the reward signal, regardless of whether it is caused by the nontrivial geometry of the state-action space or by external factors, such as the stochasticity or nonstationarity of the environment. Second, it is important to ensure that the trained policy provides a nontrivial level of performance shortly after being deployed, i.e. with a limited number of agent-environment interactions. What qualifies a nontrivial performance level is typically applicationspecific but the common benchmark in personalization tasks is the expected return of the uniformly random agent. Hence if an agent's return is consistently higher that that of the uniformly random agent, we say that a nontrivial level of performance is achieved, which is a necessary condition for deploying an agent.
To this end, in our numerical experiments the performance of an agent is measured and reported to reflect the above points. Namely, for each instance of the synthetic environment we obtain the uniformly random policy π 0 and the optimal policy π , i.e. such that for any state s ∈ S we have Then the performance of the target policy π on a state s ∈ S is reported as The positive value of R(π|·) indicates that the agent outperforms the uniformly random policy on the given state, and the value of 1 means that the optimal action is selected for the given state.

Experiment Setup
The process of generating the synthetic environment and reward signal allows for a lot of freedom in the selection of various parameters. In order to provide a wide range of experiments, we vary the complexity of different components, listed in Table I, and report the results in Figures 4-15. Specifically, we distinguish three components that contribute to the overall complexity of the Synthetic Personalization Task: the dimensionality of the environment, the geometry of the reward signal, and the architecture of the policy's network.
As for the value of the parameters d S , d A , and |A|, we consider two cases: The synthetic reward signal r : S × A → R is generated according to the process described in Section III-A. The complexity of the reward function is determined by the dimensionality d L of the latent feature space L and the architecture of the state and action feature extractors. For the ease of notation, we employ the same architecture for the state and action branches, denoted as r-architecture. We consider two cases for the geometry of the reward signal: • Simple: d L = 10 and r-architecture is [10, 10, 10]; • Complex: d L = 100 and r-architecture is [100, 100, 100]. Finally, the architecture of the neural network that is used to parameterize the agent's policy is explicitly related to the agent's ability to learn the environment. Hence we specify three choices for the network architecture, denoted as π-architecture: • Large: π-architecture is [128, 128, 128]; • Medium: π-architecture is [64, 64, 64]; • Small: π-architecture is [32,32,32]. Note that some of the algorithms we employ (namely, A2C and PPO) use two networks: one for the actor and one for the critic. In our experiments both networks use the same architecture.
The exact parameter values for each experiment are outlined in Table I. Once the parameters are chosen, a single experiment consists of the following steps: 1) Generate the environment; 2) Synthesize the reward function; 3) Train RL agents on the environment; 4) Cluster the state space via the K-means; 5) Train RL agents on the clustered environment; 6) Report the agents' performance. Each agent is deployed for 100, 000 timesteps for training with the corresponding approach, i.e. each algorithm has access to 100, 000 unique agent-environment interactions, not accounting for samples from the replay buffer. Since the performance of the agent might be sensitive to the initialization of the network's weights, each agent is trained 3 times and the average result is reported. We also note that, despite being completely synthetic, our setting is completely reproducible and each agent is observing exactly the same sequence of states, regardless of the stochasticity in the corresponding RL algorithm. In order to avoid a possible unintentional bias from the synthetically constructed environment, each experiment is repeated 3 times with an independently generated state space, action space, and reward function, and the average of the normalized returns, computed via (2), are reported in Figures 4-15. We note that while the presented experiments only use the parameter values listed in Table I, a more extensive range of experiments on other configurations has provided similar results.

V. CONCLUSION
In this effort we consider personalization tasks and discuss some of the common RL-based approaches and the practical techniques used to decrease the dimensionality of the problem, typically achieved via some form of clustering. In order to empirically evaluate the efficiency of different approaches, we develop a framework for generating synthetic personalization environments with a reward signal of arbitrary complexity, which can be used to simulate a wide range of real-world applications.
We argue that in such complicated environments most of the basic forms of clustering should not work, since naively restricting the dimensionality of the environment representation unavoidably leads to the loss of information. However, seemingly counter-intuitively, we observe that, when the conventional RL algorithms are deployed, even the most trivial form of clustering accelerates learning and does not restrict the performance. We hypothesize that this phenomenon is due to the employment of conventional RL algorithms that by design are not able to capture the complicated mechanisms behind the composition of the reward signals that are common in real-world applications. As a particular observation, our results imply that the information lost during the clustering process is not used by the conventional agents, which calls for the development of more sophisticated approaches, which is the topic of our future work.