1 citations · 3 across the 19 of their papers we have counts for
22 papers
On the Power of Adaptivity for -Best Arm Identification in Linear Bandits
Arnab Maiti, Yunbei Xu, Kevin Jamieson
We study the minimax sample complexity of -best arm identification in linear bandits. Given a compact action set that spans and an unknown…
Adversarial Learning in Games with Bandit Feedback: Logarithmic Pure-Strategy Maximin Regret
Shinji Ito, Haipeng Luo, Arnab Maiti +2
Learning to play zero-sum games is a fundamental problem in game theory and machine learning. While significant progress has been made in minimizing external regret in the self-pla…
Revisiting the Bertrand Paradox via Equilibrium Analysis of No-regret Learners
Arnab Maiti, Junyan Liu, Kevin Jamieson +1
We study the discrete Bertrand pricing game with a non-increasing demand function. The game has players who simultaneously choose prices from the set $\{1/k, 2/k, \ldots,…
Efficient Uncoupled Learning Dynamics with Last-Iterate Convergence in Bilinear Saddle-Point Problems over Convex Sets under Bandit Feedback
Arnab Maiti, Claire Jie Zhang, Kevin Jamieson +3
In this paper, we study last-iterate convergence of learning algorithms in bilinear saddle-point problems, a preferable notion of convergence that captures the day-to-day behavior…
Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback
Shinji Ito, Kevin Jamieson, Haipeng Luo +2
We study online learning in finite-horizon episodic Markov decision processes (MDPs) under the challenging aggregate bandit feedback model, where the learner observes only the cumu…
On the Universal Near Optimality of Hedge in Combinatorial Settings
Zhiyuan Fan, Arnab Maiti, Kevin Jamieson +2
In this paper, we study the classical Hedge algorithm in combinatorial settings. In each round, the learner selects a vector from a set ,…
Learning to Incentivize in Repeated Principal-Agent Problems with Adversarial Agent Arrivals
Junyan Liu, Arnab Maiti, Artin Tajdini +2
We initiate the study of a repeated principal-agent problem over a finite horizon , where a principal sequentially interacts with types of agents arriving in an advers…
Efficient Near-Optimal Algorithm for Online Shortest Paths in Directed Acyclic Graphs with Bandit Feedback Against Adaptive Adversaries
Arnab Maiti, Zhiyuan Fan, Kevin Jamieson +2
In this paper, we study the online shortest path problem in directed acyclic graphs (DAGs) under bandit feedback against an adaptive adversary. Given a DAG with a sour…
Near-Optimal Pure Exploration in Matrix Games: A Generalization of Stochastic Bandits & Dueling Bandits
Arnab Maiti, Ross Boczar, Kevin Jamieson +1
We study the sample complexity of identifying the pure strategy Nash equilibrium (PSNE) in a two-player zero-sum matrix game with noise. Formally, we are given a stochastic model w…
Query-Efficient Algorithm to Find all Nash Equilibria in a Two-Player Zero-Sum Matrix Game
Arnab Maiti, Ross Boczar, Kevin Jamieson +1
We study the query complexity of finding the set of all Nash equilibria in two-player zero-sum matrix games. Fearnley and Savani (2016) s…
On the Limitations and Possibilities of Nash Regret Minimization in Zero-Sum Matrix Games under Noisy Feedback
Arnab Maiti, Kevin Jamieson, Lillian J. Ratliff
This paper studies a variant of two-player zero-sum matrix games, where, at each timestep, the row player selects row , the column player selects column , and the row player…
Instance-dependent Sample Complexity Bounds for Zero-sum Matrix Games
Arnab Maiti, Kevin Jamieson, Lillian J. Ratliff
We study the sample complexity of identifying an approximate equilibrium for two-player zero-sum matrix games. That is, in a sequence of repeated game plays, how many r…
Fairness and Welfare Quantification for Regret in Multi-Armed Bandits
Siddharth Barman, Arindam Khan, Arnab Maiti +1
We extend the notion of regret with a welfarist perspective. Focussing on the classic multi-armed bandit (MAB) framework, the current work quantifies the performance of bandit algo…
On Binary Networked Public Goods Game with Altruism
Arnab Maiti, Palash Dey
In the classical Binary Networked Public Goods (BNPG) game, a player can either invest in a public project or decide not to invest. Based on the decisions of all the players, each…
Tight Approximation Algorithms for Two Dimensional Guillotine Strip Packing
Arindam Khan, Aditya Lonkar, Arnab Maiti +2
In the Strip Packing problem (SP), we are given a vertical half-strip and a set of axis-aligned rectangles of width at most . The goal is to find a n…
Parameterized Algorithms for Kidney Exchange
Arnab Maiti, Palash Dey
In kidney exchange programs, multiple patient-donor pairs each of whom are otherwise incompatible, exchange their donors to receive compatible kidneys. The Kidney Exchange problem…
Universal and Tight Online Algorithms for Generalized-Mean Welfare
Siddharth Barman, Arindam Khan, Arnab Maiti
We study fair and efficient allocation of divisible goods, in an online manner, among agents. The goods arrive online in a sequence of time periods. The agents' values for…
On Guillotine Separable Packings for the Two-dimensional Geometric Knapsack Problem
Arindam Khan, Arnab Maiti, Amatya Sharma +1
In two-dimensional geometric knapsack problem, we are given a set of n axis-aligned rectangular items and an axis-aligned square-shaped knapsack. Each item has integral width, inte…
Streaming Algorithms for Stochastic Multi-armed Bandits
Arnab Maiti, Vishakha Patil, Arindam Khan
We study the Stochastic Multi-armed Bandit problem under bounded arm-memory. In this setting, the arms arrive in a stream, and the number of arms that can be stored in the memory a…
On Parameterized Complexity of Binary Networked Public Goods Game
Arnab Maiti, Palash Dey
In the Binary Networked Public Goods game, every player needs to decide if she participates in a public project whose utility is shared equally by the community. We study the probl…
On Parameterized Complexity of Liquid Democracy
Palash Dey, Arnab Maiti, Amatya Sharma
In liquid democracy, each voter either votes herself or delegates her vote to some other voter. This gives rise to what is called a delegation graph. To decide the voters who event…
Query Complexity of Tournament Solutions
Arnab Maiti, Palash Dey
A directed graph where there is exactly one edge between every pair of vertices is called a {\em tournament}. Finding the "best" set of vertices of a tournament is a well studied p…