BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//project/author//NONSGML v1.0//EN
CALSCALE:GREGORIAN
BEGIN:VEVENT
DTEND:20230512T120000Z
UID:d40a8407258538e250e9fdf7a1ff1ab8-460
DTSTAMP:19700101T120011Z
DESCRIPTION:Instance-dependent Sample Complexity Bounds for Zero-sum Matrix Games
URL;VALUE=URI:https://www.csa.iisc.ac.in/newweb/event/460/instance-dependent-sample-complexity-bounds-for-zero-sum-matrix-games/
SUMMARY:We study the sample complexity of identifying an approximate equilibrium for two-player zero-sum n×2 matrix games. That is, in a sequence of repeated game plays, how many rounds must the two players play before reaching an approximate equilibrium (e.g., Nash)? We derive instance-dependent bounds that define an ordering over game matrices that captures the intuition that the dynamics of some games converge faster than others. Specifically, we consider a stochastic observation model such that when the two players choose actions i and j, respectively, they both observe each others played actions and a stochastic observation  Xij  such that EXij = Aij. To our knowledge, our work is the first case of instance-dependent lower bounds on the number of rounds the players must play before reaching an approximate equilibrium in the sense that the number of rounds depends on the specific properties of the game matrix A as well as the desired accuracy. We also prove a converse statement: there exist player strategies that achieve this lower bound
<br>
<br>
Microsoft Teams link:
<br>
<a href="https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d">https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d
</a>
<br>
We are grateful to the Kirani family for generously supporting the theory seminar series
<br>
<br>
Hosts: Rameesh Paul, Rahul Madhavan, Aditya Subramanian and Aditya Abhay Lonkar
DTSTART:20230512T120000Z
END:VEVENT
END:VCALENDAR