Reinforcement Learning and Optimization in Large Action Spaces under Limited Feedback

Overview

Modern AI systems increasingly operate in environments where decision spaces are combinatorial, high-dimensional, or exponentially large, while feedback is sparse, global, or costly to obtain. In such regimes, classical methods become computationally prohibitive, as optimal decisions require searching intractable spaces and each evaluation provides limited information.

We first study combinatorial multi-armed bandits, where the number of actions grows exponentially. By exploiting submodularity in expectation, we introduce randomized greedy and stochastic-greedy algorithms that avoid exhaustive exploration while achieving provable sublinear regret under full-bandit feedback. These ideas extend to an offline-to-online learning framework in both single-agent and federated multi-agent settings, enabling scalable distributed learning with limited communication.

We then address global optimization of black-box reward functions with expensive evaluations and unknown smoothness. We develop adaptive Lipschitz optimization methods that eliminate provably suboptimal regions via consistency-based filtering, significantly improving query efficiency without explicit smoothness estimation.

Finally, we consider value-based reinforcement learning with large discrete action spaces. We propose stochastic Q-learning methods that replace exhaustive maximization with randomized sampling and memory mechanisms, reducing computational complexity from linear to logarithmic in the action space while preserving convergence guarantees.

Across these settings, a unifying principle emerges: scalability in large decision spaces arises from combining structural assumptions, randomized approximation, and uncertainty-aware exploration.