In this paper we investigate the Follow the Regularized Leader dynamics in sequential imperfect information games (IIG). We generalize existing results of Poincaré recurrence from normal-form games to zero-sum two-player imperfect information games and other sequential game settings. We then investigate how adapting th…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,657 papers · 148 categories
Trend · papers per month
48 results for “imperfect information games”
A Policy-Gradient Approach to Solving Imperfect-Information Games with Best-Iterate Convergencecs.GT
Policy gradient method proves convergence in imperfect-information games.
problem Policy gradient methods in imperfect-information games (EFGs).
method Policy gradient approach with best-iterate convergence.
result Policy gradient leads to provable best-iterate convergence in self-play EFGs.
JPS improves joint policies for multi-agent collaboration in imperfect information games.
problem Learning good joint policies for multi-agent collaboration with imperfect information.
method Decomposes global changes to localized policy changes, iteratively improving joint policies without re-evaluating the entire game.
result JPS improves solutions provided by unilateral approaches and outperforms algorithms designed for collaborative policy learning.
Study learns optimal strategies in imperfect information games with self-play.
problem Learning optimal strategies in imperfect information games.
method Proposes Follow the Regularized Leader (FTRL) algorithms for imperfect information games.
result Proposes two FTRL algorithms: Balanced FTRL and Adaptive FTRL.
Model-Free Learning for Two-Player Zero-Sum Partially Observable Markov Games with Perfect Recallstat.ML
Algorithm learns NE in imperfect information games with imperfect feedback.
problem Learning Nash equilibrium in imperfect information games with bandit feedback.
method IXOMD algorithm for model-free learning with convergence rate.
result IXOMD achieves convergence rate to NE.
Paper solves learning imperfect-information games with fewer episodes.
problem Learning imperfect-information extensive-form games from bandit feedback.
method Balanced Online Mirror Descent and Balanced Counterfactual Regret Minimization algorithms.
result Achieves near-optimal sample complexity for finding approximate Nash equilibria.
DREAM learns optimal strategies in imperfect games without needing a simulator.
problem Learning optimal strategies in imperfect-information games with multiple agents.
method DREAM is a deep reinforcement learning algorithm that converges to Nash Equilibria and coarse correlated equilibria.
result DREAM achieves state-of-the-art performance in benchmark games and is competitive with simulator-based algorithms.
Study on liquidity and market efficiency in auction games with imperfect information.
problem Generating liquidity in illiquid auction markets with imperfect information.
method Characterized Nash equilibria in a two-player game with imperfect information, linking market spreads to signal strength.
result Without incentives, the market is inefficient and does not lead to trades. Quadratic fees indexed on half spread can generate liquidity.
RLCFR improves CFR's generalization in imperfect information games.
problem Improving CFR's performance in large-scale, imperfect information games.
method RLCFR integrates CFR with deep reinforcement learning to update strategies dynamically.
result RLCFR significantly enhances CFR's generalization ability in various games.
We introduce a new virtual environment for simulating a card game known as "Big 2". This is a four-player game of imperfect information with a relatively complicated action space (being allowed to play 1,2,3,4 or 5 card combinations from an initial starting hand of 13 cards). As such it poses a challenge for many curre…
Adaptive OMD reduces variance in learning optimal strategies for imperfect information games.
problem High variance in learning optimal strategies for imperfect information games.
method Fixed sampling approach with locally applied Online Mirror Descent (OMD) algorithm.
result Convergence rate of with high probability.
Lazy-CFR: fast and near optimal regret minimization for extensive games with imperfect informationcs.LG
Counterfactual regret minimization (CFR) is the most popular algorithm on solving two-player zero-sum extensive games with imperfect information and achieves state-of-the-art performance in practice. However, the performance of CFR is not fully understood, since empirical results on the regret are much better than the …
We study pricing and superhedging strategies for game options in an imperfect market with default. We extend the results obtained by Kifer in \cite{Kifer} in the case of a perfect market model to the case of an imperfect market with default, when the imperfections are taken into account via the nonlinearity of the weal…
Cross-dimensional neural networks improve AI in Catan game.
problem Challenging to build AI agents for Catan game using RL.
method Introduced cross-dimensional neural networks to handle game complexities.
result RL agent outperforms best heuristic agent in Catan.
First sample-efficient algorithm for learning EFCE in bandit feedback settings.
problem Learning EFCE in bandit feedback settings for IIEFGs.
method Proposed -EFCE and uncoupled no-regret algorithm with wide-range regret minimization.
result First sample-efficient algorithm for learning EFCE from bandit feedback.
Investigates a Kyle model with imperfect information and risk aversion.
problem Tackles a Kyle model with imperfect information and risk-averse informed traders.
method Solves an optimal transport problem and a filtering problem under specific measures.
result Constructs an equilibrium for the Gaussian Kyle model with imperfect information and risk aversion.
This paper tackles sample-efficient reinforcement learning for partially observable Markov games.
problem Learning in partially observable Markov games with incomplete information.
method A simple algorithm combining optimism and Maximum Likelihood Estimation (MLE) for self-play, and a variant of optimistic MLE for adversarial opponents.
result The proposed algorithms achieve approximate Nash, correlated, and coarse correlated equilibria in polynomial samples for weakly revealing POMGs.
On April 13th, 2019, OpenAI Five became the first AI system to defeat the world champions at an esports game. The game of Dota 2 presents novel challenges for AI systems such as long time horizons, imperfect information, and complex, continuous state-action spaces, all challenges which will become increasingly central …
Bayesian probability theory is one of the most successful frameworks to model reasoning under uncertainty. Its defining property is the interpretation of probabilities as degrees of belief in propositions about the state of the world relative to an inquiring subject. This essay examines the notion of subjectivity by dr…
Partial-monitoring games constitute a mathematical framework for sequential decision making problems with imperfect feedback: The learner repeatedly chooses an action, opponent responds with an outcome, and then the learner suffers a loss and receives a feedback signal, both of which are fixed functions of the action a…
Optimization of parameterized policies for reinforcement learning (RL) is an important and challenging problem in artificial intelligence. Among the most common approaches are algorithms based on gradient ascent of a score function representing discounted return. In this paper, we examine the role of these policy gradi…
From the early days of computing, games have been important testbeds for studying how well machines can do sophisticated decision making. In recent years, machine learning has made dramatic advances with artificial agents reaching superhuman performance in challenge domains like Go, Atari, and some variants of poker. A…
Real life hedging in the Black-Scholes model must be imperfect and if the stock's drift is higher than the risk free rate, leads to a profit on average. Hence the option price is examined as a fair game agreement between the parties, based on expected payoffs and a simple measure of risk. The resulting prices result in…
This work presents a game-theoretic method for AVs that handles imperfect communication and individual rewards.
problem Real-time, imperfect communication and individual rewards in multi-agent interactions.
method Game-theoretic approach that allows for imperfect communication and individual rewards.
result More realistic assumptions lead to better reward inference and prediction of future actions.
Bayesian framework calibrates imperfect models using physics-informed priors and Hamiltonian Monte Carlo.
problem Quantifying uncertainty in imperfect computer models described by differential equations.
method Physics-informed Gaussian process priors, discrepancy function, Hamiltonian Monte Carlo, data approximations.
result Framework accurately recovers true parameters and produces accurate predictions.
The paper tackles targeted attacks on rank aggregation methods, proving the fixed point of adversarial game.
problem The security issue of rank aggregation methods, especially the vulnerability to targeted attacks.
method Formulated as a game-theoretic framework, the attack behavior is a fixed point of the composition of the adversary and the victim.
result The victims will produce the target ranking list once the adversary has complete information.
We derive asset pricing formula for markets with incomplete information and subjective views.
problem Asset pricing in markets with informational imperfections and subjective investor beliefs.
method Closed-form market equilibrium formula based on Merton's model, non-linear system of equations, conditional posterior distribution.
result Derivation of market reference model for excess returns under random shadow-costs.
Paper introduces a method to learn physics between digital twins using imperfect models.
problem Learning physics from imperfect data and low-fidelity models.
method Bayesian Hierarchical modeling with physics-informed Gaussian processes.
result Models learning between digital twins are less uncertain than independent models but not over-confident.
Modeling the purposeful behavior of imperfect agents from a small number of observations is a challenging task. When restricted to the single-agent decision-theoretic setting, inverse optimal control techniques assume that observed behavior is an approximately optimal solution to an unknown decision problem. These tech…
Policy gradient and actor-critic algorithms form the basis of many commonly used training techniques in deep reinforcement learning. Using these algorithms in multiagent environments poses problems such as nonstationarity and instability. In this paper, we first demonstrate that standard softmax-based policy gradient c…
Forecasting Uncertain Events with Small Groupscond-mat.stat-mech
We present a novel methodology for predicting future outcomes that uses small numbers of individuals participating in an imperfect information market. By determining their risk attitudes and performing a nonlinear aggregation of their predictions, we are able to assess the probability of the future outcome of an uncert…
Solves a game between brokers and informed traders using stochastic differential equations.
problem Optimizing wealth in a game between brokers and informed traders with private signals.
method Closed-form solutions to a mean-field game using forward-backward SDEs.
result Optimal trading strategies for both brokers and informed traders are found.
Missing Information and Asset Allocationcond-mat.stat-mech
When the available statistical information is imperfect, it is dangerous to follow standard optimisation procedures to construct an optimal portfolio, which usually leads to a strong concentration of the weights on very few assets. We propose a new way, based on generalised entropies, to ensure a minimal degree of dive…
In 2015, Google's DeepMind announced an advancement in creating an autonomous agent based on deep reinforcement learning (DRL) that could beat a professional player in a series of 49 Atari games. However, the current manifestation of DRL is still immature, and has significant drawbacks. One of DRL's imperfections is it…
Selective planning with imperfect models reduces harmful effects of model inadequacy.
problem Harmful effects of using an imperfect model in reinforcement learning.
method Selective planning with heteroscedastic regression to estimate predictive uncertainty from model inadequacy.
result Effective selective planning requires considering both parameter uncertainty and model inadequacy.
Investors' strategic trading affects asset prices, modeled as a game.
problem Investors' trading rates influence asset prices in dynamic markets.
method Model as a non-zero sum singular stochastic differential game, establishing equivalence between best-response and auxiliary control problems.
result Unique Nash equilibrium is deterministic with a closed-form solution.
In this paper the theory of semi-bounded rationality is proposed as an extension of the theory of bounded rationality. In particular, it is proposed that a decision making process involves two components and these are the correlation machine, which estimates missing values, and the causal machine, which relates the cau…
In this paper, we investigate Dimensionality reduction (DR) maps in an information retrieval setting from a quantitative topology point of view. In particular, we show that no DR maps can achieve perfect precision and perfect recall simultaneously. Thus a continuous DR map must have imperfect precision. We further prov…
Study proves value of non-Markovian games with partial, asymmetric info.
problem Value of non-Markovian Dynkin games with partial and asymmetric information.
method Probabilistic and functional analytic approach based on Sion's min-max theorem.
result Existence of optimal strategies for both players in randomised stopping times.
DefogGAN: Predicting Hidden Information in the StarCraft Fog of War with Generative Adversarial Netscs.LG
DefogGAN predicts hidden RTS game information to aid strategic decision-making.
problem Predicting hidden information in real-time strategy games like StarCraft.
method Conditional Generative Adversarial Network (GAN) with pyramidal reconstruction loss.
result DefogGAN predicts enemy buildings and combat units as accurately as professional players.
Most approaches aiming to ensure a model's fairness with respect to a protected attribute (such as gender or race) assume to know the true value of the attribute for every data point. In this paper, we ask to what extent fairness interventions can be effective even when only imperfect information about the protected at…
Paper defines saddle points in asymmetric Dynkin games using martingale theory.
problem Tackles saddle point conditions in asymmetric Dynkin games with partial information.
method Uses martingale theory to identify super and submartingales related to equilibrium payoffs.
result Characterizes saddle point strategies in terms of equilibrium payoffs' dynamics and Doob-Meyer decompositions.
Financial markets, with their vast range of different investment opportunities, can be seen as a system of many different simultaneous games with diverse and often unknown levels of risk and reward. We introduce generalizations to the classic Kelly investment game [Kelly (1956)] that incorporates these features, and us…
The paper tackles learning from imperfect human feedback, especially in dueling bandit problems.
problem Learning from human feedback that can be irrational or imperfect.
method Developed a Robustified Stochastic Mirror Descent for Imperfect Dueling (RoSMID) algorithm.
result Achieved nearly optimal regret for dueling bandit problems under imperfect human feedback.
Study best-response learning dynamics in zero-sum polymatrix games under full and minimal information settings.
problem Learning dynamics in zero-sum polymatrix games under different information settings.
method Two-timescale learning dynamics combining smoothed best-response updates and TD-learning for estimating local payoff functions.
result Polynomial-time finite-sample guarantees for convergence to an ε-Nash equilibrium in the minimal information case.
Imitation learning (IL) aims to learn an optimal policy from demonstrations. However, such demonstrations are often imperfect since collecting optimal ones is costly. To effectively learn from imperfect demonstrations, we propose a novel approach that utilizes confidence scores, which describe the quality of demonstrat…
Multi-asset minority gamesphysics.soc-ph
We study analytically and numerically Minority Games in which agents may invest in different assets (or markets), considering both the canonical and the grand-canonical versions. We find that the likelihood of agents trading in a given asset depends on the relative amount of information available in that market. More s…
New framework uses tempered optimism to handle imperfect experts in online learning.
problem Challenges of implicit optimism in practical online learning environments.
method Introduces tempered optimism as a framework for online non-convex learning, modifies existing algorithms.
result Demonstrates tempered optimism as a fruitful paradigm for online non-convex learning.