Search papers, labs, and topics across Lattice.
This paper investigates a multi-agent multi-armed bandit problem within two-sided matching markets, leveraging cumulative prospect theory (CPT) to model human decision-making. By analyzing a state-of-the-art learning algorithm with CPT-weighted rewards, the authors derive a player optimal regret of \(\mathcal{O}(K\log T \left(\frac{1}{螖}\right)^{2/伪})\) and improve this by optimizing the selection of active arms during exploration, achieving optimal regret guarantees when the number of arms significantly exceeds the number of players. Additionally, the study addresses adversarial scenarios where reward corruption occurs, proposing robust algorithms that maintain logarithmic player-optimal regret guarantees in both known and unknown corruption budgets.
Optimizing arm selection in multi-agent bandit settings can eliminate dependence on the number of arms, achieving optimal regret even in adversarial environments.
We study a multi-agent multi-armed bandit problem in the competitive setup with two-sided matching markets under a human centric decision making model. To capture human preferences, we use cumulative prospect theory (CPT) that weighs the actions of the agent in a nonlinear fashion using a ($伪$-H枚lder continuous) weight function. CPT has been widely used in behavioral economics and risk sensitive machine learning to emulate human preferences. We analyze the state-of-the-art learning algorithm with CPT weight distorted rewards and obtain a player optimal regret of $\mathcal{O}(K\log T \left(\frac{1}螖\right)^{2/伪})$, where $K$ denotes the number of arms, $T$ is the learning horizon, and $螖$ represents (suitably defined) players' minimum preference gap. Noticing the dependence on $螖$ to be sub-optimal, we further improve this regret by judiciously selecting the active set of arms during exploration, which removes the dependence on $K$ in the dominant term and achieves an improved (optimal) regret guarantees in the setting where the number of arms $K$ is significantly larger than the number of players $N$. In addition, we consider adversarial markets where the observed rewards of the agents may be corrupted. We propose and analyze algorithms for robust markets with CPT as risk sensitive measure in both settings where the total corruption budget is known and where it is unknown, and establish logarithmic player-optimal regret guarantees in both cases.
