4 ms·

So is [1], for example, misleading? [1] https://arxiv.org/abs/1406.2661 https://arxiv.org/abs/1406.2661

nl 10y ago
That paper doesn't mention game theory or the Nash equilibrium at all. Perhaps you mean [2], which does. However, the article seems to misinterpret this: the fact that that system approximates the Nash equilibrium should be expected. Any system (including humans) that performs well in those types of games will, almost by definition. [2] https://arxiv.org/pdf/1603.01121.pdf https://arxiv.org/pdf/1603.01121.pdf
- westoncb 10y ago
  It doesn't mention Nash equilibrium, but the whole approach they are discussing comes from the idea of pitting two networks against each other in a "minimax two-player game". "We propose a new framework for estimating generative models via an adversarial process, in which we simultaneously train two models ... This framework corresponds to a minimax two-player game." Edit: Regarding the paper you linked to. The fact that a Nash equilibrium is expected is an important part of why it's interesting to structure things this way: it's an optimization process guaranteed to stabilize (whereas it's problematic that other approaches will diverge). "When applied to Leduc poker, Neural Fictitious Self-Play (NFSP) approached a Nash equilibrium, whereas common reinforcement learning methods diverged"
  - nl 10y ago
    I think we agree? The articles claims (based on the paper I linked, and others) that: What we see in these 3 players are 3 different ways game theory plays in Deep Learning. (1) As a means of describing and analyzing new DL architectures. (2) As a way to construct a learning strategy and (3) A way to predict behavior of human participants. The last application can make your skin crawl! Of these claims, I think all are wrong. One can certainly make the case that it is interesting to measure the performance of a system compared to the Nash equilibrium (when possible), but the author seems to think that the designers of the system are somehow using game theory to design the system.
    - westoncb 10y ago
      They are in one of the cases pointed out, not the other two. The novel idea is to have two networks compete against each other in a two-player minimax game, developing progressively better strategies until something like Nash equilibrium is reached--at which point you have one well-trained classifying network and one well-trained generating network.
graycat 10y ago
I can't comment on "misleading" without reading, likely studying, the article you mentioned. There's a lot to game theory, e.g., one I omitted, differential game theory as in a missile chasing an airplane. But the likely most relevant, first cut, simple view is that each of the two players, Red and Blue, has a list of moves they can make. Then there is one (von Neumann case) or two (Nash case) payoff matrices. Then each of Red and Blue picks a move or a probability distribution of moves. The broad idea is to have and use a saddle point, maybe available only by making moves probabilistically in which case each of Red and Blue finds a probability distribution over the moves they can make and then picks a move according to their distribution and independent of everything else relevant. So, just as in the classic children's game paper-scissors-rock, each player picks a move in secret, and then both players show their moves at the same time. Each player seeks to maximize their long run expected gain. As can be shown easily from linear programming and its duality theory, for paper-scissors-rock the saddle point probability distributions are that each player picks each of the three moves paper, scissors, rock with probability 1/3rd. Of course, Red and Blue pick their moves independently and in secret. The matrix for paper-scissors-rock is 3 x 3. But the theory and the linear programming solution applies the same for positive integers m and n for m moves for Red, n moves for Blue, and a matrix m x n. All the components of the matrix are >= 0 and represent, say, a gain for Red and a loss for Blue. The classic von Neumann result shows how to get a saddle point from a payoff matrix with one row for each move for Red and one column for each move for Blue. Again, we can get this result from linear programming duality theory. The Nash result is a little more general. Sion's result is really just a case of max-min in mathematical programming, i.e., optimization. Yes, convexity can play an important role, but we would need to be clear on just what is convex. Convexity is central to Sion's result. Yes, the theory gets involved with some classic fixed point results. So, for machine learning, for a start, is the game even roughly in the sense of classic von Neumann and paper-scissors-rock? If so, what are the moves and, then, the payoffs? Getting that far, are we looking for two probability distributions? Then with the distributions, how do we apply those to the machine learning calculations, iterations, optimizations, improvements, etc.? Little questions like those. So, to start to apply game theory, let's start with a problem and formulate it as a problem in some appropriate part of game theory.

nl 10y ago

That paper doesn't mention game theory or the Nash equilibrium at all. Perhaps you mean [2], which does. However, the article seems to misinterpret this: the fact that that system approximates the Nash equilibrium should be expected. Any system (including humans) that performs well in those types of games will, almost by definition. [2] https://arxiv.org/pdf/1603.01121.pdf https://arxiv.org/pdf/1603.01121.pdf

westoncb 10y ago
It doesn't mention Nash equilibrium, but the whole approach they are discussing comes from the idea of pitting two networks against each other in a "minimax two-player game". "We propose a new framework for estimating generative models via an adversarial process, in which we simultaneously train two models ... This framework corresponds to a minimax two-player game." Edit: Regarding the paper you linked to. The fact that a Nash equilibrium is expected is an important part of why it's interesting to structure things this way: it's an optimization process guaranteed to stabilize (whereas it's problematic that other approaches will diverge). "When applied to Leduc poker, Neural Fictitious Self-Play (NFSP) approached a Nash equilibrium, whereas common reinforcement learning methods diverged"
- nl 10y ago
  I think we agree? The articles claims (based on the paper I linked, and others) that: What we see in these 3 players are 3 different ways game theory plays in Deep Learning. (1) As a means of describing and analyzing new DL architectures. (2) As a way to construct a learning strategy and (3) A way to predict behavior of human participants. The last application can make your skin crawl! Of these claims, I think all are wrong. One can certainly make the case that it is interesting to measure the performance of a system compared to the Nash equilibrium (when possible), but the author seems to think that the designers of the system are somehow using game theory to design the system.
  - westoncb 10y ago
    They are in one of the cases pointed out, not the other two. The novel idea is to have two networks compete against each other in a two-player minimax game, developing progressively better strategies until something like Nash equilibrium is reached--at which point you have one well-trained classifying network and one well-trained generating network.

graycat 10y ago

I can't comment on "misleading" without reading, likely studying, the article you mentioned. There's a lot to game theory, e.g., one I omitted, differential game theory as in a missile chasing an airplane. But the likely most relevant, first cut, simple view is that each of the two players, Red and Blue, has a list of moves they can make. Then there is one (von Neumann case) or two (Nash case) payoff matrices. Then each of Red and Blue picks a move or a probability distribution of moves. The broad idea is to have and use a saddle point, maybe available only by making moves probabilistically in which case each of Red and Blue finds a probability distribution over the moves they can make and then picks a move according to their distribution and independent of everything else relevant. So, just as in the classic children's game paper-scissors-rock, each player picks a move in secret, and then both players show their moves at the same time. Each player seeks to maximize their long run expected gain. As can be shown easily from linear programming and its duality theory, for paper-scissors-rock the saddle point probability distributions are that each player picks each of the three moves paper, scissors, rock with probability 1/3rd. Of course, Red and Blue pick their moves independently and in secret. The matrix for paper-scissors-rock is 3 x 3. But the theory and the linear programming solution applies the same for positive integers m and n for m moves for Red, n moves for Blue, and a matrix m x n. All the components of the matrix are >= 0 and represent, say, a gain for Red and a loss for Blue. The classic von Neumann result shows how to get a saddle point from a payoff matrix with one row for each move for Red and one column for each move for Blue. Again, we can get this result from linear programming duality theory. The Nash result is a little more general. Sion's result is really just a case of max-min in mathematical programming, i.e., optimization. Yes, convexity can play an important role, but we would need to be clear on just what is convex. Convexity is central to Sion's result. Yes, the theory gets involved with some classic fixed point results. So, for machine learning, for a start, is the game even roughly in the sense of classic von Neumann and paper-scissors-rock? If so, what are the moves and, then, the payoffs? Getting that far, are we looking for two probability distributions? Then with the distributions, how do we apply those to the machine learning calculations, iterations, optimizations, improvements, etc.? Little questions like those. So, to start to apply game theory, let's start with a problem and formulate it as a problem in some appropriate part of game theory.