# Optimal Recommendation to Users that React: Online Learning for a Class of POMDPs

arXiv: https://arxiv.org/abs/1603.09233 · HTML: https://mlsanity.com/paper/1603.09233/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Mar 2016.

## Built on by (most cited first, 13 of 13)

- [Optimistic Whittle Index Policy: Online Learning for Restless Bandits](https://mlsanity.com/paper/2205.15372/) (2022)
- [Finite-Time Analysis of Whittle Index based Q-Learning for Restless Multi-Armed Bandits with Neural Network Function Approximation](https://mlsanity.com/paper/2310.02147/) (2023)
- [Efficient Resource Allocation with Fairness Constraints in Restless Multi-Armed Bandits](https://mlsanity.com/paper/2206.03883/) (2022)
- [Limited Resource Allocation in a Non-Markovian World: The Case of Maternal and Child Healthcare](https://mlsanity.com/paper/2305.12640/) (2023)
- [Faster Q-Learning Algorithms for Restless Bandits](https://mlsanity.com/paper/2409.05908/) (2024)
- [DOPL: Direct Online Preference Learning for Restless Bandits with Preference Feedback](https://mlsanity.com/paper/2410.05527/) (2024)
- [Whittle Index Learning Algorithms for Restless Bandits with Constant Stepsizes](https://mlsanity.com/paper/2409.04605/) (2024)
- [Modeling Churn in Recommender Systems with Aggregated Preferences](https://mlsanity.com/paper/2502.18483/) (2025)
- [Explicit User Manipulation in Reinforcement Learning Based Recommender Systems](https://mlsanity.com/paper/2203.10629/) (2022)
- [Influencing Bandits: Arm Selection for Preference Shaping](https://mlsanity.com/paper/2403.00036/) (2024)
- [AOTree: Aspect Order Tree-based Model for Explainable Recommendation](https://mlsanity.com/paper/2407.19937/) (2024)
- [Churn-Aware Recommendation Planning under Aggregated Preference Feedback](https://mlsanity.com/paper/2507.04513/) (2025)
- [Meta-Learning Multi-armed Bandits for Beam Tracking in 5G and 6G Networks](https://mlsanity.com/paper/2512.05680/) (2025)

## Abstract (arXiv)

We describe and study a model for an Automated Online Recommendation System (AORS) in which a user's preferences can be time-dependent and can also depend on the history of past recommendations and play-outs. The three key features of the model that makes it more realistic compared to existing models for recommendation systems are (1) user preference is inherently latent, (2) current recommendations can affect future preferences, and (3) it allows for the development of learning algorithms with provable performance guarantees. The problem is cast as an average-cost restless multi-armed bandit for a given user, with an independent partially observable Markov decision process (POMDP) for each item of content. We analyze the POMDP for a single arm, describe its structural properties, and characterize its optimal policy. We then develop a Thompson sampling-based online reinforcement learning algorithm to learn the parameters of the model and optimize utility from the binary responses of the users to continuous recommendations. We then analyze the performance of the learning algorithm and characterize the regret. Illustrative numerical results and directions for extension to the restless hidden Markov multi-armed bandit problem are also presented.