Bandit Guided Strategy Selection in High Dimensional Spaces

14 concepts16 papers2 proposals

Multi-armed bandit (MAB) algorithms are traditionally used to solve the exploration-exploitation dilemma at the lowest level of execution—deciding which ad to display, which path to take in a grid world, or which action to choose in a reinforcement learning state. However, when navigating high-dimensional, discrete, or infinite search spaces, optimizing at the individual action level causes a combinatorial explosion.

A powerful paradigm shift addresses this challenge: elevating multi-armed bandits from low-level action selectors to high-level strategy selectors. By treating entire macro-level candidates—such as symbolic formulas, algorithmic variants, code transformations, or database configurations—as discrete "arms" in a bandit framework, systems can use mathematically grounded exploration-exploitation mechanisms to dynamically allocate a computational or simulation budget. This approach allows algorithms to rapidly prune underperforming strategies based on noisy, empirical feedback while focusing resources on exploiting the most promising configurations.

Automating Algorithm and Policy Discovery

Instead of relying on human intuition to manually tune heuristics or design control policies, researchers can generate a massive space of symbolic formulas or algorithmic variants and let a bandit framework navigate them.

For example, in Monte Carlo Search Algorithm Discovery for Single-Player Games, a formal grammar automatically generates a vast space of candidate search algorithms. By framing the selection of the optimal algorithm as a pure-exploration multi-armed bandit problem, the framework dynamically allocates its computational budget, rapidly discarding underperforming candidates and focusing its evaluation on discovering novel, task-tailored search strategies.

This concept is highly effective for discovering interpretable control strategies. Raphael Fonteneau in Learning Exploration/Exploitation Strategies for Single Trajectory Reinforcement Learning applies this framing to search through a space of "formula-based" exploration-exploitation strategies. Each candidate formula acts as an arm; the agent samples environments, executes episodes using that formula, and uses an Upper Confidence Bound (UCB) approach to identify the best-performing strategies under tight computational constraints.

[ High-Dimensional Strategy Space ]
       /           |           \
  [Formula A]  [Formula B]  [Formula C]   <-- Treated as "Arms"
       \           |           /
        v          v          v
   [  Bandit Selection Mechanism  ]       <-- Allocates simulation budget via UCB
                   |
                   v
       [ High-Performing Strategy ]

This methodology is extended by Louis Wehenkel et al. in Policy Search in a Space of Simple Closed-form Formulas: Towards Interpretability of Reinforcement Learning. They frame direct search over a large discrete space of human-readable mathematical formulas as a bandit problem, where an upper confidence bound algorithm balances the verification of unverified formulas with the exploitation of high-performing candidates. This allows the discovery of compact, interpretable policies that can outperform deep look-ahead planning.

Even the design of reward functions can be automated through this lens. Ning Gao et al. in RF-Agent: Automated Reward Function Design via Language Agent Tree Search frame reward function design as a sequential decision-making task managed by Monte Carlo Tree Search (MCTS), enabling systematic exploration and exploitation of the reward space while allowing the system to backtrack from suboptimal local minima.

Pruning Complex Search Trees and Games

Tree search algorithms inherently rely on balancing exploration and exploitation. As noted by Michele Sebag in A tour of machine learning: An AI perspective, MCTS scales sequential decision-making precisely by integrating multi-armed bandit algorithms into tree-structured search spaces, balancing unvisited action paths with known high-reward trajectories during lookahead planning. This mechanism is crucial for physical tasks; for instance, Victor Dh ́Edin et al. in Diffusion-based learning of contact plans for agile locomotion utilize MCTS to explore a vast space of potential footstep sequences for robotic locomotion, balancing the exploration of new paths with the exploitation of promising ones.

When environments become nondeterministic or adversarial, standard motion planning often fails due to the sheer size of the game tree. To overcome this, Qi Heng Ho et al. in Sampling-based Reactive Synthesis for Nondeterministic Hybrid Systems apply a multi-armed bandit algorithm at the strategy level to navigate a two-player game tree. This mechanism prioritizes the expansion of promising branches likely to satisfy mission requirements while continuing to investigate less-explored regions of the state space.

The authors reinforce this intuition in Poster Abstract: Sampling-based Approach to Robust STL Synthesis for Complex Systems under Uncertainty, demonstrating that applying multi-armed bandit logic to strategy selection within an AND/OR search tree manages the exploration-exploitation trade-off in infinite game spaces. By treating control selection at each node as a bandit problem, the search is biased toward winning strategies without permanently ignoring valid alternative paths, enabling effective pruning of otherwise intractable trees.

Optimizing Systems and Heuristics

Systems engineering and combinatorial optimization frequently rely on hand-tuned heuristics. Modeling these choices as a strategy-level bandit allows software to self-tune based on real-world performance rather than flawed theoretical models.

In combinatorial optimization, Elias B. Khalil et al. in Machine Learning for Integer Programming model the selection between different branching variables or heuristic rules as a multi-armed bandit problem. By treating each heuristic option as an arm, the algorithm learns which choices yield the best performance within a specific search tree while occasionally trying less-used options to discover better strategies. Similarly, for data clustering, S.B. Muravyov et al. in Automatic hyperparameter optimization for clustering algorithms with reinforcement learning use selection strategies like Softmax or UCB to navigate the trade-off between exploring entirely different clustering algorithms (such as k-Means vs. DBSCAN) and exploiting known high-performers within a constrained search space.

This paradigm extends directly to low-level hardware and database optimization:

Macro Exploration in Reinforcement Learning and Language Models

Instead of exploring random, low-level actions, agents can explore random high-level behaviors, skills, or conversational framing tactics.

In hierarchical reinforcement learning, Siyuan Li in Deep Reinforcement Learning with Hierarchical Structures treats the selection of pre-trained low-level skills as a multi-armed bandit problem using upper confidence bounds. This approach balances the exploration of new skills with the exploitation of known effective ones far more efficiently than standard soft-max action selection methods.

Taking this further, Ofir Nabati et al. in Representation-Driven Reinforcement Learning manage exploration at the level of global strategies by embedding entire candidate policies into a latent linear space. By treating policy selection as a contextual bandit problem in this learned space, the system applies uncertainty-aware selection algorithms to balance the refinement of known strategies with the discovery of novel behaviors in complex, sparse-reward environments.

Standard RL:     [State] ---> [Action 1] or [Action 2] or [Action 3]
                                   (High variance, slow convergence)

Strategy Bandit: [State] ---> [Policy A (Full Skill)] or [Policy B (Full Skill)]
                                   (Regulated via Contextual Bandit Space)

Even adversarial interactions with Large Language Models can be optimized using this macro-framing. Aditya Ramesh et al. in EFFICIENT JAILBREAK ATTACK SEQUENCES ON LARGE LANGUAGE MODELS VIA MULTI-ARMED BANDIT-BASED CONTEXT SWITCHING model conversational tactic selection as a multi-armed bandit problem. By utilizing an epsilon-greedy algorithm, the framework automates the discovery of effective conversational frameworks, balancing the exploration of diverse framing strategies with the exploitation of those that have historically succeeded in bypassing safety constraints.

Finally, in high-dimensional and noisy simulation environments like epidemiology, Oliver Bent et al. in Novel Exploration Techniques (NETs) for Malaria Policy Interventions frame policy selection as a stochastic multi-armed bandit problem. Treating each complex intervention configuration as an independent arm allows an agent to balance the exploration of new strategies with the exploitation of known high-performing ones, ultimately identifying cost-effective policy mixes that challenge traditional expert consensus.

Why Strategy-Level Selection Works

The core reason strategy-level bandit selection succeeds across these diverse domains is its ability to decouple candidate generation from candidate evaluation.

In traditional optimization, an algorithm must understand the internal mechanics of the search space to make progress. By contrast, strategy-level bandit selection treats candidate strategies as black boxes. The bandit algorithm does not need to know why a specific GPU kernel transformation, database index, or symbolic formula works; it only needs to observe its empirical performance and track the associated uncertainty.

By using mathematically rigorous allocation rules (like UCB or epsilon-greedy) at the macro level, the system transforms an intractable, high-dimensional search space into a structured sequential decision-making problem. This ensures that computational resources are never wasted on exhaustive searches through dead ends, while guaranteeing that the system continuously explores alternative strategic paths.

Key Foundational Work

Learning Exploration/Exploitation Strategies for Single Trajectory Reinforcement Learning (2012) — contributed 2 concept elements to this direction.
Policy Search in a Space of Simple Closed-form Formulas: Towards Interpretability of Reinforcement Learning (2012) — contributed 1 concept elements to this direction.
Monte Carlo Search Algorithm Discovery for Single-Player Games (2013) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_bandit_guided_strategy_selection_4cca3386,
  title = {bandit-guided strategy selection},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/bandit-guided-strategy-selection/rdr_4cca3386501d4f03a9ca7ba38a6e7aed},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_bandit_guided_strategy_selection_4cca3386_v1,
  title = {bandit-guided strategy selection},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/bandit-guided-strategy-selection/rdr_4cca3386501d4f03a9ca7ba38a6e7aed/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake