Research map / Probabilistic and scientific modeling / Bayesian optimization
Transition Constrained Bayesian Optimization via Markov Decision Processes
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Casts transition-constrained Bayesian optimization for maximizer identification as an MDP planning problem, solved via Frank-Wolfe with RL/dynamic-programming subproblems (discrete) or MPC (continuous), yielding non-Markovian policies via adaptive resampling.
Problem
Bayesian optimization where the next query is constrained by known, possibly stochastic transition dynamics (e.g., movement limits, monotonicity, transition-dependent noise), so future choices require planning over the experiment horizon.
Approach
Replace the greedy acquisition function with a variance-reduction utility over maximizer-candidate pairs, reformulated as a function of state-action visitation distributions over an MDP; optimize it with Frank-Wolfe, where each linearized subproblem is an RL problem solved exactly by dynamic programming (discrete) or as MPC (continuous), and re-plan at every step for a non-Markovian policy.
Key results
- On the Knorr pyrazole reactor benchmark with episodic feedback, MDP-BO identifies the best arm in a higher proportion of runs than baselines (the paper reports it as best-performing).
- On Lake Ypacarai, the method correctly identifies the maximum in approximately 50% of runs by episode two and achieves better regret than MDP-EI.
- On synthetic benchmarks with movement constraints, MDP-BO matches state-of-the-art local-constraint methods (TrSnAKe, LSR) while being more robust with lower variance in chosen paths.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use transition-constrained MDP-BO rather than MDP-EI | Lake Ypacarai, episodic feedback · Lake Ypacarai | correct maximum identification: approximately 50% by episode two | Helped |
| Use transition-constrained MDP-BO rather than MDP-EI | Lake Ypacarai, episodic feedback · Lake Ypacarai | regret | Helped |
| Account for transition-driven measurement noise | Free-electron laser optimization · Free-electron laser | inference regret | Helped |
| Use Thompson Sampling rather than UCB to approximate the maximizer set (ablation) | MDP-BO · Asynchronous synthetic benchmarks | predictive regret | Helped |
| Use UCB rather than Thompson Sampling to approximate the maximizer set (ablation) | MDP-BO · Synchronous synthetic benchmarks | predictive regret | Helped |
| Use MDP-BO-UCB rather than Thompson-sampling planning variants (ablation) | MDP-BO · Synchronous synthetic benchmarks | predictive regret | Mixed |
| Use MDP-BO rather than MDP-EI | Knorr pyrazole synthesis, episodic feedback · Knorr pyrazole synthesis | best prediction regret | Helped |
| Use MDP-BO rather than MDP-EI | Knorr pyrazole synthesis, immediate feedback · Knorr pyrazole synthesis | best prediction regret | No clear effect |
| Replace MDP-BO planning with greedy reward optimization | Knorr pyrazole synthesis, immediate feedback · Knorr pyrazole synthesis | best prediction regret | Hurt |
| Use MDP-BO rather than MDP-EI | Lake Ypacarai, immediate feedback with high noise · Lake Ypacarai | final performance: from episode three onwards | Helped |
| Use MDP-BO rather than TrSnAKe or LSR | Continuous synthetic benchmarks · Synchronous and asynchronous synthetic benchmarks | predictive regret | No clear effect |
| Use MDP-BO-TS rather than MDP-BO-UCB (ablation) | MDP-BO · Asynchronous synthetic benchmarks | path consistency | Helped |
Surprising findings
- LSR, a specialist heuristic for local box constraints, performs very competitively and often matches MDP-BO in synchronous benchmarks.
- The variance-based maximizer-identification objective coincides with an objective from linear bandit best-arm identification literature derived from a frequentist view.
Limitations
- Continuous-MDP sub-problem is non-convex and solved heuristically via MPC-style parameterization with linear dynamics.
- Theoretical convergence result relies on assumptions (e.g., decreasing maximizer set with bounded gap C_t) that are conjectured rather than proven.
- Assumes transition constraints and dynamics are known a priori.
Experimental setup
Datasets: Knorr pyrazole synthesis simulator Lake Ypacarai contamination benchmark free-electron laser simulator Michalewicz Hartmann Levy Branin SnAr (Summit)
Benchmarks: Knorr pyrazole synthesis Lake Ypacarai monitoring free-electron laser tuning Michalewicz Hartmann Levy Branin SnAr
Metrics: proportion of runs identifying true maximum median predictive regret
Baselines: Greedy-UCB MDP-EI TrSnAKe LSR MDP-BO-TS MDP-BO-UCB
Builds on: Gaussian process bandits convex reinforcement learning truncated SnAKe local search region BayesOpt
Closest papers by meaning
- Optimizing the Unknown: Black Box Bayesian Optimization with Energy-Based Model and Reinforcement Learning (NeurIPS 2025 · similarity 0.90)
- Bayesian Policy Optimization for Model Uncertainty (ICLR 2019 · similarity 0.89)
- Automating Bayesian optimization with Bayesian optimization (NeurIPS 2018 · similarity 0.88)
- Augmented Bayesian Policy Search (ICLR 2024 · similarity 0.88)
- Sequential Monte Carlo for Policy Optimization in Continuous POMDPs (NeurIPS 2025 · similarity 0.88)
- Stopping Bayesian Optimization with Probabilistic Regret Bounds (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.