Bayesian Optimization-based Combinatorial Assignment

• URL: http://arxiv.org/abs/2208.14698v1
• Date: Wed, 31 Aug 2022 08:47:02 GMT
• Title: Bayesian Optimization-based Combinatorial Assignment
• Authors: Jakob Weissteiner, Jakob Heiss, Julien Siems, Sven Seuken
• Abstract summary: We study the assignment domain, which includes auctions and course allocation. The main challenge in this domain is that the bundle space grows exponentially in the number of items.
• Score: 10.73407470973258
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the combinatorial assignment domain, which includes combinatorial auctions and course allocation. The main challenge in this domain is that the bundle space grows exponentially in the number of items. To address this, several papers have recently proposed machine learning-based preference elicitation algorithms that aim to elicit only the most important information from agents. However, the main shortcoming of this prior work is that it does not model a mechanism's uncertainty over values for not yet elicited bundles. In this paper, we address this shortcoming by presenting a Bayesian Optimization-based Combinatorial Assignment (BOCA) mechanism. Our key technical contribution is to integrate a method for capturing model uncertainty into an iterative combinatorial auction mechanism. Concretely, we design a new method for estimating an upper uncertainty bound that can be used as an acquisition function to determine the next query to the agents. This enables the mechanism to properly explore (and not just exploit) the bundle space during its preference elicitation phase. We run computational experiments in several spectrum auction domains to evaluate BOCA's performance. Our results show that BOCA achieves higher allocative efficiency than state-of-the-art approaches.

Related papers

• Batch Ensemble for Variance Dependent Regret in Stochastic Bandits [41.95653110232677]
  Efficiently trading off exploration and exploitation is one of the key challenges in online Reinforcement Learning (RL) Inspired by practical ensemble methods, in this work we propose a simple and novel batch ensemble scheme that achieves near-optimal regret for Multi-Armed Bandits (MAB) Our algorithm has just a single parameter namely the number of batches, and its value does not depend on distributional properties such as the scale and variance of the losses.
  arXiv  Detail & Related papers  (2024-09-13T06:40:56Z)
• LoRA-Ensemble: Efficient Uncertainty Modelling for Self-attention Networks [52.46420522934253]
  We introduce LoRA-Ensemble, a parameter-efficient deep ensemble method for self-attention networks. By employing a single pre-trained self-attention network with weights shared across all members, we train member-specific low-rank matrices for the attention projections. Our method exhibits superior calibration compared to explicit ensembles and achieves similar or better accuracy across various prediction tasks and datasets.
  arXiv  Detail & Related papers  (2024-05-23T11:10:32Z)
• Equation Discovery with Bayesian Spike-and-Slab Priors and Efficient Kernels [57.46832672991433]
  We propose a novel equation discovery method based on Kernel learning and BAyesian Spike-and-Slab priors (KBASS) We use kernel regression to estimate the target function, which is flexible, expressive, and more robust to data sparsity and noises. We develop an expectation-propagation expectation-maximization algorithm for efficient posterior inference and function estimation.
  arXiv  Detail & Related papers  (2023-10-09T03:55:09Z)
• Machine Learning-Powered Combinatorial Clock Auction [13.724491757145385]
  We study the design of iterative auctions (ICAs) We present a novel method for training an ML model on demand queries. We experimentally evaluate our ML-based demand mechanism in several spectrum auction domains.
  arXiv  Detail & Related papers  (2023-08-20T10:43:50Z)
• Mastering the exploration-exploitation trade-off in Bayesian Optimization [0.2538209532048867]
  The acquisition function drives the choice of the next solution to evaluate, balancing between exploration and exploitation. This paper proposes a novel acquisition function, mastering the trade-off between explorative and exploitative choices, adaptively.
  arXiv  Detail & Related papers  (2023-05-15T13:19:03Z)
• Tree ensemble kernels for Bayesian optimization with known constraints over mixed-feature spaces [54.58348769621782]
  Tree ensembles can be well-suited for black-box optimization tasks such as algorithm tuning and neural architecture search. Two well-known challenges in using tree ensembles for black-box optimization are (i) effectively quantifying model uncertainty for exploration and (ii) optimizing over the piece-wise constant acquisition function. Our framework performs as well as state-of-the-art methods for unconstrained black-box optimization over continuous/discrete features and outperforms competing methods for problems combining mixed-variable feature spaces and known input constraints.
  arXiv  Detail & Related papers  (2022-07-02T16:59:37Z)
• Surrogate modeling for Bayesian optimization beyond a single Gaussian process [62.294228304646516]
  We propose a novel Bayesian surrogate model to balance exploration with exploitation of the search space. To endow function sampling with scalability, random feature-based kernel approximation is leveraged per GP model. To further establish convergence of the proposed EGP-TS to the global optimum, analysis is conducted based on the notion of Bayesian regret.
  arXiv  Detail & Related papers  (2022-05-27T16:43:10Z)
• Efficient Exploration in Binary and Preferential Bayesian Optimization [0.5076419064097732]
  We show that it is important for BO algorithms to distinguish between different types of uncertainty. We propose several new acquisition functions that outperform state-of-the-art BO functions.
  arXiv  Detail & Related papers  (2021-10-18T14:44:34Z)
• Bayesian decision-making under misspecified priors with applications to meta-learning [64.38020203019013]
  Thompson sampling and other sequential decision-making algorithms are popular approaches to tackle explore/exploit trade-offs in contextual bandits. We show that performance degrades gracefully with misspecified priors.
  arXiv  Detail & Related papers  (2021-07-03T23:17:26Z)
• Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration [143.43658264904863]
  We show how iteration under a more standard notion of low inherent Bellman error, typically employed in least-square value-style algorithms, can provide strong PAC guarantees on learning a near optimal value function. We present a computationally tractable algorithm for the reward-free setting and show how it can be used to learn a near optimal policy for any (linear) reward function.
  arXiv  Detail & Related papers  (2020-08-18T04:34:21Z)
• Preferential Batch Bayesian Optimization [16.141259199997005]
  preferential batch Bayesian optimization (PBBO) is a new framework that allows finding the optimum of a latent function of interest. We show how the acquisitions developed under this framework generalize and augment previous approaches in Bayesian optimization.
  arXiv  Detail & Related papers  (2020-03-25T14:59:15Z)

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.