Anti-jamming communication without pre-shared secrets has gained increasing research interest recently and is commonly tackled by utilizing the technique of uncoordinated frequency hopping (UFH). Existing researches, however, are almost all based on ad hoc designs of frequency hopping strategies, mainly due to lack of theoretical foundations for scheme performance evaluation. To fill this gap, in this paper we introduce the online optimization theory into our solution and, for the first time, make the thorough quantitative performance characterization possible for UFH-based anti-jamming communications. Specifically, we formulate the UFH-based anti-jamming communication as a non-stochastic multi-armed bandit (MAB) problem and propose an online learning-based UFH algorithm achieving asymptotic optimum. To reduce the time and space complexity, we further develop an enhanced algorithm exploiting the internal structure of strategy selection process. We analytically prove the optimality of the proposed algorithms under various message coding scenarios. An extensive simulation study is conducted to validate our theoretical analysis and show that the learning-based UFH algorithms are resilient against both oblivious and adaptive jamming attacks.