Learning to Bid Long-Term: Multi-Agent Reinforcement Learning with Long-Term and Sparse Reward in Repeated Auction Games

• URL: http://arxiv.org/abs/2204.02268v1
• Date: Tue, 5 Apr 2022 15:02:28 GMT
• Title: Learning to Bid Long-Term: Multi-Agent Reinforcement Learning with Long-Term and Sparse Reward in Repeated Auction Games
• Abstract summary: We propose a multi-agent distributed reinforcement learning algorithm that balances between potentially conflicting short-term reward and sparse, delayed long-term reward. We compare different long-term rewards to incentivize the algorithm to maximize individual payoff and overall social welfare.
• Score: 5.865500664175491
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We propose a multi-agent distributed reinforcement learning algorithm that balances between potentially conflicting short-term reward and sparse, delayed long-term reward, and learns with partial information in a dynamic environment. We compare different long-term rewards to incentivize the algorithm to maximize individual payoff and overall social welfare. We test the algorithm in two simulated auction games, and demonstrate that 1) our algorithm outperforms two benchmark algorithms in a direct competition, with cost to social welfare, and 2) our algorithm's aggressive competitive behavior can be guided with the long-term reward signal to maximize both individual payoff and overall social welfare.

Related papers

• Provably Optimal Learning Algorithms for Assistance Games [60.843021846414956]
  We provide the first provably efficient learning algorithms for repeated assistance games.<n>We present decentralized algorithms for both an informed human and the assistant.<n>We prove that achieving a regret approximation factor better than $(1-1/e)$ is computationally intractable.
  arXiv  Detail & Related papers  (2026-07-09T00:38:42Z)
• A Differential Perspective on Distributional Reinforcement Learning [7.028778922533688]
  We extend distributional reinforcement learning to the average-reward setting, where an agent aims to optimize the reward received per time-step.<n>In particular, we utilize a quantile-based approach to develop the first set of algorithms that can successfully learn and/or optimize the long-run per-step reward distribution.
  arXiv  Detail & Related papers  (2025-06-03T19:26:25Z)
• Agent-Temporal Credit Assignment for Optimal Policy Preservation in Sparse Multi-Agent Reinforcement Learning [14.003793644193605]
  In multi-agent environments, agents often struggle to learn optimal policies due to sparse or delayed global rewards. We introduce Temporal-Agent Reward Redistribution (TAR$2$), a novel approach designed to address the agent-temporal credit assignment problem. TAR$2$ decomposes sparse global rewards into time-step-specific rewards and calculates agent-specific contributions to these rewards.
  arXiv  Detail & Related papers  (2024-12-19T12:05:13Z)
• A Robust Mixed-Effects Bandit Algorithm for Assessing Mobile Health Interventions [39.8207428422509]
  "DML-TS-NNR" is a contextual bandit algorithm for mobile health interventions. It addresses challenges like participant heterogeneity, nonstationarity, and nonlinearity in rewards. We demonstrate the superior performance of the DML-TS-NNR algorithm in a simulation and two off-policy evaluation studies.
  arXiv  Detail & Related papers  (2023-12-11T14:24:24Z)
• Impatient Bandits: Optimizing Recommendations for the Long-Term Without Delay [29.23091752603817]
  We study a content exploration task, which we formalize as a multi-armed bandit problem with delayed rewards. We develop a predictive model of delayed rewards that incorporates all information obtained to date. We apply our approach to a podcast recommendation problem, where we seek to identify shows that users engage with repeatedly over two months.
  arXiv  Detail & Related papers  (2023-07-19T12:35:16Z)
• Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics [53.62091043347035]
  We study a game between autobidding algorithms that compete in an online advertising platform. We propose a gradient-based learning algorithm that is guaranteed to satisfy all constraints and achieves vanishing individual regret.
  arXiv  Detail & Related papers  (2023-01-30T21:59:30Z)
• Anti-Concentrated Confidence Bonuses for Scalable Exploration [57.91943847134011]
  Intrinsic rewards play a central role in handling the exploration-exploitation trade-off. We introduce emphanti-concentrated confidence bounds for efficiently approximating the elliptical bonus. We develop a practical variant for deep reinforcement learning that is competitive with contemporary intrinsic rewards on Atari benchmarks.
  arXiv  Detail & Related papers  (2021-10-21T15:25:15Z)
• Optimal and Efficient Algorithms for General Mixable Losses against Switching Oracles [0.0]
  We study the online optimization of mixable loss functions in a dynamic environment. Our results are guaranteed to hold in a strong deterministic sense in an individual sequence manner.
  arXiv  Detail & Related papers  (2021-08-13T21:48:55Z)
• Softmax with Regularization: Better Value Estimation in Multi-Agent Reinforcement Learning [72.28520951105207]
  Overestimation in $Q$-learning is an important problem that has been extensively studied in single-agent reinforcement learning. We propose a novel regularization-based update scheme that penalizes large joint action-values deviating from a baseline. We show that our method provides a consistent performance improvement on a set of challenging StarCraft II micromanagement tasks.
  arXiv  Detail & Related papers  (2021-03-22T14:18:39Z)
• Provably Efficient Algorithms for Multi-Objective Competitive RL [54.22598924633369]
  We study multi-objective reinforcement learning (RL) where an agent's reward is represented as a vector. In settings where an agent competes against opponents, its performance is measured by the distance of its average return vector to a target set. We develop statistically and computationally efficient algorithms to approach the associated target set.
  arXiv  Detail & Related papers  (2021-02-05T14:26:00Z)
• Adaptive Algorithms for Multi-armed Bandit with Composite and Anonymous Feedback [32.62857394584907]
  We study the multi-armed bandit (MAB) problem with composite and anonymous feedback. We propose adaptive algorithms for both the adversarial and non- adversarial cases.
  arXiv  Detail & Related papers  (2020-12-13T12:25:41Z)
• Resource Allocation in Multi-armed Bandit Exploration: Overcoming Sublinear Scaling with Adaptive Parallelism [107.48538091418412]
  We study exploration in multi-armed bandits when we have access to a divisible resource that can be allocated in varying amounts to arm pulls. We focus in particular on the allocation of distributed computing resources, where we may obtain results faster by allocating more resources per pull.
  arXiv  Detail & Related papers  (2020-10-31T18:19:29Z)
• Learning Guidance Rewards with Trajectory-space Smoothing [22.456737935789103]
  Long-term temporal credit assignment is an important challenge in deep reinforcement learning. Existing policy-gradient and Q-learning algorithms rely on dense environmental rewards that provide rich short-term supervision. Recent works have proposed algorithms to learn dense "guidance" rewards that could be used in place of the sparse or delayed environmental rewards.
  arXiv  Detail & Related papers  (2020-10-23T23:55:06Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  We propose unified algorithms for the important cases of first-order expectations and second-order expectations in edge-factored, non-projective spanning-tree models. Our algorithms exploit a fundamental connection between gradients and expectations, which allows us to derive efficient algorithms.
  arXiv  Detail & Related papers  (2020-08-29T14:58: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.