Adversarial imitation learning (AIL), a prominent approach in imitation learning, has achieved significant practical success powered by neural network approximation. However, existing theoretical analyses of AIL are primarily confined to simplified settings-such as tabular and linear function approximation-and involve complex algorithmic designs that impede practical implementation. This creates a substantial gap between theory and practice. This paper bridges this gap by exploring the theoretical underpinnings of online AIL with general function approximation. We introduce a novel framework called optimization-based AIL (OPT-AIL), which performs online optimization for reward learning coupled with optimism-regularized optimization for policy learning. Within this framework, we develop two concrete methods: model-free OPT-AIL and model-based OPT-AIL. Our theoretical analysis demonstrates that both variants achieve polynomial expert sample complexity and interaction complexity for learning near-expert policies. To the best of our knowledge, they represent the first provably efficient AIL methods under general function approximation. From a practical standpoint, OPT-AIL requires only the approximate optimization of two objectives, thereby facilitating practical implementation. Empirical studies demonstrate that OPT-AIL outperforms previous state-of-the-art deep AIL methods across several challenging tasks.

Abstract The SM4 block cipher is a Chinese national standard and an ISO international standard. Since white-box cryptography has many real-life applications nowadays, a few white-box implementations of SM4 has been proposed, among which a type of constructions is dominated, which uses a linear or affine diagonal block encoding to protect the original three 32-bit branches entering a round function and uses its inverse as the input encoding to the S-box layer. In this paper, we analyse the security of this type of constructions against Lepoint et al.’s collision-based attack method. Our experiment under a small fraction of (encodings, round key) combinations shows that the rank of the concerned linear system is much less than the number of the involved unknowns, meaning these white-box SM4 implementations should resist Lepoint et al.’s method, but we leave it as an open problem whether there are such encodings that the rank of the corresponding linear system is slightly less than the number of the involved unknowns, in which scenario Lepoint et al.’s method may be used to recover a round key for the case with linear encodings and to remove most white-box operations until mainly some Boolean masks for the case with affine encodings.