BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1692
DTSTAMP:20260218T043348Z
SUMMARY:Window Mean Payoff in Turn-Based Stochastic Games
DESCRIPTION:Speaker: Pranshu Gaba (TIFR)\n\nAbstract: \nWe look at turn-bas
 ed stochastic games\, which are two-player zero-sum games played on direct
 ed graphs in which each edge has a payoff associated with it and each vert
 ex is either controlled by Player 1 or by Player 2\, or is a probabilistic
  vertex. The game begins by placing a token on an initial vertex. Then\, w
 henever the token is on a player-controlled vertex\, that player chooses a
 n out-edge and whenever the token is on a probabilistic vertex\, an out-ed
 ge is chosen according to the underlying distribution\, and in both cases\
 , the token moves along the chosen edge. The play goes on in this manner f
 orever\, resulting in an infinite path in the graph\, which in turn gives 
 an infinite sequence of payoffs for Player 1. Fixing strategies of both pl
 ayers gives a distribution over plays in the graph. A well-studied object
 ive in stochastic games is the mean-payoff objective\, which requires that
  the average payoff per turn in the limit of the play be non-negative. In 
 this thesis\, we study a finitary version of the mean-payoff objective cal
 led the window mean-payoff objective. The window mean-payoff objective str
 engthens the mean-payoff objective by requiring that the average payoff be
 come non-negative in every sliding window (of bounded length) of the play.
  In particular\, we see algorithms for the following decision problems:- S
 atisfaction: Does Player 1 have a strategy to ensure\, with probability at
  least p\, that the window mean-payoff value of the play is non-negative?-
  Expectation: Does Player 1 have a strategy to ensure that the window mean
 -payoff value of the play is non-negative in expectation?- Optimizing expe
 ctation with guarantees: Does Player 1 have a strategy to simultaneously e
 nsure that the window mean-payoff value of the play is non-negative surely
  (or almost-surely or limit-surely) and is greater than a given threshold 
 in expectation?- Sure-almost-sure satisfaction (in Markov Decision Process
 es (MDPs)): Does Player 1 have a strategy to simultaneously ensure that th
 e window mean-payoff value of the play is non-negative surely and is great
 er than a given threshold almost-surely? (MDPs are a special case of stoch
 astic games with no Player 2 controlled vertices.)Moreover\, whenever a wi
 nning strategy exists for a player\, we show how to construct the strategy
  and also give bounds on the amount of memory required to define the strat
 egy.\n
URL:https://www.tcs.tifr.res.in/web/events/1692
DTSTART;TZID=Asia/Kolkata:20260226T174500
DTEND;TZID=Asia/Kolkata:20260226T184500
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR