FROM DEEP LEARNING TO DEEP DEDUCING: AUTOMATICALLY TRACKING DOWN NASH EQUILIB-
Year: 2018

Abstract:
Contrary to most reinforcement learning studies, which emphasize on training a deep neural network to approximate its output layer to certain strategies, this paper proposes a reversed method for reinforcement learning. We call this “Deep Deducing”. In short, after adequately training a deep neural network according to a strategy-environment-to-payoff table, then we initialize randomized strategy input and propagate the error between the actual output and the desired output back to the initially-randomized strategy input in the “input layer” of the trained deep neural network gradually to perform a task similar to “human deduction”. And we view the final strategy input in the “input layer” as the fittest strategy for a neural network when confronting the observed environment input from the world outside.

text: Contrary to most reinforcement learning studies, which emphasize on training a deep neural network to approximate its output layer to certain strategies, this paper proposes a reversed method for reinforcement learning. We call this “Deep Deducing”. In short, after adequately training a deep neural network according to a strategy-environment-to-payoff table, then we initialize randomized strategy input and propagate the error between the actual output and the desired output back to the initially-randomized strategy input in the “input layer” of the trained deep neural network gradually to perform a task similar to “human deduction”. And we view the final strategy input in the “input layer” as the fittest strategy for a neural network when confronting the observed environment input from the world outside.

heading: 1 INTRODUCTION
text: Contrary to most reinforcement learning studies (as in “Playing Atari with Deep Reinforcement Learning (Mnih et al., 2013).”), which emphasize on training a deep neural network to approximate its output layer to certain strategies and view the output layer of a deep neural network as its strategy in a certain natural environment, this paper provides a revolutionary way for reinforcement learning and a possible road toward general A.I..
Also, contrary to most Game Theory studies, which emphasize on the role of human experts to device smart mathematics algorithm (as in “When Machine Learning Meets AI and Game Theory (Agrawal & Jaiswal, 2012).”), this paper emphasizes on the role of machine and tends to show a bridge between A.I. territory and Game Theory.
The method is simple. In short, after training a deep neural network according to a strategyenvironment-to-payoff (input-to-output) table that records possible strategies and the environments along with the consequential payoffs, then we randomize the strategy input in the “input layer” and propagate the error between the actual output and the desired output back to the strategy input in the “input layer” of the same trained deep neural network recurrently to perform a task similar to “human deduction”. And we view the final strategy input in the “input layer” as the fittest strategy for a neural network confronting the observed environment input from the world outside. Since the information is sent back to the input layer in a reversed way like deduction in logic, we can call this “Deep Deducing”.
By using the same trick, we can force a neural network to automatically track down the Nash Equilibrium in a Simultaneous Discrete Game (which will be explained later). Since Nash Equilibrium is the optimal combination of strategies from which no player will be willing to deviate, and, for any player who deviates from NE, the player will be punished, the ability to find the Nash Equilibrium in advance in a randomized complex system indicates certain intelligence in an autonomous agent.

heading: 2 ALGORITHM: DEEP DEDUCING
text: To grasp the intuition behind Deep Deducing, we will first take a mosquito for example as shown in Figure 1.
Imagine the brain of a mosquito consists of a canonical deep feedforward neural network with only one input layer, one hidden layer, and one output layer. The input layer consists of strategy input and environment input. And the output layer consists of payoff out. A list of neurons in the strategy input records the strategies (denoted is) that the mosquito has adopted in response to certain environment information (denoted in), which environment information is also simultaneously recorded by the other list of the neurons in the environment input as well. Meanwhile the neurons in the payoff output also instantaneously record the payoff (denoted o) to the mosquito when it adopts a certain strategy is under a certain environment in. The concatenation of is and in is denoted as i.
The brain of the mosquito is trained to memorize the set of concatenations of strategy and environment (denoted I) as well as the set of their payoffs (denoted O). That is the set of the weights of the synapse (denoted W) are adjusted through (Stochastic Gradient Descent and Back Propagation):
Wt+1 ←Wt − α ∂
∂Wt E(o− o
′ ) (1)
where t is the current epoch, α is the learning rate, E is the error function (the loss or cost function, here we use squared error), and o ′ is the estimated payoff generated by current i and Wt. This is Deep Learning.
For illustration, the consequence of seeing human’s hand and choosing not to fly away is recorded. Of course the consequence is death, in which case the payoff to the mosquito is [0]. A cloud (of IoT) records the consequence (payoff) of every combination and trains the brain (the neural network) of the mosquito according to Figure 2 as below.
When the brain (the neural network) of the mosquito is adequately trained (by using Stochastic Gradient Descent) according to the table in Figure 2, upon seeing a human’s hand at presence, the brain (the neural network) of the mosquito must figure out and make deduction about what strategy it shall adopt in order to stay alive. In another word, how could the neural network figure out a strategy that, when put into the neural network along with environment input [1, 0, 0], can generate the payoff [1]?
The answer that Deep Deducing gives is rather simple – Just randomize the strategy input in the input layer of the trained neural network and let the neurons that represent the strategy input to adjust itself gradually to render the neural network to reach output [1] by propagating the error between the generated output and the desired output [1] back to the neurons in the strategy input itself for fixed epochs or as long as the generated output (of the adjusted strategy input obtained in the last epoch) does not adhere to [1] in a reasonable deviation.
That is, for a given in where 0 ≤ in ≤ 1, a set of trained Wtrained and a pre-fixed desired payoff od, 0 ≤ od ≤ 1, we first initialize a randomized strategy input is0 at time zero where 0 ≤ sigmoid(i s 0) ≤ 1. Then, by using Back Propagation, we let:
istrategyt+1 ← i strategy t − α
∂
∂istrategyt E(od − o
′ t) (2)
where t is the current epoch, α is the deducing rate (like learning rate), E is the error function, and o ′
t is the estimated payoff generated by current sigmoid(i s t ), i n and Wtrained. This is “Deep Deducing”. Please notice that, in, Wtrained and od are fixed, and the only thing that is changing is ist and o ′
t. And there is no Stochastic Gradient Descent since the desired payoff od is pre-fixed. By exploiting the existing trained neural network and the trick of Back Propagation, Deep Deducing forms a single, compounded and self-completed optimization problem for ist to reach the global minimum error, and therefore any kind of optimization skill, such as gradient-based particle swarm optimization, can be applied here as well. For simplicity, we will only use the most plain and modest gradient descent with only one starting point for ist to force the machine to track down Nash Equilibrium.
The whole process is illustrated in Figure 3.
Finally, after fixed epochs, according to the preliminary experimental result shown in Figure 3, the mosquito will obtain a strategy input that approximate [1, 0, 0] when argmaxed and one-hotted, which means the mosquito better just flies away. This final strategy information will later be sent to other parts of the mosquito to initiate the procedure of flying such as twitching wing tensors. We speculate that this simple three-layered deep neural network constitutes the very core of the mosquito’s decision-making mechanism.
Therefore, the Deep Deducing algorithm can be dissected into two phases. The first is the training or learning phase, and the second is the deduction phase. In the training or learning phase, the mosquito learns about the consequence in response to the combination of strategy and environment. In the deduction phase, the mosquito must figure out a strategy that can make it stay alive when human is at presence. The pseudo code of Deep Deducing for the learning phase is shown in Algorithm 1.
Algorithm 1 : training phase for the mosquito example 1: I← set of strategies and environments 2: O← set of corresponding payoffs 3: W0 ← initialize set of randomizedweights at time zero 4: α← learning rate 5: Nepochs ← number of epochs 6: Nsamples ← number of training samples 7: for t in [Nepochs] do 8: index← randomint(Nsamples) 9: i← I[index] 10: o← O[index] 11: o
′ ← feedforward(i,Wt) 12: Wt+1 ←Wt − α ∂∂WtE(o− o ′ ) 13: end for 14: Wtrained ←WNepochs
As for the deduction phase, the pseudo code can be shown in Algorithm 2.
Algorithm 2 : deduction phase for the mosquito example 1: istrategy0 ← initialize randomstrategy input at time zero 2: inature ← environment input 3: od ← initialize desired payoff output 4: α← deducing rate 5: Nepochs ← number of epochs 6: for t in [Nepochs] do 7: o ′ t ← feedforward(concatenate(sigmoid(istrategyt ), i
nature),Wtrained) 8: istrategyt+1 ← i
strategy t − α ∂∂istrategyt E(o d − o′t) 9: end for
10: optimal strategy ← onehot(argmax(sigmoid(istrategyNepochs )))
For the sake of simplicity, we will summarize the deduction phase in just one single sentence - Tuning the neurons in the strategy input to generate the desired output.

heading: 3 EXPERIMENT: TRACKING DOWN THE NASH EQUILIBRIUM IN A SIMULTANEOUS DISCRETE GAME
text: The first experiment here we will examine is simply the extension of the notion of the mosquito example stated above.
If we take the mosquito and the hand of human as the two players A and B in a Simultaneous Discrete Game in Game Theory. We can train a neural network according to the strategies-to-payoff
table for player A and B, then we can tune the neurons in the strategy input for player A to generate the desired output for player A, and vice versa. After we interchangeably and iteratively tune these two sets of neurons each represents the strategy input for player A and B, these two sets of neurons will converge to the Nash Equilibrium.
For example, in Simultaneous Discrete Game, we often see the strategies-to-payoff table for player A and B as shown in Table 1.
In the same manner, we first train a neural network according to the strategies-to-payoff table for player A and B as illustrated in Figure 4 below.
Second, since it is not a zero-sum game, we will tune (by one epoch) the neurons which represent the strategy input for player A to generate the desired payoff output for player A, namely [1, *] (where “*” stands for whatever the payoff for player B already is), and then we will tune (by one epoch) the neurons which represent the strategy input for player B to generate the desired output for player B, namely [*, 1] (where “*” stands for whatever the payoff for player A already is). We will keep this procedure for fair epochs as shown in Figure 5.
After fair epochs, as the preliminary experimental result in Figure 5, the neurons which represent the strategy input for player A will converge to [1, 0, 0] when argmaxed and one-hotted. And the neurons which represent the strategy of player B will also converge to [1, 0, 0] when argmaxed and one-hotted. This means that player A and player B will both adopt strategy [1, 0, 0], which is exactly the Nash Equilibrium in the strategies-to-payoff table in Table 1. The more formal experiment result is shown in Figure 9.
In Game Theory, this strategies-to-payoff table is Prisoner’s Dilemma, and strategy input [1, 0, 0] is the “betrayal” strategy. Deep Deducing automatically tracks down the Nash Equilibrium in Prisoner’s Dilemma which is that both players will betray each other (as in “Primer in Game Theory (Gibbons, 1994).”). Since Nash Equilibrium is the combination of strategies that no player is willing to deviate from , and, for any player who does not choose the NE strategy, he or she will be punished for his or her deviation (as in “Games of Strategy, Second Edition (Dixit & Skeath, 2004).”), the ability to track down NEs in a complex system in advance shows certain intelligence in a autonomous system. By this logic, since Deep Deducing, in the preliminary result, tracks down NE in the prisoner’s dilemma, there is certain intelligence in Deep Deducing. The pseudo code here
can also be dissected into two phases, namely the training or learning phase and the deduction phase. For the training phase, we simply duplicate the training phase in the mosquito example except that this time the environment input was replace by strategy input for player B, and the original strategy by strategy input for player A.

heading: 4 EXPERIMENT RESULTS
text: To thoroughly testify the functionality of Deep Deducing, we will first permute the payoffs in the prisoner dilemma in Table 1 to check if Deep Deducing with a set of trained synapses can track down Nash Equilibriums (NEs) in different locations with arbitrarily randomized starting points for strategy inputs for player A and B in each permuted table. Then we will generate 50 game tables with the size of 2x2 and 4x4, with randomly generated payoffs, to check if Deep Deducing with a set of trained synapses can track down the sole and the only NE in each table with different size. The program we set up guarantees there is only one NE in each table. Therefore, at a random guess, the chance to spot NE is 25 % in table 2x2 and 6.25 % in table 4x4.
Preliminary result shows that Deep Deducing can track down NE in different locations with arbitrarily randomized starting points for strategy inputs for player A and B. Also the result shows that Deep Deducing can track down NEs at the precision of nearly 100 % in tables 2x2, and 70 % in tables 4x4, which is obviously higher than random guess. The whole source code corresponding to each Figure can be seen at: https://github.com/AnonymousDeepDeducingCode/ DeepDeducing/tree/master, open for inspection.
The model here we will use is simply the traditional canonical 3-layered deep feedforward neural network with no modification. The squared error is used for error function (loss or cost function). To avoid noise in Back Propagation in Deep Deducing, the strategies are represented in digits. For example, strategies in table 2x2 can be represented by 1 digit, [0] or [1], since 1 digit is sufficient to represent all possible strategies for a player. Strategies in table 4x4 can be represented by 2 digits, [0, 0], [1, 0], [0, 1] and [1, 1], for each player. Also, the payoff for each player in each table is represented by digits as well. For example, payoff 3 is represented by [1, 1, 1, 0, 0, 0, 0, 0, 0, 0] with possible maximum payoff 10. The sequence is irrelevant and can be changed at user’s will because the volume of error sent back to the input layer is all that matters. Here, we set maximum payoff as well as the optimal desired payoffs to 10 for each player. The final strategy adopted by a player depends on the closest range of its final strategy input to [0] or [1]. For example, if the strategy input for player A arrives at [0.13] in the end, player A will adopt strategy [0]. If the strategy input for player B arrives at [0.653] in the end, player B will adopt strategy [1].
The size of the 3-layered neural network is set to be n*h*m, where n is the sum of the size of the strategy inputs for A and B in each table, h is the size of hidden layer, and m is the sum of the size of the neurons that represent possible maximum payoffs for player A and B in each table. Therefore, n*h*m = (1+1)*h*(10+10) in table 2x2, and n*h*m = (2+2)*h*(10+10) in table 4x4.
For the first test, the prisoner’s dilemma in Table 1 is permuted into 4 different tables as below in Table 2.
With a 3-layered deep feedforward neural network with size (1+1)*30*(10+10) with learning and deducing rate at 0.01 and learning and deducing epochs at 10000, the trajectories of arbitrarily randomized starting points for strategy inputs for player A and B in each corresponding table in Table 2 can be shown in the left part of Figure 15.
As we can see in the left part of Figure 15, regardless of the initially randomized starting points (denoted red dots) for the strategy inputs, the strategy inputs for player A and B converge to NE (denoted blue dots) in each table under Deep Deducing.
If We further fix the strategy input for player A to [0], and tune only the strategy input for player B, we will obtain the right part of Figure 15. As we can see in the right part of Figure 15, the strategy inputs of player B still converge to the optimal (and conditional) strategies for player B in Table 2 (denoted blue dots), regardless of its initially randomized starting positions (denoted red dots).
Since a canonical deep neural network use sigmoid as activation function, when the training of the neural network is sufficient, a little deviation in the input layer does not generally affect the output of the neural network as a whole, which renders the optimization geometry for the strategy inputs rather smooth and further lessens the chance of getting stuck at local minimum for gradient descent and other types of optimization skills. If we take sum of the squared errors (odB − o′B) 2 as axis z, we can obtain Figure 17.
We can see the smoothness of geometry for the strategy inputs increases as the neural network learns more about a game table and further lessens the chance of getting stuck at local minimum for gradient descent and other types of optimization skills (see Figure 9). This explains why Deep Deducing can be attached to Deep Learning.
However, how did the strategy inputs for player A and B automatically track down NE in the left part of Figure 15? This paper proposes two possible explanations. The first possible and more vivid explanation is that, imagine strategy inputs for A and B are two small ants in two different mountain sides, they both want to climb to the lowest points of their own mountains, however they overlap each other (phantom space) and wherever ant A moves, ant B will be carried to the same direction due to the this phantom effect, and vice versa. If ant A moves first and then ant B moves afterwards repeatedly, in the end, ant A and B will pull each other to a certain point (as the blue rectangles in Figure 8), and this point is never the lowest point of their own mountain side. This can be shown in Figure 8.
The second possible explanation is that, In Kakutani’s fixed point theorem, a topology space kept mapped into itself (if closed, continuous) will converge to a point. This point is the fixed point under every mapping. By Nash theorem, if the mapping is the pursuit of the best interest of each player, this point will be the Nash Equilibrium (as in “Introduction to Topology: Pure and Applied (Adams & Franzosa, 2008).”). In Figure 15, we can observe that the trajectory of strategy inputs for player A and B under Deep Deducing algorithm converge to a certain point regardless of their initial different position. Therefore, by Kakutani’s fixed point theorem, there is a fixed point under every mapping. Further by Nash theorem, the fixed point shall also be the Nash Equilibrium since Deep Deducing mimics the rationale of human player in the pursuit of their own interest. Therefore, Deep Deducing tracks down the fixed point, and, therefore tracks down the Nash Equilibrium.
For the second test to track down NEs in 50 randomly generated game tables, we instead use a 3-layered deep feedforward neural network with size (1+1)*15*(10+10) for table 2x2 and (2+2)*15*(10+10) for table 4x4 with learning and deducing rate at 0.1 and deducing epochs at 5000. The success rate to track down NEs in each table type (2x2 and 4x4) varies with learning or training epochs. The final result is shown in Figure 9.
As we can see, Deep Deducing is almost 100 % accurate in tables of size 2x2, however the precision in tables of size 4x4 drops to 70%. This is because the learning process only lessens the chance of getting stuck at local minimum, we are only using plain and modest gradient descent with Back Propagation, and the strategy inputs for player A and B might get stuck at ”common” local minimums in 4x4 tables, which minimum is the common minimum in the error surface of player A and B respectively (so we call it ”common”) in which case we cannot expect ant A and B to pull each other out of their local minimums. To solve this problem, we will apply a simplified gradient-based particle swarm optimization and transform Equation 2 into Equation 3a and 3b for player A and 4a and 4a for player B:
mAt ← i A t − i A t−1 (3a)
iAt+1 ← i A t − α
∂
∂iAt E(odA − o
′A t ) + αm A t + α(i Aoptimal t − i A t ) (3b)
mBt ← i B t − i B t−1 (4a)
iBt+1 ← i B t − α
∂
∂iBt E(odB − o
′B t ) + αm B t + α(i Boptimal t − i B t ) (4b)
where iAoptimalt is the optimal solution in the strategy swarm for player A at time t, and vice versa. Since Deep Deducing exploits Back Propagation as the gradient descent method, ∂
∂iBt E(odB − o′Bt )
can serve as a gradient for swarm optimization.
We initiate only seven particles in each strategy swarm A and B separately. The deducing epoch is set to be 100*100, where 100 is the iteration inside each swarm and 100 between swarm A and swarm B.
In the beginning of iteration inside a swarm, we keep the leader obtained from the last iteration and renew the rest of swarm (randomly) as well as all the momentum. In the mid of the iteration inside the swarm, the particles will learn from each other and improve their positions. And in end of the swarm iteration, the best strategy input will survive and be elected as the new leader and the rest of the swarm will be killed. This leader of swarm A will become a variable to consider with, for the iteration inside swarm B. The same process go through the strategy swarm of A and B. We can simply imagine this process as the democratic election system and international competition system. By doing so, we exploit the benefit of gradient-based particle swarm optimization to escape local minimums while keeping the swarm as resilient as possible by introducing new particles to compete with (and learn from) the old leader, killing less efficient particles in the swarm, and then raising a possible new leader to confront the enemy swarm. We will then obtain Figure 10 as the renewed accuracy for 4x4 tables:
As we can see in Figure 10, the accuracy improves to 80 % for 4x4 tables . Deep Deducing tracks down NEs despite the fact that there is only one uncoupled algorithm.
For more interesting result, please consult Appendix. From evidence above (including Appendix), we can conclude that there is certain intelligence in Deep Deducing.

heading: 5 CONCLUSIONS
text: The experiments shown here are not all inclusive, but the preliminary experiments indicate that Deep Deducing can perform the similar task to human deduction by simply propagating error further back to the input layer. In this sense, the input layer of a neural network does not only serve as an information receiver (as we always envisage) but also an information sender, which information is further sent to other parts of the body such as muscles or even other neural networks.
The whole traditional deep neural network can be viewed as a gigantic memory or knowledge reservoir of strategy, environment and payoff. In a word, a simple traditional deep neural network itself is already a memory pool, ready to have its information be extracted for later usage, and Recurrent Neural Network just augmented this function by allowing variable inputs to be considered. This finding might implement the notion of ”memory” as we envisaged (as in “Deep Learning (LeCun et al., 2015).”).
By back-propagating error back to the input layer, a traditional deep neural network forms an internal information exchange route similar to the internal information exchange in Hopfield Neural Network. The only difference is that the former uses Back Propagation algorithm while the latter exploits the notion of thermodynamics (Hopfield Neural Network can be viewed as a Restricted Boltzmann Machine with visible layers mapping to itself in supervised learning, while a Boltzmann Machine can be viewed as a Hopfield Neural Network with hidden layers and simulated annealing, the latter see “Connectionist architectures for Artificial Intelligence (Fahlman & Hinton, 1987).”). This internal information from other pathways does not only train the synapses itself as we always envisage (as in “How neural networks learn from experience (Hinton, 1992).”), but also the source (neurons in the input layer) as well.
There are pros and cons to Deep Deducing. First, Deep Deducing is highly intuitive and can be easily coded. Second, Deep Deducing can be seamlessly combined with other types of neural networks as long as the back-propagation algorithm or back-propagation-like algorithm is compatible with the latter. However, the downside is that Deep Deducing requires heavy epochs as well as training time on the training or learning phase in order to achieve high precision in the deduction phase in some application.
There is still an abundant discovery that we have made, and we are still making progress.

Review summaries:
The paper proposes a method of searching for a Nash equilibrium strategy in games where the strategy-to-payoff mapping is defined by a neural network. The idea is to perform gradient optimization of the payoff w.r.t. the strategy. Preliminary results on tic-tac-toe and variations of the prisoner’s dilemma task are presented. The paper has an interesting idea at the core. However, it is poorly written, does not properly discuss the related works and does not present a convincing method or experimental results.