[Lowerbounds, Upperbounds]

FRIDAY FEBRUARY 15TH
3:30PM
WEH 7220

TITLE: LP-duality Based Algorithms for Restless Bandit Problems

Kamesh Munagala, Duke University

Abstract:

In numerous areas of operations research and artificial intelligence, we face a problem common to gamblers choosing slot machines (or bandits) in a casino: whether to try new machines or keep playing the one we know and hope for the best! More generally, we face the trade-off between exploration and exploitation: between learning from and adapting to a stochastic system and exploiting our current best-knowledge. A model that captures this trade-off is the celebrated Multi-arm Bandit Problem, which was formulated and solved many decades ago, and has since then become a fundamental tool in decision theory. However, in many stochastic applications, we cannot use the basic multi-arm bandit model, but must consider a generalization called the Restless Bandit Problem. Although this problem has been extensively studied, little positive progress has been made. In fact, it has been proven that in its ultimate generality, the restless bandit problem is PSPACE-Hard to approximate to any non-trivial factor.

In this talk, we derive a 2-approximation algorithm for a general subclass of the Restless Bandit Problem, in which the state-transition probability for each bandit is “separable” into a constant probability matrix and a vector of arbitrary monotone functions of time. The monotonicity models increasing levels of uncertainty as time-since-last-observation increases, which occurs in many applications such as in wireless scheduling. The resulting algorithm is simple and intuitive.

To derive the result, we modify a well-known LP relaxation, take its dual, and add a “balance” condition which provides more structure to the LP. From the dual variables, we construct an index policy, and prove that it’s a 2-approximation by using complementary slackness and a potential function argument. Our techniques are fairly clean, yield simple index policies with small approximation factors, and are applicable to related stochastic scheduling problems.

Joint work with Sudipto Guha, UPenn, and Peng Shi, Duke.

Date: 2008-02-13 12:00
Room: NSH 1507
Speaker: Katrina Ligett
Title: A Learning Theory Approach to Non-Interactive Database Privacy

Abstract:

We demonstrate that, ignoring computational constraints, it is possible to release privacy-preserving databases that are useful for all queries over a discretized domain from any given concept class with polynomial VC-dimension. We show a new lower bound for releasing databases that are useful for halfspace queries over a continuous domain. Despite this, we give a privacy-preserving polynomial-time algorithm that releases information useful for all halfspace queries, for a slightly relaxed definition of usefulness. Inspired by learning theory, we introduce a new notion of data privacy, which we call distributional privacy, and show that it is strictly stronger than the prevailing privacy notion, differential privacy.