TL;DR
This paper introduces the Weighted Tallying Bandit (WTB), a new online learning framework that models situations where an agent's performance depends on its recent history, accounting for the decaying nature of human memory. They propose an efficient algorithm that achieves near-optimal performance by leveraging a "Repeated Exposure Optimality" condition, which is inspired by human learning and physiological phenomena.
What Problem Does This Paper Address?
Many real-world applications, like recommender systems or crowdsourcing, involve agents interacting with humans. In these scenarios, a human's preferences or abilities aren't static; they can be influenced by the agent's recent actions. For example, a worker might need a "calibration period" to perform optimally, and their memory of past tasks fades over time. Existing "tallying bandit" models capture the idea that an action's cost depends on how often it was recently chosen (within a memory window $m$). However, these models often treat all past occurrences equally. This paper addresses the limitation that human memory decay is not uniform – recent events have a stronger impact than older ones within the memory window. They introduce the Weighted Tallying Bandit (WTB) to model this more accurately, where the cost is a weighted sum of recent action counts, reflecting memory decay.
Methods
The core of the paper is the Weighted Tallying Bandit (WTB) framework, which generalizes existing tallying bandits by incorporating a weighted sum of past action counts. To make this tractable, they introduce the Repeated Exposure Optimality (REO) condition. REO posits that there exists an action that, when repeatedly performed, eventually yields a loss lower than any other action sequence, even accounting for some suboptimality ($\alpha$). This condition is motivated by phenomena like "warm-up decrement" in human motor skills.
Their main algorithmic contribution is a modified Successive Elimination (SE) algorithm. This algorithm, when provided with an upper bound $M$ on the unknown memory capacity $m$, achieves a Complete Policy Regret (CPR) guarantee of $O(\sqrt{KT} + (m+M)K)$. CPR is a strong measure of regret, considering the worst-case optimal policy. They also prove a lower bound of $\Omega(mK + M)$ for CPR, demonstrating their algorithm's near-optimality.
Datasets
The paper uses simulated datasets for evaluation. Specifically:
- Synthetic Loss Functions: Used to test the algorithm in controlled environments, including scenarios with and without the $\alpha$-REO condition.
- Simulated Dart Throwing Tournament: Based on real-world observations of dart players' performance stabilization after initial throws, this simulates a calibration period.
- Simulated F1 Tournament: Leverages real F1 lap time data (1950-2022) to model driver performance that improves with practice (lap index).
Key Insights and Ideas
- Weighted Memory Decay: The core idea is that human memory isn't a simple counter within a fixed window. Recent events matter more, and WTB captures this by weighting recent action counts. This is a more realistic model for human-interactive systems.
- Repeated Exposure Optimality (REO): This condition is crucial for tractability. It ensures that there's a "best" action that eventually shines through, even if it requires some initial "warm-up" or calibration. This bridges the gap between theoretical models and real-world phenomena like learning curves.
- Near-Optimal CPR with Additive $m$ Dependence: The most significant theoretical result is achieving a CPR guarantee that scales favorably with the horizon $T$ and number of actions $K$, with only an additive dependence on the memory parameters ($m$ and $M$). This is a major improvement over prior work where $m$ often appeared multiplicatively.
- Impossibility of Full Adaptivity to $m$: The paper proves that it's impossible to design an algorithm that is fully adaptive to an unknown memory capacity $m$ (i.e., doesn't require an upper bound $M$) while achieving sublinear CPR. This highlights the necessity of providing an upper bound $M$.
Key Results
- Algorithm SE: A modified Successive Elimination algorithm achieves a Complete Policy Regret (CPR) of $O(\sqrt{KT} + (m+M)K)$ for WTB problems satisfying REO. This is nearly optimal, with a lower bound of $\Omega(mK + M)$.
- Comparison to sMAB: The CPR guarantee for WTB with REO is comparable to the traditional regret guarantee for simpler stochastic multi-armed bandits (sMAB), differing mainly by an additive term in $mK$ and $M$.
- Experimental Validation: Numerical simulations on synthetic data and realistic scenarios (darts, F1 racing) demonstrate that the proposed SE algorithm significantly outperforms baseline methods like EXP3, EXP3B, and UCB. The performance of SE is shown to be robust to the choice of the upper bound $M$.
Limitations and Future Work
- Optimality of $\alpha$ Dependence: While the algorithm's dependence on $m$ and $M$ is shown to be optimal (up to logarithmic factors), the dependence on the REO parameter $\alpha$ is not fully characterized as optimal for all values of $\alpha$.
- Modeling Fatigue/Deterioration: The current WTB model primarily captures the "warm-up" or calibration phase. It doesn't explicitly model scenarios where performance might degrade after prolonged activity (e.g., fatigue). Future work could explore models that handle both improvement and deterioration.
- Individual Memory Capacities: The current model assumes a single memory capacity $m$ for all actions. Extending this to allow each action to have its own memory capacity ($m_x$) would be a more general and potentially more accurate model for some applications.
- Recommender Systems: While motivated by recommender systems, the paper suggests further work is needed to quantitatively analyze real-world recommender system data to confirm the existence of WTB with REO structures and to demonstrate the practical impact of the proposed methods.
Summary updated