In digital health and EdTech, recommendation systems face a significant
challenge: users often choose impulsively, in ways that conflict with the
platform's long-term payoffs. This misalignment makes it difficult to
effectively learn to rank items, as it may hinder exploration of items with
greater long-term payoffs. Our paper tackles this issue by utilizing users'
limited attention spans. We propose a model where a platform presents items
with unknown payoffs to the platform in a ranked list to $T$ users over time.
Each user selects an item by first considering a prefix window of these ranked
items and then picking the highest preferred item in that window (and the
platform observes its payoff for this item). We study the design of online
bandit algorithms that obtain vanishing regret against hindsight optimal
benchmarks.
We first consider adversarial window sizes and stochastic iid payoffs. We
design an active-elimination-based algorithm that achieves an optimal
instance-dependent regret bound of $O(\log(T))$, by showing matching regret
upper and lower bounds. The key idea is using the combinatorial structure of
the problem to either obtain a large payoff from each item or to explore by
getting a sample from that item. This method systematically narrows down the
item choices to enhance learning efficiency and payoff.
Second, we consider adversarial payoffs and stochastic iid window sizes. We
start from the full-information problem of finding the permutation that
maximizes the expected payoff. By a novel combinatorial argument, we
characterize the polytope of admissible item selection probabilities by a
permutation and show it has a polynomial-size representation. Using this
representation, we show how standard algorithms for adversarial online linear
optimization in the space of admissible probabilities can be used to obtain a
polynomial-time algorithm with $O(\sqrt{T})$ regret.

使用用户的有限注意力解决推荐系统中的长期回报偏差问题，通过在线贪心算法和多项式时间算法降低后悔度和寻优问题。