Influencing Bandits: Arm Selection for Preference Shaping
This work addresses the challenge of preference shaping in recommendation systems, which is incremental as it builds on existing bandit and opinion dynamics models.
The paper tackles the problem of shaping population preferences in a non-stationary multi-armed bandit setting where rewards reinforce opinions, aiming to maximize the fraction favoring a predetermined arm. It proposes algorithms like Explore-then-commit and Thompson sampling for binary opinions under decreasing and constant elasticity models, analyzing their regret and extending them to multiple opinion types and scenarios with multiple recommendation systems.
We consider a non stationary multi-armed bandit in which the population preferences are positively and negatively reinforced by the observed rewards. The objective of the algorithm is to shape the population preferences to maximize the fraction of the population favouring a predetermined arm. For the case of binary opinions, two types of opinion dynamics are considered -- decreasing elasticity (modeled as a Polya urn with increasing number of balls) and constant elasticity (using the voter model). For the first case, we describe an Explore-then-commit policy and a Thompson sampling policy and analyse the regret for each of these policies. We then show that these algorithms and their analyses carry over to the constant elasticity case. We also describe a Thompson sampling based algorithm for the case when more than two types of opinions are present. Finally, we discuss the case where presence of multiple recommendation systems gives rise to a trade-off between their popularity and opinion shaping objectives.