Now, we kind of cheated here. Because I told you there's just
these, those two strategies. But there's actually a bunch of other strategies
you can play against tit for tat. And it's worth thinking through,
how do you compute a best response to some finite-state strategy? So
tit for tat is a finite-state strategy in that it has these
two [LAUGH], these two states. And the strategies expressed in terms of
transitions between those two states. But in general, if we have some
kind of finite-state strategy, like tit for tat, how do we figure
out how to maximize our own reward in the
face of playing against that strategy? So in this
picture here that I drew, the states are labeled
with the opponent's choice, the finite state strategies choice, okay?
>> Mm-hm.
>> The edges, that's in black, the edges and
labeled in green here, are labeled with our choice.
So, for example, if we're in this state of
the, sorry, if our opponent is in this state.
>> Mm-hm.
>> We have a choice. We can either
cooperate or defect. On this round.
>> Mm-hm.
>> So, the green arrows tell us how that will impact the state of the
opponent. And then these red numbers, I
just added the information about well I know
that if the opponant is about to cooperate and I choose to cooperate. I can
just look up in the pay off matrix that that's a -1 for me. Right? Agreed?
>> Agreed.
>> So I just annotated all these edges, all these choices with these
extra numbers. So, one of the things that's cool about this is unlike
just the payoff matrix representation that we had before, our
choice, it impacts the payoff, which is the same as
that, but it also impacts the future decisions of the
opponent. And that gives us this structure here and also
says that maybe this is a slightly harder thing to
figure out because of the fact that we can't just
maximize our, the number. We actually have to think about
where that's going to lead us in the future as well.
>> So two things then. One,
I was always fond of saying that the matrix was all that you
needed. But that really only made sense when you were just playing once.
>> Yes. That's right.
>> Right? And, two, I look at this and it's a finite state machine
but you know what else it looks like to me? It looks like an MDP.
>> Excellent. It is indeed an MDP. Now,
it's a, in this case, my opponent's finite
state strategy is deterministic, so it's a deterministic
MDP, but it is. It's a discounted MDP.
Gamma's playing the role of the discount factor.
The entries from the payoff matrix are playing
the roles of rewards Our action is playing
the choice of our action, and the opponent's
internal state structure is playing the role our
states. So it is, it's an MDP, and
so how do we figure out what an
optimal strategy is against a finite state strategy?
>> We solve the MDP.
>> Yeah, exactly. So any, any method for solving an MDP can then be used
to actually compute the strategy, so what is the strategy going to look like? It
is going to be a mapping from states of the opponent to action choices for us.
>> Right, but that's fine because a state
does not have to be your state, it's
just what matters. What matters in this case
is what they opponent is going to do.
>> Right. So now what are the strategies
that can be meaningful against tit for tat?
>> So
if we cooperate then we're going to stay in
this state and it's always going to be the
right thing to do to cooperate. So always
cooperate is one. If we always, if we defect,
now we have a choice again so we
could defect from this state which would cause us
to defect forever, so always defect is another
one. But what's the other thing that could happen?
>> Well, we could tit for tat ourselves.
>> Well, sort of. I mean, so, we could defect, so we could
defect against cooperate, but cooperate against defect. Which
would actually cause us to do D-C, D-C,
D-C. So those are the only, oh I see. No, you're right. I'm not sure how to
say it. But the policy is, defect when
you're in this state, and cooperate when you're in
this state. But the effect of that is to go back and forth against tit for tat.
>> Right.
>> Basically, take this loop here.
And those are the only policies that matter. And in this case, we
worked out that. Always cooperate is good against tit for tat if it has
a high discount factor and always defect is better if you have a
low discount factor. But, we can get that for real by solving the MDP.
>> Right and that makes sense and the reason that those are only
3, let me see if I get this right, the reason those are the
only 3 that makes sense because if you think of this as an MDP
then it has no history, so when you are in C there are only
2 choices and when you are in D there are
really only two choices so if you look at the way
you've drawn it. You either stay were you are in
c or d, or you take the loop. And those are
really the only three options because the rest of them
would require you remember what you did, you know, a time
step or two ago, and there's no way to do
that in an MDP, at least not as you've written it.
>> Well, there's a way to do it, it just would never be better
than doing it this way. So an MDP always has a mark off deterministic
optimal policy.
>> Right.
>> So we only need to consider those.
>> I think that was the same thing that
I was trying to say, but with different words.
>> [LAUGH] Ok.