Sequential decision-making studies how an agent learns to interact optimally with its environment over time. This thesis investigates the interplay between two requirements for such an agent: statistical efficiency, which concerns how effectively the agent uses available information, and computational efficiency, which concerns whether the resulting procedure can be implemented in practice. It identifies statistically efficient procedures, exposes the computational obstacles they may create, and uncovers structures that make them computationally feasible.

The first part of the thesis characterizes statistical efficiency through large deviations theory. In particular, the first chapter considers offline reinforcement learning, in which we construct the least-conservative reward estimator subject to a prescribed exponential decay rate for the probability of overestimation. In the second chapter, we establish exponential decay rates for the probability that the iterates of policy-gradient algorithms are inaccurate. The second part views statistical efficiency as the ability to adapt optimally to diverse environments. The third chapter studies multi-armed bandits, where we develop an adaptive perturbation-based algorithm that achieves optimal regret across stochastic and adversarial regimes while remaining computationally efficient. We extend such ideas to contextual combinatorial bandits in the fourth chapter. The third part confronts the computational cost of statistically efficient uncertainty modeling in Markov decision processes (MDPs). The fifth chapter studies robust MDPs with uncertainty sets that preserve dependencies among transition probabilities emanating from different states and are therefore computationally challenging; nevertheless, a gradient-dominance structure enables a globally convergent algorithm. In the sixth chapter, we consider continuous-state robust MDPs and exploit a mixture structure to develop a tractable algorithm with optimal sample complexity.

The thesis therefore identifies problem-specific alignments and tensions between statistical and computational efficiency. On the one hand, statistical efficiency may require adapting to structures that simpler models ignore, yet the same features can render the method intractable. On the other hand, gradient dominance and mixture structures enable computational benefits without sacrificing statistical efficiency. When no comparable structure is available, the question becomes how much statistical performance must be conceded for tractability. This perspective points toward a theory that identifies the optimal trade-off between information-theoretic and computational limits.