Copertina

Efficient Near-Optimal Algorithm for Online Shortest Paths in Directed Acyclic Graphs with Bandit Feedback Against Adaptive Adversaries

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Maiti, Arnab, Fan, Zhiyuan, Jamieson, Kevin, Ratliff, Lillian J., Farina, Gabriele
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Machine Learning Computer Science and Game Theory
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

On the Universal Near Optimality of Hedge in Combinatorial Settings
di: Fan, Zhiyuan, et al.
Pubblicazione: (2025)

On the Limitations and Possibilities of Nash Regret Minimization in Zero-Sum Matrix Games under Noisy Feedback
di: Maiti, Arnab, et al.
Pubblicazione: (2023)

Query-Efficient Algorithm to Find all Nash Equilibria in a Two-Player Zero-Sum Matrix Game
di: Maiti, Arnab, et al.
Pubblicazione: (2023)

Learning to Incentivize in Repeated Principal-Agent Problems with Adversarial Agent Arrivals
di: Liu, Junyan, et al.
Pubblicazione: (2025)

Efficient Uncoupled Learning Dynamics with $\tilde{O}\!\left(T^{-1/4}\right)$ Last-Iterate Convergence in Bilinear Saddle-Point Problems over Convex Sets under Bandit Feedback
di: Maiti, Arnab, et al.
Pubblicazione: (2026)

On the Optimality of Dilated Entropy and Lower Bounds for Online Learning in Extensive-Form Games
di: Fan, Zhiyuan, et al.
Pubblicazione: (2024)

Online Learning and Equilibrium Computation with Ranking Feedback
di: Liu, Mingyang, et al.
Pubblicazione: (2026)

Algorithms and Complexity of Influence Maximization on Directed Acyclic Graphs
di: Liu, Panfeng, et al.
Pubblicazione: (2026)

GAE Falls Short in Imperfect-Information Self-Play Reinforcement Learning
di: Fan, Zhiyuan, et al.
Pubblicazione: (2026)

The Stability of Online Algorithms in Performative Prediction
di: Farina, Gabriele, et al.
Pubblicazione: (2026)

Online Learning for Uninformed Markov Games: Empirical Nash-Value Regret and Non-Stationarity Adaptation
di: Liu, Junyan, et al.
Pubblicazione: (2026)

Adversarial Learning in Games with Bandit Feedback: Logarithmic Pure-Strategy Maximin Regret
di: Ito, Shinji, et al.
Pubblicazione: (2026)

Parameterized Algorithms for Kidney Exchange
di: Maiti, Arnab, et al.
Pubblicazione: (2021)

Cautious Optimism: A Meta-Algorithm for Near-Constant Regret in General Games
di: Soleymani, Ashkan, et al.
Pubblicazione: (2025)

A Learning Algorithm That Attains the Human Optimum in a Repeated Human-Machine Interaction Game
di: Isa, Jason T., et al.
Pubblicazione: (2025)

Structure from Strategic Interaction & Uncertainty: Risk Sensitive Games for Robust Preference Learning
di: Horwitz, Max, et al.
Pubblicazione: (2026)

Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedback
di: Ba, Wenjia, et al.
Pubblicazione: (2021)

Online Budget Allocation with Censored Semi-Bandit Feedback
di: Bachoc, François, et al.
Pubblicazione: (2025)

Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback
di: Ito, Shinji, et al.
Pubblicazione: (2025)

On the Power of Adaptivity for $\varepsilon$-Best Arm Identification in Linear Bandits
di: Maiti, Arnab, et al.
Pubblicazione: (2026)

An Efficient Black-Box Reduction from Online Learning to Multicalibration, and a New Route to $Φ$-Regret Minimization
di: Farina, Gabriele, et al.
Pubblicazione: (2026)

Mediator Interpretation and Faster Learning Algorithms for Linear Correlated Equilibria in General Extensive-Form Games
di: Zhang, Brian Hu, et al.
Pubblicazione: (2023)

Nearly-Optimal Bandit Learning in Stackelberg Games with Side Information
di: Balcan, Maria-Florina, et al.
Pubblicazione: (2025)

Convergence of Learning Dynamics in Stackelberg Games
di: Fiez, Tanner, et al.
Pubblicazione: (2019)

Generalizing Better Response Paths and Weakly Acyclic Games
di: Yongacoglu, Bora, et al.
Pubblicazione: (2024)

Adaptive Bandit Algorithms for Contextual Matching Markets
di: Lin, Shiyun, et al.
Pubblicazione: (2026)

Optimal Correlated Equilibria in General-Sum Extensive-Form Games: Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation
di: Zhang, Brian, et al.
Pubblicazione: (2022)

Polynomial-Time Computation of Exact $Φ$-Equilibria in Polyhedral Games
di: Farina, Gabriele, et al.
Pubblicazione: (2024)

Strategically Robust Multi-Agent Reinforcement Learning with Linear Function Approximation
di: Gonzales, Jake, et al.
Pubblicazione: (2026)

Emergent specialization from participation dynamics and multi-learner retraining
di: Dean, Sarah, et al.
Pubblicazione: (2022)

Subgame Optimal and Prior-Independent Online Algorithms
di: Hartline, Jason, et al.
Pubblicazione: (2024)

Uncoupled and Convergent Learning in Monotone Games under Bandit Feedback
di: Dong, Jing, et al.
Pubblicazione: (2024)

Near-Linear MIR Algorithms for Stochastically-Ordered Priors
di: Bahar, Gal, et al.
Pubblicazione: (2025)

Optimal Algorithms for Bandit Learning in Matching Markets
di: Pagare, Tejas, et al.
Pubblicazione: (2025)

On Binary Networked Public Goods Game with Altruism
di: Maiti, Arnab, et al.
Pubblicazione: (2022)

Convergence Analysis of Gradient-Based Learning with Non-Uniform Learning Rates in Non-Cooperative Multi-Agent Settings
di: Chasnov, Benjamin, et al.
Pubblicazione: (2019)

Improved Regret and Contextual Linear Extension for Pandora's Box and Prophet Inequality
di: Liu, Junyan, et al.
Pubblicazione: (2025)

Team Belief DAG: Generalizing the Sequence Form to Team Games for Fast Computation of Correlated Team Max-Min Equilibria via Regret Minimization
di: Zhang, Brian Hu, et al.
Pubblicazione: (2022)

Nearly Minimax Optimal Submodular Maximization with Bandit Feedback
di: Tajdini, Artin, et al.
Pubblicazione: (2023)

Two-Player Zero-Sum Games with Bandit Feedback
di: Yılmaz, Elif, et al.
Pubblicazione: (2025)