Open Problems

Multi-Agent & Goal-Conditioned RL

Evaluating the Robustness and Limits of Tree-Search RL Under Stochastic Dynamics and Function Approximation

Scope to testOpen
Possible candidate · 2/5 runs4 papers report this25% from 2025+

Generated automatically from the limitations stated in 4 papers (NeurIPS, ICML), listed under Evidence. It is not a paper, and it does not come from papers submitted to CSPaper.

The problem

Existing theoretical guarantees and empirical evaluations for tree-search and tree-MDP RL algorithms are strictly restricted to deterministic, tabular, or binary-tree settings. Real-world decision-making domains involve transition stochasticity and large state spaces requiring neural function approximation, where deterministic branching assumptions are untested. Without systematic evaluation across stochastic transitions and continuous state spaces, it is unknown whether deterministic tree-guided methods degrade gracefully or fail catastrophically.

Why it matters

Clarifies the operational boundaries and robustness limits of tree-based RL methods when deterministic assumptions are relaxed, providing concrete guidance on when deterministic tree planning remains valid in noisy environments.

Ways to approach it

Prior-work checks are free with an account. Results someone already ran are shown to everyone.

  1. 1

    Benchmark existing deterministic tree-search algorithms on synthetic MDPs with systematically injected transition noise ($\epsilon \in [0, 0.5]$), measuring empirical regret, node expansion overhead, and failure rates.

  2. 2

    Extend deterministic tree-MDP policy bounds to bounded stochastic transition models, measuring how theoretical suboptimality gaps scale with environmental transition variance.

  3. 3

    Implement and evaluate tree-search RL with deep neural function approximation on standard continuous control benchmarks, measuring value estimation error and policy convergence against tabular baselines.

Have a different approach?

Describe how you would tackle this problem and we'll look for papers that already do it. Free; your text stays private.

Free · 3 checks per day

Why it might fail

If trivial adaptations from standard stochastic planning (such as expectimax or chance-node MCTS) immediately bridge the gap without revealing any distinct theoretical trade-offs, the contribution would reduce to routine benchmarking.

Evidence

Each paper's own statement of the limitation, verbatim.

Nearest existing work

Related open problems

Multi-Agent & Goal-Conditioned RL

Effect to explainPartly addressed

Policy Generalization Across Large Agent-Count Shifts in Multi-Agent Reinforcement Learning

Multi-agent and goal-conditioned reinforcement learning policies trained on small team sizes fail catastrophically when evaluated on larger agent counts, collapsing to near-zero success rates on unseen large-scale tasks. Existing architectures and skill representations fail to capture distribution shifts under scale, forcing practitioners to retrain separate policies from scratch for every team size. This inability to transfer learned coordination across team scales prevents the deployment of multi-agent policies to dynamic environments where entity counts vary at runtime.

Possible candidate · 2/5 runs3 papers report this100% from 2025+
Generated automatically, not curated by hand. Automated prior-work checks catch about a third of existing work, so treat this problem as a lead to investigate.