Source author record

Arnab Maiti

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computer Science and Game Theory Data Structures and Algorithms Machine Learning Computational Complexity Computational Geometry

Catalog footprint

Research overview

4works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

On the Power of Adaptivity for $\varepsilon$ -Best Arm Identification in Linear Bandits

We study the minimax sample complexity of $\varepsilon$ -best arm identification in linear bandits. Given a compact action set $\mathcal{X}$ that spans $\mathbb{R}^d$ and an unknown reward vector $θ\in\mathbb{R}^d$ , the goal is to output an arm $\widehat{x}\in\mathcal{X}$ such that $\langle \widehat{x},θ\rangle \ge \max_{x\in\mathcal{X}} \langle x,θ\rangle - \varepsilon$ with probability at least $1-δ$ , using as few samples as possible. First, we present a non-adaptive fixed-design method with sample complexity $\mathcal{O}\!\left(\frac{d\log(1/δ)}{\varepsilon^2}+\frac{w(\mathcal{X})^2}{\varepsilon^2}\right)$ , where $w(\mathcal{X})$ is a Gaussian width term dependent on $\mathcal{X}$ , and we prove a matching lower bound $Ω\!\left(\frac{d\log(1/δ)}{\varepsilon^2}+\frac{w(\mathcal{X})^2}{\varepsilon^2}\right)$ for all non-adaptive fixed-design methods. We then turn to adaptive sampling. We raise an important structural question: beyond the canonical basis, are there structured action sets for which adaptivity yields only logarithmic-factor improvements over the optimal non-adaptive rate? We answer in the affirmative for several natural action sets, namely the hypercube, the $\ell_2$ ball, $m$ -sets, and multi-task multi-armed bandits. Finally, we provide the first construction of an action set $\mathcal{X}$ for which adaptivity yields a polynomial-factor improvement over every non-adaptive algorithm. A key ingredient behind this separation is an $\ell_2$ -norm estimation subroutine: we design an adaptive algorithm that uses $\mathcal{O}\!\left(\frac{d\log(1/δ)}{\varepsilon^2}\right)$ samples from the unit $\ell_2$ ball in $\mathbb{R}^d$ and outputs an estimate $\widehat r$ satisfying $|\widehat r-\|θ\|_2|\le \varepsilon$ with probability at least $1-δ$ , where $θ$ is the unknown reward vector.

preprint2024arXiv

On Binary Networked Public Goods Game with Altruism

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 player receives a reward as per his/her utility function. However, classical models of BNPG game do not consider altruism which players often exhibit and can significantly affect equilibrium behavior. Yu et al. (2021) extended the classical BNPG game to capture the altruistic aspect of the players. We, in this paper, first study the problem of deciding the existence of a Pure Strategy Nash Equilibrium (PSNE) in a BNPG game with altruism. This problem is already known to be NP-Complete. We complement this hardness result by showing that the problem admits efficient algorithms when the input network is either a tree or a complete graph. We further study the Altruistic Network Modification problem, where the task is to compute if a target strategy profile can be made a PSNE by adding or deleting a few edges. This problem is also known to be NP-Complete. We strengthen this hardness result by exhibiting intractability results even for trees. A perhaps surprising finding of our work is that the above problem remains NP-Hard even for bounded degree graphs when the altruism network is undirected but becomes polynomial-time solvable when the altruism network is directed. We also show some results on computing an MSNE and some parameterized complexity results. In summary, our results show that it is much easier to predict how the players in a BNPG game will behave compared to how the players in a BNPG game can be made to behave in a desirable way.

preprint2022arXiv

Fairness and Welfare Quantification for Regret in Multi-Armed Bandits

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 algorithms by applying a fundamental welfare function, namely the Nash social welfare (NSW) function. This corresponds to equating algorithm's performance to the geometric mean of its expected rewards and leads us to the study of Nash regret, defined as the difference between the -- a priori unknown -- optimal mean (among the arms) and the algorithm's performance. Since NSW is known to satisfy fairness axioms, our approach complements the utilitarian considerations of average (cumulative) regret, wherein the algorithm is evaluated via the arithmetic mean of its expected rewards. This work develops an algorithm that, given the horizon of play $T$ , achieves a Nash regret of $O \left( \sqrt{\frac{k \log T}{T}} \right)$ , here $k$ denotes the number of arms in the MAB instance. Since, for any algorithm, the Nash regret is at least as much as its average regret (the AM-GM inequality), the known lower bound on average regret holds for Nash regret as well. Therefore, our Nash regret guarantee is essentially tight. In addition, we develop an anytime algorithm with a Nash regret guarantee of $O \left( \sqrt{\frac{k\log T}{T}} \log T \right)$ .

preprint2022arXiv

Tight Approximation Algorithms for Two Dimensional Guillotine Strip Packing

In the Strip Packing problem (SP), we are given a vertical half-strip $[0,W]\times[0,\infty)$ and a set of $n$ axis-aligned rectangles of width at most $W$ . The goal is to find a non-overlapping packing of all rectangles into the strip such that the height of the packing is minimized. A well-studied and frequently used practical constraint is to allow only those packings that are guillotine separable, i.e., every rectangle in the packing can be obtained by recursively applying a sequence of edge-to-edge axis-parallel cuts (guillotine cuts) that do not intersect any item of the solution. In this paper, we study approximation algorithms for the Guillotine Strip Packing problem (GSP), i.e., the Strip Packing problem where we require additionally that the packing needs to be guillotine separable. This problem generalizes the classical Bin Packing problem and also makespan minimization on identical machines, and thus it is already strongly NP-hard. Moreover, due to a reduction from the Partition problem, it is NP-hard to obtain a polynomial-time $(3/2-\varepsilon)$ -approximation algorithm for GSP for any $\varepsilon>0$ (exactly as Strip Packing). We provide a matching polynomial time $(3/2+\varepsilon)$ -approximation algorithm for GSP. Furthermore, we present a pseudo-polynomial time $(1+\varepsilon)$ -approximation algorithm for GSP. This is surprising as it is NP-hard to obtain a $(5/4-\varepsilon)$ -approximation algorithm for (general) Strip Packing in pseudo-polynomial time. Thus, our results essentially settle the approximability of GSP for both the polynomial and the pseudo-polynomial settings.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Arnab Maiti

Research overview

Is this your work?

4 publications

On the Power of Adaptivity for $\varepsilon$ -Best Arm Identification in Linear Bandits

On Binary Networked Public Goods Game with Altruism

Fairness and Welfare Quantification for Regret in Multi-Armed Bandits

Tight Approximation Algorithms for Two Dimensional Guillotine Strip Packing

See the researcher in context

Building this map preview

Arnab Maiti

Research overview

Is this your work?

4 publications

On the Power of Adaptivity for ε\varepsilonε-Best Arm Identification in Linear Bandits

On Binary Networked Public Goods Game with Altruism

Fairness and Welfare Quantification for Regret in Multi-Armed Bandits

Tight Approximation Algorithms for Two Dimensional Guillotine Strip Packing

See the researcher in context

Building this map preview

On the Power of Adaptivity for $\varepsilon$ -Best Arm Identification in Linear Bandits