Efficient Reinforcement Learning under Structures: From Single-Agent to Multi-Agent to the Era of LLMs

Reinforcement learning (RL) provides a powerful framework for sequential decision-making and has enabled a wide range of high-impact applications. Real-world RL problems rarely appear in their ``vanilla'' form: they come with rich, problem-dependent structures that either imposes additional constraints on algorithm design or offers properties that can be exploited to improve learning efficiency. The central theme of the RL algorithm design is to identify those structures and develop specialized techniques for both statistical and practical efficiency. In this thesis, we systematically study several influential families of structured RL problems and develop principled algorithms with rigorous theoretical guarantees. In the first part, we focus on single-agent RL and analyze two prevalent structural features. The first is the availability of auxiliary information in the form of approximate value or model (e.g. simulator). We develop the Doubly-Robust Policy Gradients estimator that integrate such side information with advanced variance-reduction techniques, providing more sample-efficient and stable policy optimization. The second feature is the deployment constraints---limitations on how frequently one may update or deploy new policies---which are ubiquitous in user-facing and safety-critical applications. This motivates the study of deployment-efficient RL, where the deployment cost is treated as a first-class resource. We derive sharp information-theoretic lower bounds on the number of policy deployments required for near-optimal performance and design algorithms that achieve near-optimal deployment efficiency. In the second part, we turn to multi-agent RL, where multiple decision-makers interact strategically. We first consider large-population systems modeled as Mean-Field Games (MFGs), and show how to exploit the symmetric structure for efficient Nash Equilibrium learning, even when the number of agents is extremely large. Next, we study incentive design for autonomous agents following structured learning dynamics. We identify a simple yet practical ``Markovian'' condition---where agents' policy updates depend only on their current policy and observed rewards---under which learning effective and efficient incentive (or ``steering'') strategies is tractable, even when the principal has no explicit model of the agents' internal learning rules. Finally, we investigate RL for Large Language Models (LLMs) post-training, with a focus on transfer learning in Reinforcement Learning from Human Feedback (RLHF). We analyze the special structural properties induced by the KL-regularized RLHF objective, which uncover new connections between policy coverability and its suboptimality gap. Built on these insights, we propose transfer-learning algorithms with provable improvements over learning from scratch, and demonstrate their empirical benefits through experiments.