Reward attribution in deep q learning and texas holdem poker

I’m having issues with reward attribution in poker using deep q learning. Multiple actions will yield one reward, but the reward is only known at the end of the hand, not before.

I have built a gym environment for Texas Hold’em, with the idea to use deep q agents to learn how to outperform random poker players: www.gitnub.com/dickreuter/neuron_poker

One of the difficulties I’m facing is the correct reward attribution after each move. The reward will be known at the end of the hand only but before I could only approximate it with a montecarlo simulation that would be subject to a number of assumptions and most probably not precise enough.

My question is therefore: would it be a valid approach to only give the agent only the reward after it becomes known what the outcome of the hand is? Specifically, an action at pre flop (no cards yet on the table), then another one at the flop (3 cards are put in the table) and finally at turn and river will collectively yield a single reward that is only known when the hand is over. Shouldn’t all actions therefore have the same reward that is then being used for experience replay?

Any suggestions on how the reward calculation is best addressed would be appreciated. It seems an essential part of the problem.

Any suggestions on how the reward calculation is best addressed would be appreciated. It seems an essential part of the problem.

It is. This is part of what is called the credit assignment problem.

The good news is that all Reinforce Learning (RL) algorithms - of which Q learning is one type - are designed to solve this problem. Some are better than others at this aspect of learning, but when you are talking about just a few steps of delay between no known reward and an end of episode total, then this is not a major difficulty of your problem as far as RL goes. Therefore, you should base the reward function on signalling goals of the agent as simply and purely as possible. For a single poker game this might be winning, drawing or losing, or possibly the amount of money won at the end of each hand. A really good agent for instance - that would be hard to develop - might be able to figure out when to suffer a loss over a game or two, so as to encourage opponents to make mistakes later on.

In short then, make your reward function simple and sparse. It is common to have RL systems where nearly all rewards are $$0$$, because success task or failure are only known at the end of a long episode. Or seemingly equally uninformative you might have all rewards $$-1$$ when the goal is to complete a task quickly (in this case the fact that there are no more rewards at the end of the task means that maximising total reward is the same thing as minimising the time it took).

RL agents solve the credit assignment problem by tracking some aggregate of rewards - sometimes called the return or the utility. In Q learning, the tracking mechanism is action values - the return is the expected, discounted* sum of all future rewards, when taking action $$a$$ in state $$s$$ and thereafter following a fixed policy. The action values are usually noted as $$Q(s,a)$$.

The Q learning update rule links different time steps together in order to improve the agent's estimate for the correct action values. For basic, single-step Q-learning, this is a relatively simple update rule (compared to other RL agents that may perform better at Poker) that you can apply when you know a start state $$s$$, the action taken $$a$$, the immediate reward $$r$$ that resulted, and the next state $$s'$$:

$$Q(s,a) \leftarrow Q(s,a) + \alpha(r + \gamma \text{max}_{a'} Q(s',a') - Q(s,a))$$

You can see this explicitly links the estimate between one time step (related to $$s, a$$) and the next (related to $$r, s'$$). It doesn't matter to Q learning agents that many rewards in the middle of a game will be $$0$$. Over many iterations, this back tracking of aggregate value into earlier and earlier estimates will allow the agent to make more optimal decisions at early states.

Having said that, Poker is known to be a very tough game for learning agents to play well. The lack of information about opponents' cards, and use of bets to signal or misdirect intentions over the long term are tough challenges to resolve. Basic Q learning is not adequate for learning high level play, although it may still be instructive to make a Poker bot using Q learning. It should still beat your completely random agents, as they are somewhat predictable in a statistical sense of having fixed distributions of success/fail without needing to know what cards they hold during play.

would it be a valid approach to only give the agent only the reward after it becomes known what the outcome of the hand is?

Yes this is normal.

Specifically, an action at pre flop (no cards yet on the table), then another one at the flop (3 cards are put in the table) and finally at turn and river will collectively yield a single reward that is only known when the hand is over.

Yes this is normal. The first two time steps will have a reward of $$0$$, and the last time step will be allocated all the reward associated with that example.

Shouldn’t all actions therefore have the same reward that is then being used for experience replay

No, only the last step should store the reward associated with it - i.e. only ever store the immediate reward in the experience replay table.

This is important, the Q learning update rule works by in part by allocating the rewards back through time steps statistically. It also means that if there is more than one way to get into a desirable state, but that sometimes due to chance that state may still fail, the agent will still try to follow the failed trajectories into the good state (and vice versa, just because one lucky game scored well from a terrible position should still mean the agent will learn to avoid that position).

Monte Carlo updates work a little bit more like your idea. What these do technically is calculate the return or utility from each time step, and update action value estimates at the end of the episode. This also works, but storing those returns in a Q learning experience replay table and using in place of immediate reward is probably not going to work very well because the Q learning agent is already doing the same aggregation of rewards.

* "Discounted" refers to the discount factor $$\gamma \le 1$$ which helps set a finite measure for continuous tasks (you may not need this for a Poker bot, where play is episodic). There are also alternatives such as setting a finite horizon, or using the expected long-term mean reward per time step. What these all have in common is that they are aggregates of the reward signal that measure long-term success.

• Thanks for the detailed answer. Just to clarify, you think that giving no reward at all at the intermediate steps will lead to better convergence than giving some kind of estimated reward through a simulation with ex-post knowledge of the action? It seems counter intuitive, but I'll give it a try now. – Nickpick Jul 10 '19 at 21:56
• @Nickpick: Yes that is the case. Although you can grant intermediate rewards prior to reaching a goal, if you know what you are doing, it is just as likely to cause problems. Focus on rewards that are a true measure of the goal first, and let the algorithm do its job. – Neil Slater Jul 11 '19 at 8:40
• It appears to have improved the performance quite a bit. But I'm still struggling with illegal moves. Currently, I give an immediate reward of -100 (arbitrary number) for illegal moves but I'm not ending the episode. Any opinion on that? – Nickpick Jul 11 '19 at 9:54
• I also have a follow up question: stats.stackexchange.com/questions/416942/… – Nickpick Jul 11 '19 at 10:00
• For illegal moves in games, it is more usual to filter them out and not let the agent take them. Maximise Q over the allowed moves. Unless the moves can actually be taken with real consequences in your target environment, or they are impossible to detect when they happen (e.g. they only turn out to be considered "illegal" at the end), then there is no real benefit to teach the agent to discover this by itself. – Neil Slater Jul 11 '19 at 11:48