  We develop a general theory to optimize the frequentist regret for sequential
learning problems, where efficient bandit and reinforcement learning algorithms
can be derived from unified Bayesian principles. We propose a novel
optimization approach to generate "algorithmic beliefs" at each round, and use
Bayesian posteriors to make decisions. The optimization objective to create
"algorithmic beliefs," which we term "Algorithmic Information Ratio,"
represents an intrinsic complexity measure that effectively characterizes the
frequentist regret of any algorithm. To the best of our knowledge, this is the
first systematical approach to make Bayesian-type algorithms prior-free and
applicable to adversarial settings, in a generic and optimal manner. Moreover,
the algorithms are simple and often efficient to implement. As a major
application, we present a novel algorithm for multi-armed bandits that achieves
the "best-of-all-worlds" empirical performance in the stochastic, adversarial,
and non-stationary environments. And we illustrate how these principles can be
used in linear bandits, bandit convex optimization, and reinforcement learning.
