Image Image Image




Post new topic Reply to topic  [ 6 posts ] 
Author Message
 Post subject: Excessive Gap Technique implementations?
PostPosted: Thu Jan 07, 2010 6:42 pm 
Offline
Senior member
User avatar

Posts: 125
Favourite Bot: wetbot
I've seen lots of discussion here about Counterfactual Regret Minimization (CFRM), but nothing re CMU's EGT. Has anyone tried implementing it? If so, what are your thoughts on it?

With the iterated smoothing improvement shown in the 2008 "First-Order Algorithm with O(ln(1/e)) ..." paper by Gilpin Pena and Sandholm, it seems to have a nice convergence guarantee (while they claim CFRM's convergence rate is unknown?) and also very efficient memory usage. These factors seem to suggest that it might solve larger extensive-form games than CFRM (holding cycles and memory constant). But, to date, I haven't seen direct comparisons of the methods. Would especially like to hear from someone that has implemented both EGT and CFRM and could compare and contrast. Thanks.


Top
 Profile E-mail  
 
 Post subject: Re: Excessive Gap Technique implementations?
PostPosted: Thu Jan 07, 2010 7:59 pm 
Offline
PokerAI fellow
User avatar

Posts: 7731
Favourite Bot: V12
Can you recommend some best paper on this? Or any reference material you would find best for this.

I have a small test bed where I can test vs fictitious play and some (personal) heuristic algorithms (altought I don't have CFRM at place there). That provided I can actually implement EGT in the same testbed.

_________________
indiana


Top
 Profile E-mail  
 
 Post subject: Re: Excessive Gap Technique implementations?
PostPosted: Thu Jan 07, 2010 8:25 pm 
Offline
Junior member
User avatar

Posts: 27
Favourite Bot: custom
Quick google search came up with this paper.
http://www.cs.cmu.edu/~sandholm/first-orderAlgWithLogConvergence.AAAI08.pdf

If there is a more throughout paper than that I would be interested as well.


Top
 Profile E-mail  
 
 Post subject: Re: Excessive Gap Technique implementations?
PostPosted: Thu Jan 07, 2010 8:33 pm 
Offline
Senior member
User avatar

Posts: 125
Favourite Bot: wetbot
Quote:
Can you recommend some best paper on this? Or any reference material you would find best for this.

Sure. Best paper on EGT is here:

http://www.cs.cmu.edu/~gilpin/papers/egt.wine07.pdf

The version of EGT described was O(1/e), but at the end, they muse about O(ln(1/e)), which they later achieved by introducing "iterated smoothing", which is described here:

http://www.cs.cmu.edu/~gilpin/papers/it ... aaai08.pdf

So, really, the 2nd paper supersedes the first, but the first paper gives good background, especially about compact memory utilization, and also linear speedup from parallelization, which is another nice benefit.

Both papers are rather technical, especially the 2nd, but they do have some pseudo-code. Frankly, I don't think I am smart enough to parse the papers well enough to create an implementation without some additional guidance, but I know there are lots of smart people here that don't suffer that impediment.

Also, this powerpoint presentation gives something of an overview starting on slide #51:

http://www.cs.cmu.edu/.../Game%20theory ... 0games.ppt

On slide #52, they show a progression of the state-of-the-art over time, and list EGT as concurrent with CFRM. But, looking at EGT's memory requirements, they look really low, but I haven't seen a direct comparison to that of CFRM. If EGT converges at least as fast CFRM but uses a lot less memory, shouldn't it be able to solve a larger/better abstraction?


Top
 Profile E-mail  
 
 Post subject: Re: Excessive Gap Technique implementations?
PostPosted: Fri Jan 08, 2010 6:02 pm 
Offline
Junior member
User avatar

Posts: 27
Favourite Bot: custom
Wow, my math skills are nowhere near to understand what these papers are talking about. However, from what I understand, they say that the payoff matrix grows sublinear to the game tree size. So sublinear is still linear, otherwise they would say it is logarithmic or something. As I recall CFR uses sequence forms which also grow linear to the game tree size (i think). So as far as memory constrains go they both should be close to each other. However the benefit of excessive gap seems to be the convergence rate of the algorithm. Whereas CFR has no mention of the convergence rate, other then the empirical data shown in the paper. Comments?


Top
 Profile E-mail  
 
 Post subject: Re: Excessive Gap Technique implementations?
PostPosted: Fri Mar 01, 2013 7:48 pm 
Offline
New member
User avatar

Posts: 4
Favourite Bot: my own
I'll go ahead and necropost a little.

May anybody give some input about Excessive Gap Technique? It is said in paper mentioned here, that it gets eps-exploitability solution in O(1/eps) time, i.e. exploitability ~ 1/time. That's actually very impressive, since CFRM's rate of convergence is 1 / sqrt(time). I have CFRM implemented and fully working, and exploitability is proportional to 1/ sqrt(time) indeed, with a good precision.

Memory consumption in CFRM is O(#information sets), and as far as I understand there is no way to improve this even if we use another algorithm, since we have to store the strategy we're working on.


Top
 Profile E-mail  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 6 posts ] 


Who is online

Users browsing this forum: No registered users and 14 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to: