Non-Stationary Bandits under Recharging Payoffs: Improved Planning with Sublinear Regret

In the last two decades, the predominant rise of the social media industry has made the notion of a newsfeed an integral part of our lives. In a newsfeed, a user observes a structured sequence of content items (posts, photos etc.) particularly selected by the platform according to her/his preferences. Apart from social media, an analogous idea - potentially relabeled - also appears in different domains as, for example, "frequently bought together" in e-commerce, "shuffling similar songs" in music recommendation, or "recommended articles" in scholarly literature indexing databases. Whether it is measured in terms of click-rate or time devoted, the high-level objective of newsfeeds is fairly well-known: to maximize the user's engagement with the platform. In many applications, however, achieving this objective is not as simple as identifying the user's "favorite" content, given that her/his satisfaction can depend on the time passed since the same (or similar) content has been observed. As an example, a user's engagement can worsen if a social media feed (resp., a music recommendation platform) constantly presents content from the same source (resp., same artist). Motivated by such scenarios, researchers have recently studied online decision making problems capturing the notion of "recovering" payoffs, namely, scenarios where the payoff of an action drops (to zero) after each play and then slowly increases back to a baseline. In the context of online learning, these nonstationary models interpolate between multi-armed bandits, where the environment is assumed to be intact, and reinforcement learning, since the actions may now alter the future environment in a structured manner.