Matching Markets meet Cumulative Prospect Theory: Towards Optimal and Adversarially Robust Learning

• URL: http://arxiv.org/abs/2606.19883v1
• Date: Thu, 18 Jun 2026 07:43:05 GMT
• Title: Matching Markets meet Cumulative Prospect Theory: Towards Optimal and Adversarially Robust Learning
• Abstract summary: 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.<n>We use cumulative prospect theory (CPT) that weighs the actions of the agent in a nonlinear fashion using a ($$-Hlder continuous) weight function.
• Score: 8.823317238417834
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Regret Minimization in Bilateral Trade With Perturbed Markets [25.375074054942434]
  We address the problem of maximizing Gain from Trade (GFT) in repeated buyer-seller exchanges subject to global budget balance constraints.<n> adversarial environments allow for no-regret learning against the best fixed-price mechanism.<n>Our algorithm maintains the worst-case $tildemathcalO(T3/4)$ regret bound relative to a per-round budget-balanced baseline.
  arXiv  Detail & Related papers  (2026-05-11T12:37:53Z)
• On the Exploitability of FTRL Dynamics [3.072746147114436]
  We show that exploitability is an inherent feature of the Follow-the-Regularized-Leader family, rather than an artifact of specific instantiations.<n>Our analysis uncovers once more the sharp dichotomy: non-steep regularizers allow maximum surplus via finite-time elimination of suboptimal actions, whereas steep ones introduce a vanishing correction that may delay exploitation.
  arXiv  Detail & Related papers  (2026-04-06T19:46:45Z)
• Reinforcement Learning from Multi-Source Imperfect Preferences: Best-of-Both-Regimes Regret [71.69884486156359]
  We study episodic RL from emphmulti-source imperfect preferences through a cumulative imperfection budget.<n>We propose a unified algorithm with regret $tildeO(sqrtK/M+)$, which exhibits a best-of-both-regimes behavior.
  arXiv  Detail & Related papers  (2026-03-20T19:34:53Z)
• Nearly Tight Regret Bounds for Profit Maximization in Bilateral Trade [14.182863671689836]
  Bilateral trade models the task of intermediating between two strategic agents, a seller and a buyer, willing to trade a good for which they hold private valuations.<n>We study this problem from the perspective of a broker, in a regret minimization framework.<n>We propose a learning algorithm that guarantees a nearly tight $tildeO(sqrtT)$ regret when seller and valuations are drawn.
  arXiv  Detail & Related papers  (2025-09-26T16:42:05Z)
• Two-Player Zero-Sum Games with Bandit Feedback [6.66618805642802]
  We study a two-player zero-sum game in which the row player aims to maximize their payoff against an adversarial column player.<n>We propose three algorithms based on the Explore-Then-Commit framework.
  arXiv  Detail & Related papers  (2025-06-17T13:46:32Z)
• Robust Reinforcement Learning from Corrupted Human Feedback [86.17030012828003]
  Reinforcement learning from human feedback (RLHF) provides a principled framework for aligning AI systems with human preference data. We propose a robust RLHF approach -- $R3M$, which models the potentially corrupted preference label as sparse outliers. Our experiments on robotic control and natural language generation with large language models (LLMs) show that $R3M$ improves robustness of the reward against several types of perturbations to the preference data.
  arXiv  Detail & Related papers  (2024-06-21T18:06:30Z)
• Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback [58.66941279460248]
  Learning from human feedback plays an important role in aligning generative models, such as large language models (LLM)<n>We study a model within this domain--contextual dueling bandits with adversarial feedback, where the true preference label can be flipped by an adversary.<n>We propose an algorithm namely robust contextual dueling bandits (RCDB), which is based on uncertainty-weighted maximum likelihood estimation.
  arXiv  Detail & Related papers  (2024-04-16T17:59:55Z)
• Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
  This paper studies the problem of contextual dueling bandits, where the binary comparison of dueling arms is generated from a generalized linear model (GLM) We propose a new SupLinUCB-type algorithm that enjoys computational efficiency and a variance-aware regret bound $tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$. Our regret bound naturally aligns with the intuitive expectation in scenarios where the comparison is deterministic, the algorithm only suffers from an $tilde O(d)$ regret.
  arXiv  Detail & Related papers  (2023-10-02T08:15:52Z)
• Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games [104.74734408204749]
  We show that if all agents in a multi-player general-sum normal-form game employ Optimistic Multiplicative Weights Update (OMWU), the external regret of every player is $O(textrmpolylog(T))$ after $T$ repetitions of the game. We extend their result from external regret to internal regret and swap regret, thereby establishing uncoupled learning dynamics that converge to an approximate correlated equilibrium.
  arXiv  Detail & Related papers  (2021-11-11T01:19:53Z)
• Risk-Sensitive Reinforcement Learning: Near-Optimal Risk-Sample Tradeoff in Regret [115.85354306623368]
  We study risk-sensitive reinforcement learning in episodic Markov decision processes with unknown transition kernels. We propose two provably efficient model-free algorithms, Risk-Sensitive Value Iteration (RSVI) and Risk-Sensitive Q-learning (RSQ) We prove that RSVI attains an $tildeObig(lambda(|beta| H2) cdot sqrtH3 S2AT big)$ regret, while RSQ attains an $tildeObig(lambda
  arXiv  Detail & Related papers  (2020-06-22T19:28:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.