A new algorithm reduces online eigenvector computation time while maintaining optimal performance.
problem Online learning of top eigenvectors in both adversarial and stochastic settings.
method Follow the Compressed Leader (FTCL) framework, compressing the matrix strategy to dimensions 3 (adversarial) and 1 (stochastic).
result Achieves optimal regret without sacrificing running time, resolving open questions.
Characterizes preferences for decision-making under uncertainty using a leader-follower game model.
problem Decision-making under uncertainty and ambiguity aversion.
method Characterizes niveloidal preferences through a leader-follower game model, satisfying specific axioms.
result The leader's strategy space can serve as an ambiguity aversion index.
We introduce CSE for MLSF games and devise online learning algorithms for achieving no-external Stackelberg-regret.
problem Learning equilibrium in leader-follower games with noisy bandit feedback.
method Proposed Correlated Stackelberg Equilibrium (CSE) and online learning algorithms balancing exploration and exploitation.
result Achieves no-external Stackelberg-regret, converging to approximate CSE.
New RL algorithms learn QSE from strategic feedbacks with sample efficiency.
problem Learning QSE in Markov games with strategic feedbacks.
method Proposes sample-efficient algorithms for online and offline settings, combining quantal response model learning and RL.
result Achieves sublinear regret bounds and quantifies model uncertainty.
Study leader-follower games with terminal state constraints using McKean-Vlasov SDEs.
problem Leader-follower games with terminal state constraints.
method Linear McKean-Vlasov forward-backward SDEs, existence and uniqueness results, convergence results.
result Existence and uniqueness of solutions for leader-follower games with constraints.
Investors with asymmetric information play a game to optimize their portfolios.
problem Two investors with different information levels compete in portfolio selection.
method Modelled as a Stackelberg game with entropy-regularized mean-variance objectives.
result Equilibria exist where follower's strategy depends on leader's actions.
Neural operators approximate Stackelberg game solutions.
problem Intractability of follower's best-response operator in dynamic Stackelberg games.
method Used attention-based neural operators to approximate the best-response operator.
result Approximate best-response operator yields close game value.
Study of 2 i m e s 2 2 imes 2 2 im es 2 zero-sum games with noisy observations and commitments.
problem Analyzing 2 i m e s 2 2 imes 2 2 im es 2 zero-sum games with noisy observations and commitments. method Modeling a 2 i m e s 2 2 imes 2 2 im es 2 zero-sum game with a leader committing to a strategy and a follower observing a noisy version of the leader's action. result Observing the leader's action is either beneficial or immaterial for the follower, and the equilibrium payoff is bounded.
Game theory approach to predicting and responding to interventions based on causal relationships.
problem Optimizing predictions and interventions in response to observational data.
method Prediction-intervention game framework, focusing on invariant subsets of covariates.
result Stable-blanket predictors are optimal for certain follower objectives and under specific conditions.
CB-RL solves complex decision-making problems with contextual information and exogenous events.
problem Optimal policy in strategic decision-making problems that depend on environmental configuration and exogenous events.
method Contextual Bilevel Reinforcement Learning (CB-RL) with a stochastic Hyper Policy Gradient Descent (HPGD) algorithm.
result Demonstrated convergence and performance of the HPGD algorithm for reward shaping and tax design.
FTPL with Fréchet perturbation achieves near optimal regret bounds for m-set semi-bandit problems.
problem Optimizing regret bounds for m-set semi-bandit problems in adversarial and stochastic settings.
method Follow-the-Perturbed-Leader (FTPL) with Fréchet perturbation.
result Achieves near optimal regret bounds of O ( n m ( d log ( d ) + m 5 / 6 ) ) \mathcal{O}(\sqrt{nm}(\sqrt{d\log(d)}+m^{5/6})) O ( nm ( d log ( d ) + m 5/6 )) in adversarial setting and logarithmic regret in stochastic setting. Adaptive learning rates improve FTPL's BOBW guarantees in bandit problems.
problem Improving Follow-the-Perturbed-Leader's BOBW guarantees in bandit problems.
method Introducing surrogate probability functions to compute adaptive learning rates without exact probabilities.
result BOBW guarantees for FTPL with Pareto perturbations for any α > 1 α>1 α > 1 . New mechanism designs regulate herding in financial markets.
problem Herding causes irrational market decisions and volatility.
method A trilateral game framework based on optimal control theory.
result Effective mechanisms improve social welfare.
Paper optimizes FTPL for adversarial and stochastic bandits with specific tail distributions.
problem Optimizing Follow-the-Perturbed-Leader (FTPL) policy for bandit problems.
method Analyzes FTPL with Fréchet-type tail distributions in adversarial and stochastic settings.
result FTPL with certain Fréchet-type tail distributions achieves O ( K T ) \mathcal{O}(\sqrt{KT}) O ( K T ) regrets in adversarial bandits. SLHF uses sequential game theory to optimize preferences from human feedback.
problem Optimizing preferences from human feedback in sequential settings.
method SLHF frames the problem as a sequential-move game between Leader and Follower, decomposing the optimization into refinement and adversarial optimization.
result SLHF achieves strong alignment across diverse preference datasets and scales to large models.
Using a two-point correlation technique, we study emergence of market efficiency in the emergent Russian futures market by focusing on lagged correlations. The correlation strength of leader-follower effects in the lagged inter-market correlations on the hourly time frame is seen to be significant initially (2009-2011)…
LEASGD improves privacy-preserving decentralized learning with lower communication costs.
problem Achieving efficient and private decentralized learning.
method Proposes LEASGD, a Leader-Follower Elastic Averaging Stochastic Gradient Descent algorithm.
result LEASGD outperforms state-of-the-art algorithms in terms of lower loss and reduced communication costs.
Paper studies zero-sum games with noisy observations and identifies equilibrium conditions.
problem Zero-sum games with noisy observations of the leader's actions.
method Analyzes the equilibrium of games with noisy action observability, identifies necessary conditions for uniqueness, and investigates the cardinality of best responses.
result The noisy observations significantly impact the cardinality of the follower's set of best responses, and under certain conditions, this set becomes a singleton almost surely.
FTPL achieves optimal regret in online non-convex learning.
problem Online non-convex learning with non-convex losses.
method Follow the Perturbed Leader (FTPL) algorithm.
result FTPL achieves optimal regret rate of O ( T − 1 / 2 ) O(T^{-1/2}) O ( T − 1/2 ) . Advances FTPL results for bandit problems with unbounded perturbations.
problem Improving analytical foundations of FTPL in bandit problems.
method Revisiting classical FTRL-FTPL duality for unbounded perturbations.
result Establishes Best-of-Both-Worlds (BOBW) results for FTPL under a broad family of asymmetric unbounded perturbations.
FTPL policy achieves best-of-both-worlds regret in decoupled bandits with reduced computational cost.
problem Decoupled multi-armed bandit problem with observed and unobserved losses.
method Follow-the-Perturbed-Leader (FTPL) policy that avoids convex optimization and resampling.
result Achieves constant regret in stochastic regime and optimal O ( K T ) O(\sqrt{KT}) O ( K T ) regret in adversarial regime. New algorithm optimizes multi-armed bandits with low computational cost.
problem Optimizing multi-armed bandits with low computational cost.
method Proposes a new FTPL algorithm with optimistic principle for ambiguity.
result Unified regret analysis and low computational costs.
Paper analyzes FTPL's effectiveness in combinatorial semi-bandit problems.
problem Optimizing FTPL policy in combinatorial semi-bandit problems.
method Geometric resampling (GR) and conditional geometric resampling (CGR) for FTPL in semi-bandit setting.
result FTPL achieves optimal regret bounds in both Fréchet and Pareto distributions.
Proposes a new training algorithm for zero-sum games to avoid convergence issues.
problem Gradient-based training leads to weak convergence and cyclic dynamics in zero-sum architectures.
method Follow the perturbed leader algorithm with neural mediating agent.
result Guarantees convergence to mixed Nash equilibrium without cyclic behaviors.
This paper improves FTPL algorithm for semi-bandit problems with best-of-both-worlds guarantees.
problem Optimizing regret in adversarial and stochastic m m m -set semi-bandit problems. method Extending FTPL with geometric resampling (GR) to m m m -set semi-bandits and analyzing its performance. result FTPL with Fréchet and Pareto distributions achieves O ( m d T ) O(\sqrt{mdT}) O ( m d T ) regret in adversarial setting and logarithmic regret in stochastic setting. New aggregation strategy handles unbounded losses with regret bounds.
problem Online optimization with unbounded loss functions.
method Follow The Regularized Leader (FTRL) with φ-divergence.
result Worst regret bound for unbounded losses with alternative divergences.
The paper explores how regularization can lead to convergence in imperfect information games.
problem Finding equilibrium in imperfect information games with imperfect information.
method Investigates Follow the Regularized Leader dynamics and how adding a regularization term can lead to strong convergence guarantees.
result The approach leads to algorithms that converge exactly to the Nash equilibrium in imperfect information games.
New RL algorithms find SNE in Markov games with myopic followers.
problem Finding SNE in Markov games with myopic followers.
method Optimistic and pessimistic variants of least-squares value iteration, incorporating function approximation.
result First provably efficient RL algorithms for SNEs in general-sum Markov games with myopic followers.
New algorithms improve dueling bandit performance in multiplayer settings.
problem Challenges in collaborative exploration of non-informative arm pairs in multiplayer dueling bandits.
method Demonstrated Follow Your Leader approach and message-passing fully distributed protocol.
result Multiplayer algorithms outperform single-player benchmarks.
Communities in social networks or graphs are sets of well-connected, overlapping vertices. The effectiveness of a community detection algorithm is determined by accuracy in finding the ground-truth communities and ability to scale with the size of the data. In this work, we provide three contributions. First, we show t…
Improved bounds for adversarial bandits with variance analysis.
problem Optimizing decision-making in adversarial environments with varying gaps.
method First-order bounds, variance analysis, gap-dependent bounds for follow the regularized leader.
result Improved bounds for adversarial bandits with a factor of log(n)/log(log(n)) improvement.
AMM finds optimal contract for LPs to maximize order flow.
problem Maximizing order flow in AMMs with LPs.
method Leader-follower stochastic game, closed-form equilibrium solutions.
result LPs incentivized to add liquidity when external price attracts more noise trading.
FTPL method shows near-optimal regret bounds for AMDPs with bandit feedback.
problem Minimizing regret in AMDPs with adversarial losses and bandit feedback.
method Follow-the-Perturbed-Leader (FTPL) method for AMDPs.
result FTPL achieves near-optimal regret bounds for AMDPs with bandit feedback.
Optimal bounds on regret and constraint violation in adversarial COCO.
problem Minimizing regret and cumulative constraint violation in adversarial COCO.
method New surrogate loss function and Follow-the-Regularized-Leader/Online Gradient Descent.
result Achieved optimal O ( T ) O(\sqrt{T}) O ( T ) bounds on both regret and cumulative constraint violation. Improved FTPL algorithm reduces regret in predictable minimax games.
problem Online learning and minimax games with predictable loss sequences.
method Optimistic modification of FTPL with dual regularization view.
result Tighter regret bounds for predictable sequences, O ( T − 1 / 2 ) O(T^{-1/2}) O ( T − 1/2 ) accuracy. Mutation improves FTRL convergence in zero-sum games.
problem Lack of last-iterate convergence in FTRL variants.
method Introduced mutation to perturb action probabilities in FTRL.
result M-FTRL converges to Nash equilibria under full-information feedback.
Unified algorithm for linear bandits with improved regret bound.
problem Adversarial linear bandits with improved regret.
method Self-concordant perturbations in FTPL framework.
result Regret bound of O ( d n ln n ) \mathcal{O}(d\sqrt{n \ln n}) O ( d n ln n ) for hypercube and ℓ 2 \ell_2 ℓ 2 ball. New algorithm expands FTRL framework with improved worst-case regret bounds.
problem Online learning with improved worst-case regret bounds.
method Generalized implicit Follow-The-Regularized-Leader (FTRL) algorithm.
result Unified framework for designing updates improving worst-case regret bounds.
New algorithm reduces individual regret and communication costs in cooperative bandits.
problem Optimal individual and group regret in cooperative multi-agent bandits.
method Integrates a new communication policy into a learning algorithm.
result Achieves optimal individual regret and constant communication costs.
Algorithm optimizes functions without parameters, converging to global minima.
problem Optimizing functions without parameters.
method Follow The Regularized Leader with rescaled gradients and time-varying regularizers.
result Converges to global minimizer for variationally coherent functions.
New algorithm reduces online learning iterations by a factor of T^2/3.
problem Efficiency in online learning with smooth cost functions.
method Follow-the-Perturbed-Leader method using online primal-dual framework.
result Guaranteed T^2/3 regret for general online convex optimization.
New algorithm reduces regret in online learning for piecewise continuous functions.
problem Exponential loss in efficiency when moving from classical to adversarial learning.
method Introduces generalized bracketing numbers and Follow-the-Perturbed-Leader algorithm.
result Optimal scaling of optimization oracle calls with average regret.
Improved online learning for MDPs with changing costs.
problem Online learning in linearly solvable MDPs with changing state costs.
method Following the leader algorithm with logarithmic regret bound.
result Achieved regret of order log^2 T, significantly better than previous bounds.
Optimal multiclass U-calibration error found to be Θ(√KT).
problem Online multiclass U-calibration with low regret for all bounded proper losses.
method Follow-the-Perturbed-Leader algorithm and lower bound construction.
result Optimal U-calibration error is Θ(√KT).
We show a principled way of deriving online learning algorithms from a minimax analysis. Various upper bounds on the minimax value, previously thought to be non-constructive, are shown to yield algorithms. This allows us to seamlessly recover known methods and to derive new ones. Our framework also captures such "unort…
This paper extends FTPL algorithms for bandits beyond bounded hazard rate assumptions.
problem Adversarial multi-armed bandit problem with perturbations.
method Introduces new regret bounds for FTPL algorithms without bounded hazard rate assumption.
result Gaussian distribution leads to near optimal regret, up to logarithmic factors.
Follow-the-Leader (FTL) is an intuitive sequential prediction strategy that guarantees constant regret in the stochastic setting, but has terrible performance for worst-case data. Other hedging strategies have better worst-case guarantees but may perform much worse than FTL if the data are not maximally adversarial. We…
New algorithms accelerate imitation learning from expert data.
problem Sample inefficiency in reinforcement learning.
method Model-based algorithms inspired by Follow-the-Leader (FTL) with prediction.
result Provable acceleration of convergence rate up to an order.