PATROL: Provable Defense against Adversarial Policy in Two-player Games

Recent advances in deep reinforcement learning (DRL) takes artificial intelligence to the next level, from making individual decisions to accomplishing sophisticated tasks via sequential decision makings, such as defeating world-class human players in various games and making real-time trading decisions in stock markets. Following these achievements, we have recently witnessed a new attack specifically designed against DRL. Recent research shows by learning and controlling an adversarial agent/policy, an attacker could quickly discover a victim agent's weaknesses and thus force it to fail its task. Due to differences in the threat model, most existing defenses proposed for deep neural networks (DNN) cannot be migrated to train robust policies against adversarial policy attacks. In this work, we draw insights from classical game theory and propose the first provable defense against such attacks in two-player competitive games. Technically, we first model the robust policy training problem as finding the nash equilibrium (NE) point in the entire policy space. Then, we design a novel policy training method to search for the NE point in complicated DRL tasks. Finally, we theoretically prove that our proposed method could guarantee the lowerbound performance of the trained agents against arbitrary adversarial policy attacks. Through extensive evaluations, we demonstrate that our method significantly outperforms existing policy training methods in adversarial robustness and performance in non-adversarial settings. NE states that, for each player i, π i * is its optimal policy when its opponent plays the policy π -i * . This also can be expressed as π i * is the i-player's best response to its opponent's policy Obs. Obs. (a) Two-player game. Environment Policy under training Action Action Copy player 1's policy to player 2 The right half of this inequality states that π 2 * is the policy that forces π 1 * to receive the lowest long-term reward, indicating π 1 * is playing against its strongest opponent and thus is in its worst-case scenario. The left half of Eqn. (3) then shows that π 1 * is the policy that receives the highest long-term reward against π 2 * , meaning π 1 * achieves the optimal performance in the worst-case scenario. As such, by playing π 1 * for the 1st player, we could guarantee the player's optimal worst-case performance as For the 2nd player, we could derive a similar inequality: showing that π 2 * is the robust policy for the 2nd player with the optimal worst-case performance of V 2 (π 1 * , π 2 * ). To further explain why policies at the NE point are robust policies, we again take for example the real-world game scenario mentioned in Section 3. Suppose the game vendor releases π 1 * as the default policy for the 1st player. In our threat model, an attacker will then try to train a policy π 2 to defeat π 1 * . According to Eqn. (3), the best policy the attacker can search for is π 2 * . In other words, the attacker cannot find a stronger opponent for π 1 * other than π 2 * , showing that π 1 * 's worst performance is bounded and thus is robust against adversarial attacks. Similarly, π 2 * is the robust policy for the 2nd player. As such, by finding a NE point with a joint policy (π 1 * , π 2 * ), we could achieve a robust policy for both players in the game. Based on the analysis above, we can define a pair of policies (π i , π -i ) as robust policies if they satisfy the condition in Eqn. (3), and the corresponding lower bound performance for each player is V i (π i , π -i ). Theoretical foundation for training robust policies. Through the analysis above, we transform the problem of training a robust policy into searching for a NE point in a two-player zero-sum game. To learn a NE point, we seek the theoretical foundation from classical game theory and find the following theorem to guide our training algorithm design. Similarly, solving the inner optimization max π 1V 1 (π 1 , π 2 ) of the Eqn. (5) gives h(π 2 ), ) is the solution of the outer optimization of the Eqn. ( 5 ), we have So far, we have the following inequalities where the joint policy (π 1 * , g(π 1 * )) gives the maximin value of the long-term reward and the joint policy (h(π 2 * ), π 2 * ) gives the minimax value. If we could achieve that π 1 * = h(π 2 * ) and π 2 * = g(π 1 * ), the joint policy (π 1 * , π 2 * ) gives the maximin and minimax value at the same time, i.e., satisfying the conditions in Corollary 1. Besides, when π 1 * = h(π 2 * ) and π 2 * = g(π 1 * ), Eqn. ( 6 ) is equivalent to Eqn. (3), indicating (π 1 * , π 2 * ) is the policy of a NE point. As such, if a joint policy satisfies the conditions in Eqn. (5) and Eqn. (4), it reaches a NE point and thus is a set of robust policies for both players. * , π 2 * ) obtained by our proposed method, we prove that (π 1 * , π 2 * ) asymptotically converges to a NE point, such that * , π 2 ) + ε with ε → 0. Recall that the true value function is approximated with a neural ne