Combinatorial Subset Selection in Reinforcement Learning

This direction is merged into another direction: combinatorial action space explosion (combinatorial action space complexity). Its last version stays readable and citable here.

Version 1 of 134 papers35 conceptsfrozen 2026-10-04

In many real-world decision problems, an agent does not simply choose one action from a list; it must select a subset of items. Whether it is a sports coach picking a starting lineup, a recommendation engine selecting a "shelf" of products, or a network controller choosing subcarriers, the action space is combinatorial. If you have 100 items and must pick 10, there are over 17 trillion possible actions.

Standard Reinforcement Learning (RL) and Multi-Armed Bandit (MAB) algorithms treat each action as an independent entity. In a combinatorial setting, this leads to an exponential explosion that makes exploration statistically and computationally impossible. Recent research has focused on bypassing this "curse of dimensionality" by exploiting the underlying structure of sets.

Decomposing the Action Space

The most direct way to handle trillions of possible subsets is to stop treating the subset as a single "choice" and instead view it as a sequence of smaller decisions. HyungSeok Song and colleagues in Solving Continual Combinatorial Selection via Deep Reinforcement Learning propose "Select-MDPs." Instead of picking $K$ items at once, the agent picks one item at a time over $K$ micro-steps. By using weight-sharing and exploiting mathematical symmetries, the agent learns the value of items rather than the value of combinations, allowing it to generalize to sets it has never seen before.

Similarly, in the context of 5G/6G resource allocation, Mohsen Amiri and V. Venktesh introduced Champion–Challenger Sampling (CCS) in Challenger-Based Combinatorial Bandits for Subcarrier Selection in OFDM Systems. Rather than evaluating all combinations, CCS maintains a rotating shortlist of promising candidates, achieving massive speedups by focusing exploration on a small, high-performing neighborhood of the action space.

Exploiting Reward Structure

If the reward of a subset is simply the sum of the rewards of its parts, the problem is easy. However, real-world rewards are often non-linear or submodular (exhibiting diminishing returns).

Mridul Agarwal and Vaneet Aggarwal address non-linear feedback in Stochastic Top-K Subset Bandits with Linear Space and Non-Linear Feedback. Their CMAB-SM algorithm uses a "Sort-Merge" strategy. By leveraging stochastic dominance, they can identify the best items without ever having to explicitly calculate the value of every possible combination.

For scenarios where adding more items provides less and less value (submodularity), Alexander Rakhlin and Dean P. Foster developed algorithms that randomize exploration only around local optima in On Submodular Contextual Bandits. This allows the agent to achieve sublinear regret even when the total number of subsets is astronomical.

Theoretical Efficiency and Perturbations

To provide mathematical guarantees in these complex spaces, researchers often look to "perturbation" methods. In Follow-the-Perturbed-Leader Nearly Achieves Best-of-Both-Worlds for the m-Set Semi-Bandit Problems, Jingxin Zhan and Zhihua Zhang use Fréchet perturbations to stabilize the selection process. This technique allows the algorithm to adapt to both predictable (stochastic) and unpredictable (adversarial) environments without needing to track the probability of every possible subset.

Another approach is the use of Thompson Sampling (TS). While TS is popular for its empirical performance, Siwei Wang and Wei Chen showed in Thompson Sampling for Combinatorial Semi-Bandits that its success in combinatorial settings depends heavily on having an efficient "optimization oracle"—a tool that can quickly find the best set given current estimates—to avoid the exponential search.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_combinatorial_subset_selection_in_reinfo_7c67a166,
  title = {Combinatorial Subset Selection in Reinforcement Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/combinatorial-subset-selection-in-reinforcement-learning/rdr_7c67a1667cf140d2b165c8ab77945baf},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_combinatorial_subset_selection_in_reinfo_7c67a166_v1,
  title = {Combinatorial Subset Selection in Reinforcement Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/combinatorial-subset-selection-in-reinforcement-learning/rdr_7c67a1667cf140d2b165c8ab77945baf/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}