A Variational Inequality Approach to Bayesian Regression Games
- URL: http://arxiv.org/abs/2103.13509v1
- Date: Wed, 24 Mar 2021 22:33:11 GMT
- Title: A Variational Inequality Approach to Bayesian Regression Games
- Authors: Wenshuo Guo, Michael I. Jordan, Tianyi Lin
- Abstract summary: We prove the existence of the uniqueness of a class of convex and generalize it to smooth cost functions.
We provide two simple algorithms of solving them with necessarily strong convergence.
- Score: 90.79402153164587
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Bayesian regression games are a special class of two-player general-sum
Bayesian games in which the learner is partially informed about the adversary's
objective through a Bayesian prior. This formulation captures the uncertainty
in regard to the adversary, and is useful in problems where the learner and
adversary may have conflicting, but not necessarily perfectly antagonistic
objectives. Although the Bayesian approach is a more general alternative to the
standard minimax formulation, the applications of Bayesian regression games
have been limited due to computational difficulties, and the existence and
uniqueness of a Bayesian equilibrium are only known for quadratic cost
functions. First, we prove the existence and uniqueness of a Bayesian
equilibrium for a class of convex and smooth Bayesian games by regarding it as
a solution of an infinite-dimensional variational inequality (VI) in Hilbert
space. We consider two special cases in which the infinite-dimensional VI
reduces to a high-dimensional VI or a nonconvex stochastic optimization, and
provide two simple algorithms of solving them with strong convergence
guarantees. Numerical results on real datasets demonstrate the promise of this
approach.
Related papers
- Variational empirical Bayes variable selection in high-dimensional logistic regression [2.4032899110671955]
We develop a novel and computationally efficient variational approximation thereof.
One such novelty is that we develop this approximation directly for the marginal distribution on the model space, rather than on the regression coefficients themselves.
We demonstrate the method's strong performance in simulations, and prove that our variational approximation inherits the strong selection consistency property satisfied by the posterior distribution that it is approximating.
arXiv Detail & Related papers (2025-02-14T19:57:13Z) - Convex Markov Games: A Framework for Creativity, Imitation, Fairness, and Safety in Multiagent Learning [31.958202912400925]
We introduce the class of convex Markov games that allow general convex preferences over occupancy measures.
Despite infinite time horizon and strictly higher generality than Markov games, pure strategy Nash equilibria exist.
Our experiments reveal novel solutions to classic repeated normal-form games, find fair solutions in a repeated asymmetric coordination game, and prioritize safe long-term behavior in a robot warehouse environment.
arXiv Detail & Related papers (2024-10-22T00:55:04Z) - Offline Learning in Markov Games with General Function Approximation [22.2472618685325]
We study offline multi-agent reinforcement learning (RL) in Markov games.
We provide the first framework for sample-efficient offline learning in Markov games.
arXiv Detail & Related papers (2023-02-06T05:22:27Z) - Global Nash Equilibrium in Non-convex Multi-player Game: Theory and
Algorithms [66.8634598612777]
We show that Nash equilibrium (NE) is acceptable to all players in a multi-player game.
We also show that no one can benefit unilaterally from the general theory step by step.
arXiv Detail & Related papers (2023-01-19T11:36:50Z) - Preference learning along multiple criteria: A game-theoretic
perspective [97.94912276610002]
We generalize the notion of a von Neumann winner to the multi-criteria setting by taking inspiration from Blackwell's approachability.
Our framework allows for non-linear aggregation of preferences across criteria, and generalizes the linearization-based approach from multi-objective optimization.
We show that the Blackwell winner of a multi-criteria problem instance can be computed as the solution to a convex optimization problem.
arXiv Detail & Related papers (2021-05-05T03:23:11Z) - VIB is Half Bayes [80.3767111908235]
We show that the Variational Information Bottleneck can be viewed as a compromise between fully empirical and fully Bayesian objectives.
We argue that this approach provides some of the benefits of Bayes while requiring only some of the work.
arXiv Detail & Related papers (2020-11-17T15:36:35Z) - Online and Distribution-Free Robustness: Regression and Contextual
Bandits with Huber Contamination [29.85468294601847]
We revisit two classic high-dimensional online learning problems, namely linear regression and contextual bandits.
We show that our algorithms succeed where conventional methods fail.
arXiv Detail & Related papers (2020-10-08T17:59:05Z) - Stochastic Hamiltonian Gradient Methods for Smooth Games [51.47367707388402]
We focus on the class of Hamiltonian methods and provide the first convergence guarantees for certain classes of smooth games.
Using tools from the optimization literature we show that SHGD converges linearly to the neighbourhood of a gradient.
Our results provide the first global non-asymotic last-rate convergence guarantees for the class of general games.
arXiv Detail & Related papers (2020-07-08T15:42:13Z) - Naive Feature Selection: a Nearly Tight Convex Relaxation for Sparse Naive Bayes [51.55826927508311]
We propose a sparse version of naive Bayes, which can be used for feature selection.
We prove that our convex relaxation bounds becomes tight as the marginal contribution of additional features decreases.
Both binary and multinomial sparse models are solvable in time almost linear in problem size.
arXiv Detail & Related papers (2019-05-23T19:30:51Z)
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.