🚀 go-pugleaf

Prof. Munagala from Duke will be giving the CATS talk on Fri.
samir

---------- Forwarded message ----------
Date: Tue, 4 Nov 2008 18:24:45 -0500 (EST)
From: malekian@cs.umd.edu
To: theory-local@cs.umd.edu
Subject: [Theory-local] CATS talk, Friday Nov. 7th, 1 pm, AVW 4185

Event: CATS talk
Date: Nov. 7th
Time: 1 pm
Location: AVW 4185
Title: LP-duality Based Algorithms for Restless Bandit Problem
Speaer: Kamesh Munagala

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 fundamental
decision-theoretic model that captures this trade-off is the celebrated
Multi-arm Bandit Problem. The basic multi-armed bandit problem admits to
an elegant polynomial time solution. However, many stochastic scheduling
applications can only be modeled  using a generalization termed the
Restless Bandit Problem, which in its ultimate generality, 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.
We mention applications of this model to wireless scheduling and unmanned
aircraft navigation. The resulting algorithm is simple and intuitive, and
in addition, applicable to related stochastic scheduling problems.

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

_______________________________________________
Theory-local mailing list
Theory-local@mcfeely.cs.umd.edu
https://mailman.cs.umd.edu/mailman/listinfo/theory-local