NSF Award CCF-0745761

CAREER: Light-weight near optimal stochastic control policies for information acquisition and exploitation

PI:                                   Kamesh Munagala
Graduate students:          Sayan Bhattacharya (2008-present)
Undergraduate students: Peng Shi (2007-10)

This project aims to develop theoretical models for the problems of uncertainty and imprecise information in computing and communication systems such as wireless sensor networks and grid computers, and design algorithms and policies to ameliorate their impact on system performance, thereby leading to more effective larger-scale deployments of such systems. The goal will also be to develop algorithms for computing dynamic information acquisition strategies in uncertain environments, that jointly optimize the cost of acquiring more information, together with the gain from exploiting the information to enhance system performance. This class of problems falls within the larger area of stochastic control theory.

Multi-armed Bandit Problems: 
The multi-armed bandit problem in stochastic decision theory models the key trade-off between exploring the state space and exploiting the current best option. Though this problem admits to an elegant efficient optimal policy known as the Gittins index, it is well-known that such index policies become increasingly sub-optimal in the presence of cost constraints, time-varying uncertain information, blocking constraints, etc. We present a generic solution technique that combines the efficiency of index policies with provable performance guarantees.

Approximation algorithms for restless bandit problems (with Sudipto Guha and Peng Shi) J.ACM, 58(1), 2010
Combined final version of this paper in FOCS '07 and this paper in SODA '09.

Multi-armed bandits with metric switching costs (with Sudipto Guha) ICALP '09.
Improves and generalizes this paper which is a full version of this paper in STOC '07.

Iterated allocations with delayed feedback (with Sudipto Guha and Martin Pal) Submitted
Applications to Clustering: The first paper presents simple to implement constant factor approximations for the stochastic version of the k-center problem. The second paper defines a new similarity metric for clustering anomalous data, and devises a fast agglomerative technique to cluster faults in system execution traces

Exceeding expectations and clustering uncertain data (with Sudipto Guha) PODS '09.

Fa: A System for Automating Failure Diagnosis (with Songyun Duan and Shivnath Babu) ICDE '09.

Applications to Auction Design: We present a simple mechanism for making bidders reveal their uncertainty truthfully in keyword search auctions. We also extend the results to repeated auctions under a simple model of uncertainty.
Hybrid keyword search auctions (with Ashish Goel) WWW '09.    (Winner of best paper award)

We consider the problem of designing multi-unit auctions when bidders have private budget constraints. We show that a natural yet counter-intuitive auction due to Ausubel is not only truthful but also Pareto-optimal and revenue optimal in this setting. The hard part, surprisingly, is to show truthfulness. We also present the first approximation results for revenue optimal multi-item auctions when bidders have arbitrary demand and budget constraints. Our mechanisms are surprisingly simple posted price schemes.
Incentive compatible budget elicitation in multi-unit auctions (with Sayan Bhattacharya, Vincent Conitzer, and Lirong Xia) SODA '10.

Budget constrained auctions with heterogeneous items (with Sayan Bhattacharya, Gagan Goel, and Sreenivas Gollapudi) STOC '10.