Meta-Prompt Optimization for LLM-Based Sequential Decision Making

Mingze Kong; Yao Shu; Zhiyong Wang; Zhongxiang Dai

REVIEW 3 major objections 5 minor 1 cited by

Meta-Prompt Optimization for LLM-Based Sequential Decision Making

T0 review · 3 major / 5 minor · reviewed 2026-08-09 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read EXPO algorithm shows that treating meta-prompts as bandit arms lets LLM agents tune their own instructions on the fly.

desk verdict Solid empirical work on adversarial-bandit meta-prompt optimization, with a real gap: no random-domain-sampling baseline, so the mechanism claim goes beyond the evidence. read the letter →

arxiv 2502.00728 v1 pith:KJ7ZU2OJ submitted 2025-02-02 cs.LG

Mingze Kong , Zhiyong Wang , Yao Shu , Zhongxiang Dai This is my paper · ORCID

classification cs.LG

keywords meta-promptoptimizationLLMagentssequentialdecisionmakingadversarialbanditsEXP3algorithmneuralscoreestimationexemplarselectionprompt

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tries to establish that the meta-prompt given to an LLM-based sequential decision-making agent—the task description, the meta-instruction, and the choice of exemplars—should not be fixed in advance but should be automatically optimized during the run, using an adversarial bandit algorithm. The authors propose EXPO, which treats every rephrased prompt combination as a bandit arm, estimates each arm's score with a neural network trained on the prompts tried so far, and samples the next prompt from an EXP3-style exponential-weight distribution. They report that EXPO converges faster and reaches lower regression error and optimality gap than the fixed-prompt OPRO baseline on linear regression and traveling salesman problems, and that it reduces cumulative regret for an LLM-based multi-armed bandit agent. If this is right, then handcrafted prompts are a removable performance bottleneck for LLM agents, and non-stationarity in their rewards is not an obstacle but a standard bandit problem.

What carries the argument

The load-bearing mechanism is the combination of a neural-network score estimator with the EXP3 exponential-weight sampling rule from adversarial bandits. Each arm is a pair (task description D_i, meta-instruction I_i) from a pre-generated rephrased domain; the NN M(g(·); θ) takes the concatenated text embeddings of the pair, is trained with an MSE loss on the history of selected prompts and their observed scores, and predicts scores for all 10,201 arms. Those per-iteration estimates are accumulated into cumulative sums ŝ_i, and the next prompt is sampled from P[i] = exp(η ŝ_i) / Σ_j exp(η ŝ_j). The randomization and exponential reweighting are what let the method cope with non-stationary rewards; the NN is what lets it score arms it has never tried. For EXPO-ES, the same pattern is repeated on a domain of exemplar sequences, with historical NN parameters stored because the exemplar domain changes every iteration.

What would settle it

Hold out a random subset of prompt combinations, evaluate each with the task's own scorer, and compare the NN's predicted scores to the measured scores: if the correlation is near zero or the top-ranked predicted prompts perform no better than random prompts, EXPO's score-estimation step cannot be doing the work the paper attributes to it, and the reported gains would not transfer to new tasks.

Watch

Extended reading notes

Core claim

In the paper's own framing, the central discovery is that meta-prompt optimization for LLM-based sequential decision-making can be cast as an adversarial bandit problem, and that this casting works in practice. Because the LLM agent's state changes as it interacts with the environment, the score of a given meta-prompt is non-stationary across iterations, which rules out the stochastic bandit methods used in earlier prompt-optimization work; the paper shows that EXP3-style exponential-weight sampling with a neural-network score predictor handles this non-stationarity. Concretely, EXPO pre-generates a domain of 101 rephrased task descriptions and 101 rephrased meta-instructions (10,201 arms), and at each iteration trains a small neural network on embeddings of the prompts used so far and their observed scores, sums its predicted scores for every arm, and samples the next prompt from the resulting exponential distribution. The paper's experiments claim that this significantly and consistently outperforms OPRO across linear regression and TSP, that the discovered meta-prompt transfers to a fresh run of OPRO and gives a dramatic boost, and that EXPO-ES, which additionally selects exemplar subsets and their ordering, adds further gains when exemplars are informative.

Load-bearing premise

The whole scheme rests on the assumption that a neural network trained on only the few dozen meta-prompts actually tried can accurately predict scores for all ten-thousand-plus rephrased prompt combinations, so that the exponential-weight sampling distribution concentrates on genuinely better prompts rather than on overestimated ones.

Editorial extensions

If this is right

If EXPO is right, fixed handcrafted meta-prompts are a performance bottleneck for LLM-based sequential decision-making, and automatically rephrasing/tuning the task description and meta-instruction during the run yields faster convergence and better final solutions.
The adversarial bandit formulation (EXP3-style exponential weighting with randomization) is a viable way to handle non-stationary reward observations that arise because the LLM's state and experience change across iterations, where stochastic bandit methods like NeuralUCB fail.
The meta-prompt discovered by EXPO carries reusable value: fixing it as the prompt for a fresh run of OPRO gives a dramatic performance boost, implying the optimization finds genuinely better instructions and not just spuriously good ones.
EXPO-ES shows that when exemplars are informative (as in linear regression), automatically selecting their subset and order further improves performance; when they are not (as in TSP), it does not hurt.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Because Fig. 8 shows the prompt found by EXPO transfers to a fresh OPRO run, running EXPO once per task family and then deploying its discovered prompt could avoid per-run optimization cost; the paper does not test this offline-deployment mode.
The same EXP3-plus-neural-estimator recipe could be applied to other prompt components the paper mentions only in passing (output format, summary style) and to other LLM-agent settings such as RL, where state-dependent rewards create the same non-stationarity.
The method's success is likely sensitive to the quality and coverage of the rephrased domain: if the 100 LLM-generated rephrasings are all near-copies of the seed, the bandit can only select among near-identical arms, so the gains over OPRO would be partly attributable to domain generation rather than to the selection algorithm.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Quick read. The genuinely new piece is framing meta-prompt optimization for LLM agents as an adversarial bandit problem: the reward for a fixed prompt is non-stationary because the agent's state changes, so EXP3-style exponential weighting is a sensible response. The paper builds directly on the authors' own INSTINCT/EASE line, so the novelty is incremental but real. The experimental package is better than the typical preprint: two optimization tasks (OPRO on linear regression and TSP) plus an LLM-based MAB from Krishnamurthy et al., an ablation of the exploration parameter, a NeuralUCB comparison, and a genuinely useful external validation where the final prompt discovered by EXPO, fixed in place, improves OPRO. That last check is the strongest evidence that the discovered prompt is good, independent of the online selection.

Soft spots, in rough order. First, the missing baseline the stress-test flags: uniform random sampling over the same 10,201 arms. The paper itself shows that a hand-edited rephrasing beats the original OPRO prompt, suggesting the GPT-4-generated domain carries much of the value. Without a random-sampling baseline, the gain cannot be cleanly attributed to EXPO's cumulative score estimates. The external validation mitigates this but does not close it: it shows the final prompt is good, not that sequential selection beats random search over the domain. Second, the neural-network score prediction is load-bearing but never evaluated: no held-out prediction accuracy, no calibration check, and the training set is at most a few hundred examples in a 6144-dimensional embedding space. If the predicted scores are biased, the exponential weighting concentrates on overestimated prompts and the algorithm degenerates. Third, "significantly" is used without statistical tests; 3-5 repeats with standard error bars are thin for that word. Fourth, no code or data released.

None of this sinks the paper. The central empirical claim—that automatically optimized meta-prompts improve LLM-based optimizers and bandits—is supported by the fixed-prompt validation and by the consistent margins across tasks and LLMs. But the paper overclaims by attributing the gains to the bandit selection mechanism without isolating domain quality. A serious referee would ask for the random-sampling baseline and a held-out prediction evaluation.

Verdict: worth engaging. For anyone working on LLM-based optimization or prompt optimization, this is a useful data point and a fair baseline for comparison. I'd bring it to the reading group with the random-baseline question as the discussion starter, and I'd cite the external validation if I were writing about prompt transfer. It deserves peer review; a desk reject would be wrong.

Referee Report

3 major / 5 minor

Summary. The paper proposes EXPO, an adversarial-bandit-inspired algorithm for automatically optimizing the task description and meta-instruction components of meta-prompts used by LLM-based sequential decision-making agents. EXPO generates a domain of 10,201 rephrased prompt combinations, uses a neural network trained on the history of selected prompts and their scores to estimate scores of all arms, and samples the next prompt via exponential weighting. The paper also introduces EXPO-ES, which additionally selects exemplar sequences. Experiments on linear regression, TSP, and multi-armed bandit tasks with GPT-3.5 and GPT-4 claim consistent improvements over fixed-prompt baselines including a hand-edited enhanced OPRO.

Significance. If the empirical claims hold, the paper makes a useful contribution by demonstrating that automated meta-prompt optimization can improve LLM-based sequential decision-making, with gains in convergence speed and final performance across tasks and LLMs. The external validation in Sec. 5 (Fig. 8), where the final EXPO-discovered prompt improves fixed OPRO, is a valuable independent confirmation that the optimization finds effective prompts. The experimental scope is reasonably broad, and the ablation studies on the exploration parameter and the comparison with NeuralUCB provide useful insights. However, the significance is currently limited by the missing control baseline and the lack of statistical verification of the central 'significantly outperforms' claim.

major comments (3)

[Sec. 4.1, Fig. 2, App. B.1] The claim that EXPO's learned selection is responsible for the gains is undermined by the absence of a uniform-random baseline over the same 10,201-member arm domain. Because all arms are GPT-4 rephrasings of the initial prompts (App. B.1), and the paper shows that even the hand-edited enhanced OPRO improves performance, the improvements in Figs. 2 and 4 could stem from the quality of the generated domain rather than from EXPO's score-driven sampling. The authors should add a baseline that samples arms uniformly at random from the same domain, while keeping the exemplar heuristic identical, to isolate the contribution of the learned selection.
[Abstract, Sec. 4.1, App. B.2.1] The paper repeatedly uses 'significantly and consistently outperforms' (e.g., Sec. 4.1) but reports no statistical tests. With only 5 repeats for LR, 3 for TSP, and 6 for MAB, the standard-error bars in Figs. 2 and 4 may overlap at many iterations, and the word 'significant' is not supported. The authors should perform paired tests or bootstrap confidence intervals on the final performance or on the area under the learning curve, or moderate the language to 'consistent improvements' if the differences are not statistically significant.
[Algo. 1, lines 8-9, Eq. (1)] The algorithm's core relies on a neural network trained on at most 50–300 examples (the length of the history) to predict scores for all 10,201 arms in a 6,144-dimensional embedding space. No evidence is provided that these predictions are accurate or calibrated; if the NN overestimates certain arms, the softmax in Eq. (2) will concentrate sampling on those arms and degrade performance. The authors should report held-out prediction error (e.g., MSE or rank correlation) on arms not in the training history, and ideally show that the algorithm's performance is not overly sensitive to prediction noise.

minor comments (5)

[Sec. 5] In the paragraph 'Effectiveness of the Optimal Prompt Discovered by EXPO', 'ORPO' appears to be a typo for 'OPRO'.
[Sec. 4.2] The phrase 'across different prompt desings' contains a typo: 'desings' should be 'designs'.
[App. B.2.3] The prompt score definition involves a stabilizing constant b, but its value is never specified; this is a free parameter that affects the scale of scores and therefore the behavior of the exponential weights in Eq. (2). Please state the chosen value and any sensitivity to it.
[Figs. 2 and 4] The figures use color-coded curves that may be difficult to distinguish for color-blind readers; consider adding distinct markers or line styles.
[Sec. 3.1] The analogy to EXP3 is somewhat loose because standard EXP3 uses importance-weighted observed rewards, whereas EXPO uses cumulative NN-predicted scores; a sentence clarifying that the adversarial-bandit framework is only an inspiration and no regret bound is claimed would avoid overstatement.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: EXPO's contribution is an empirical algorithm comparison, not a quantity derived from its own inputs.

full rationale

The paper's central claims are empirical: EXPO and EXPO-ES 'significantly and consistently outperform' OPRO and reduce cumulative regret in LLM-based MAB. These are measured results from Figures 2 and 4, not quantities that are defined into existence by the algorithm. The score-estimation neural network is trained on observed meta-prompt scores and then used to sample among pre-generated prompt combinations; this is a standard algorithmic component, and the paper does not present the NN's score estimates as a separately 'predicted' outcome that was in fact used as a training label. The validation in which the final EXPO-discovered prompt is fixed and used to run standard OPRO again (Fig. 8) provides an independent check of the discovered prompt's quality. The self-citations to the authors' prior work on NN-based prompt optimization (Lin et al. 2024a,b; Wu et al. 2024) and on LLM-based rephrasing for domain generation are building-block reuse, not load-bearing circular justification: no uniqueness theorem is invoked, no ansatz is smuggled in via citation, and the central claim does not reduce to those cited results. The absence of a uniform-random-sampling baseline over the generated prompt domain is a legitimate experimental-design concern about attribution of the gains, but it is a correctness risk, not a logical circularity in the derivation.

Assumptions & free parameters 6 free parameters · 4 assumptions · 0 invented entities

The paper's central claim rests on several unverified modeling choices: the size and quality of the LLM-generated prompt domain, the ability of a small neural network to predict scores across the whole domain, and the substitution of predicted scores for observed rewards in the EXP3 update. No theoretical analysis is offered, and several key hyperparameters are chosen by hand without sensitivity studies.

free parameters (6)

EXP3 learning rate eta for task description and meta-instruction = 100 for LR/TSP, 10 for MAB
Chosen via ablation (values 10, 100, 1000 tested); higher eta reduces exploration.
EXP3 learning rate eta_exemplar for exemplar selection in EXPO-ES = 10
Set for exemplar selection; no ablation reported for this parameter.
Stabilizing constant b in prompt score definition = Unspecified, b > 0
Prompt Score = (-Evaluation Score + b)/b; the value is not reported and affects the scale of NN training labels.
Number of rephrasings per component (domain size) = 100 rephrasings each, 101x101 domain
A larger domain might improve results; this size was chosen without systematic tuning.
Exemplar pool and candidate count in EXPO-ES = L=20, pool=30, k_ES=257
Hand-chosen heuristics; no ablation on these counts is reported.
Neural network hidden layer widths = 1536 for EXPO, 512 for EXPO-ES
Hand-chosen architecture; no sensitivity analysis is provided.

assumptions (4)

domain assumption The observed score of the selected meta-prompt is a reliable indicator of its quality.
Sec. 2: 'the observed scores of a meta-prompt in every iteration are indicative of the quality of the arm'; used to train the NN with scores as labels.
domain assumption The LLM-generated domain of 101x101 prompt combinations contains meta-prompts that outperform the original fixed prompt.
Sec. 3.1 domain generation; if the optimal prompt is outside the domain, EXPO cannot find it (App. B.1).
domain assumption A neural network trained on a small history (one score per iteration) can generalize to predict scores of all 10,201 arms.
Algo. 1 lines 8-9; training set size is at most T (50-300) examples for a 6144-dim input, yet predictions for all arms are used to form the sampling distribution.
ad hoc to paper Reward non-stationarity can be treated as adversarial rewards, and cumulative sums of NN-predicted scores substitute for cumulative observed rewards in EXP3.
Sec. 3.1 uses predicted scores in Eq. (1) instead of observed rewards; no regret bound or formal justification is provided.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Meta-Prompt Optimization for LLM-Based Sequential Decision Making." pith.science (2026). https://pith.science/paper/KJ7ZU2OJ

@misc{pith2026250200728,
  author       = {Pith},
  title        = {Pith review of: Meta-Prompt Optimization for LLM-Based Sequential Decision Making},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KJ7ZU2OJ}},
  note         = {Machine review of arXiv:2502.00728}
}

read the original abstract

Large language models (LLMs) have recently been employed as agents to solve sequential decision-making tasks such as Bayesian optimization and multi-armed bandits (MAB). These works usually adopt an LLM for sequential action selection by providing it with a fixed, manually designed meta-prompt. However, numerous previous works have found that the prompt has a significant impact on the performance of the LLM, which calls for a method to automatically optimize the meta-prompt for LLM-based agents. Unfortunately, the non-stationarity in the reward observations during LLM-based sequential decision-making makes meta-prompt optimization highly challenging. To address this challenge, we draw inspirations from adversarial bandit algorithms, which are inherently capable of handling non-stationary reward observations. Building on this foundation, we propose our EXPonential-weight algorithm for prompt Optimization} (EXPO) to automatically optimize the task description and meta-instruction in the meta-prompt for LLM-based agents. We also extend EXPO to additionally optimize the exemplars (i.e., history of interactions) in the meta-prompt to further enhance the performance, hence introducing our EXPO-ES algorithm. We use extensive experiments to show that our algorithms significantly improve the performance of LLM-based sequential decision-making.

Figures

Figures reproduced from arXiv: 2502.00728 by the authors.

**Figure 1.** Illustration of our EXPO algorithm. We use purple to denote the task description and blue to represent the meta-instruction. which can then be used to predict the scores of every metaprompts in the domain. We denote this NN as M(g(·); θ), in which θ represents the NN parameters. Adversarial Bandits. In adversarial bandits, the goal is to compete against the best arm in hindsight (Lattimore & Szepesvari ´ , 2020). C… view at source ↗

**Figure 2.** Results of different algorithms (mean ± standard error) in the Linear Regression and TSP task (Sec. 4.1). Lower is better. regression error (i.e., mean squared error) for the LR tasks and optimality gap (i.e., the difference between the total distance of the discovered route and that of the optimal route) for the TSP tasks (lower is better for both tasks). Of note, in addition to the standard OPRO (pink curves) (Ya… view at source ↗

**Figure 3.** The task description and meta-instruction used by OPRO (left) and optimized by our EXPO (right) in a Linear Regression task. 0 20 40 60 80 100 Iteration 0 2 4 6 8 10 Cumulative Regret BSSND EXPO EXPO-ES 0 20 40 60 80 100 Iteration 0 2 4 6 8 10 Cumulative Regret BSSCD EXPO EXPO-ES BSSND (easy) BSSCD (easy) 0 20 40 60 80 100 Iteration 0 2 4 6 8 10 Cumulative Regret BSSND EXPO EXPO-ES 0 20 40 60 80 100 Iteration 0 2 4 … view at source ↗

Figures from the paper (15 more)

**Figure 6.** Figure 6: Comparison of our EXPO with NeuralUCB (i.e., a representative stochastic MAB algorithm) in the LR tasks. the impact of the degree of exploration, i.e., the value of η (see line 10 of Algo. 1). The results ( [PITH_FULL_IMAGE:figures/full_fig_p007_6.png]

**Figure 5.** Figure 5: Results of our EXPO when only optimizing the task description or the meta-instruction. render these stochastic MAB methods unsuitable. Here we verify this by comparing our EXPO with the NeuralUCB algorithm adopted by Lin et al. (2024b); Wu et al. (2024). The results fo…

**Figure 7.** Figure 7: First three figures: ablation study on impact of exploration parameter η. Bottom right: results using GPT-4-Turbo. tify effective meta-prompts, here we replace the original task description and meta-instruction in an LLM-based sequential decision-making algorithm (e.…

**Figure 8.** Figure 8: Results achieved by fixing the meta-prompt to be the optimal one discovered by our EXPO (gray curves). 6. Related Work Prompt Optimization. The field of prompt optimization has been gaining significant popularity recently. Earlier works on this topic have focused on op…

**Figure 9.** Figure 9: An example of the summarized observation history used by the LLM-based MAB algorithm from Krishnamurthy et al. (2024). (2024) (Sec. 4.2), we make two modifications to our standard EXPO-ES algorithm described in Algo. 2. Firstly, instead of randomly sampling k ES exempl…

**Figure 10.** Figure 10: The task description in the original OPRO prompt. The task description in our enhanced OPRO prompt You are given a list of points with coordinates below: {POINTS}. Below are some previous traces and their lengths. The traces are arranged in descending order based on t…

**Figure 11.** Figure 11: The task description in the enhanced OPRO prompt. The texts we have modified are highlighted in red. B.3. More Details on the LLM-Based Multi-Armed Bandits Task (Sec. 4.2) B.3.1. EXPLANATION OF BSSCD AND BSSND We provide a detailed explanation and demonstration of pro…

**Figure 12.** Figure 12: A complete example of the prompt in MAB. The different components in the prompt are explained in detail in App. B.3.1. runs per setting. Each experiment consists of 100 iterations, with the LLM-based agents making decisions and updating prompts iteratively to optimize…

**Figure 13.** Figure 13: shows a zoomed version of [PITH_FULL_IMAGE:figures/full_fig_p019_13.png]

**Figure 14.** Figure 14: Results of different algorithms in the Linear Regression task and TSP task (Sec. 4.1). We have additionally included the original OPRO (which selects all 8 actions using a temperature of 1), as well as its enhanced variant. Lower is better. Krishnamurthy et al. (2024)…

**Figure 15.** Figure 15: Convergence curves of our EXPO with and without exemplars embedding across different tasks: Linear Regression (top row) and TSP with 10, 15, and 20 nodes (bottom row). OPRO You are given a list of points with coordinates below: {POINTS}. Below are some previous traces…

**Figure 16.** Figure 16: The task description (top) and meta-instruction (bottom) used by OPRO (left) and optimized by our EXPO (right) in a TSP task. 21 [PITH_FULL_IMAGE:figures/full_fig_p021_16.png]

**Figure 17.** Figure 17: The suggestive framing (corresponding to the task description) and MAB problem description (corresponding to the metainstruction) used by BSSND hard (left) and optimized by our EXPO (right) in an LLM-based MAB task. BSSCD You are a bandit algorithm in a room with 5 b…

**Figure 18.** Figure 18: The suggestive framing (corresponding to the task description) and MAB problem description (corresponding to the metainstruction) used by BSSCD hard (left) and optimized by our EXPO (right) in an LLM-based MAB task. 22 [PITH_FULL_IMAGE:figures/full_fig_p022_18.png]

**Figure 19.** Figure 19: Comparison of our EXPO with NeuralUCB (i.e., a representative stochastic MAB algorithm) in the TSP tasks. 23 [PITH_FULL_IMAGE:figures/full_fig_p023_19.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

MASPOB: Bandit-Based Prompt Optimization for Multi-Agent Systems with Graph Neural Networks
cs.LG 2026-03 conditional novelty 6.0 of 10

MASPOB combines a GNN surrogate, LinUCB-style uncertainty, and coordinate ascent to optimize prompts in fixed-topology multi-agent LLM systems, beating AFlow and MIPRO on average across six benchmarks.

Reference graph

Works this paper leans on

28 extracted references · 7 canonical work pages · cited by 1 Pith paper

[1]

M., Longpre, S., Lambert, N., Wang, X., Muennighoff, N., Hou, B., Pan, L., Jeong, H., Raffel, C., Chang, S., Hashimoto, T., and Wang, W

Albalak, A., Elazar, Y ., Xie, S. M., Longpre, S., Lambert, N., Wang, X., Muennighoff, N., Hou, B., Pan, L., Jeong, H., Raffel, C., Chang, S., Hashimoto, T., and Wang, W. Y . A survey on data selection for language models. arXiv:2402.16827,

arXiv
[2]

3.2, there are two major differences compared to the way in which our EXPO algorithm optimizes the task description and meta-instruction (Algo

As we have discussed in Sec. 3.2, there are two major differences compared to the way in which our EXPO algorithm optimizes the task description and meta-instruction (Algo. 1). Firstly, our domain of kES arms (i.e., every arm corresponds to a randomly sampled exemplar sequence) changes in every iteration (line 8). Secondly, as a result of the time-varying...

work page 2024
[4]

Ex- ploring large language model based intelligent agents: Definitions, methods, and prospects

Cheng, Y ., Zhang, C., Zhang, Z., Meng, X., Hong, S., Li, W., Wang, Z., Wang, Z., Yin, F., Zhao, J., et al. Ex- ploring large language model based intelligent agents: Definitions, methods, and prospects. arXiv preprint arXiv:2401.03428,

arXiv
[5]

In-context exploration- exploitation for reinforcement learning

Dai, Z., Tomasi, F., and Ghiassian, S. In-context exploration- exploitation for reinforcement learning. arXiv preprint arXiv:2403.06826,

arXiv
[7]

Ambiguity-aware in-context learning with large language models

Gao, L., Chaudhary, A., Srinivasan, K., Hashimoto, K., Ra- man, K., and Bendersky, M. Ambiguity-aware in-context learning with large language models. arXiv:2309.07900,

arXiv
[8]

Task Facet Learning: A Structured Approach to Prompt Optimization

Juneja, G., Natarajan, N., Li, H., Jiao, J., and Sharma, A. Task facet learning: A structured approach to prompt optimization. arXiv preprint arXiv:2406.10504,

work page Pith review arXiv
[9]

An example of the summarized observation history used by the LLM-based MAB algorithm from Krishnamurthy et al. (2024). (2024) (Sec. 4.2), we make two modifications to our standard EXPO-ES algorithm described in Algo

work page 2024
[10]

J., Zhang, C., and Slivkins, A

Krishnamurthy, A., Harris, K., Foster, D. J., Zhang, C., and Slivkins, A. Can large language models explore in-context? arXiv preprint arXiv:2403.15371,

arXiv

Show all 28 references

[11]

The texts we have modified are highlighted in red

The task description in the enhanced OPRO prompt. The texts we have modified are highlighted in red. B.3. More Details on the LLM-Based Multi-Armed Bandits Task (Sec. 4.2) B.3.1. E XPLANATION OF BSSCD AND BSSND We provide a detailed explanation and demonstration of prompt desi...

2024
[12]

Agentbench: Evalu- ating llms as agents

Liu, X., Yu, H., Zhang, H., Xu, Y ., Lei, X., Lai, H., Gu, Y ., Ding, H., Men, K., Yang, K., et al. Agentbench: Evalu- ating llms as agents. arXiv preprint arXiv:2308.03688,

arXiv
[13]

P., Xie, Q., and Nowak, R

Mukherjee, S., Hanna, J. P., Xie, Q., and Nowak, R. Pre- training decision transformers with reward prediction for in-context multi-task structured bandit learning. arXiv preprint arXiv:2406.05064,
[14]

and Wong, E

Nguyen, T. and Wong, E. In-context example selection with influences. arXiv:2302.11042,

arXiv
[15]

J., Purtell, J., Broman, D., Potts, C., Zaharia, M., and Khattab, O

Opsahl-Ong, K., Ryan, M. J., Purtell, J., Broman, D., Potts, C., Zaharia, M., and Khattab, O. Optimizing instruc- tions and demonstrations for multi-stage language model programs. arXiv preprint arXiv:2406.11695,

arXiv
[16]

Schneider, L., Wistuba, M., Klein, A., Golebiowski, J., Zap- pella, G., and Merra, F. A. Hyperband-based bayesian op- timization for black-box prompt selection. arXiv preprint arXiv:2412.07820,

arXiv
[17]

Best arm identifi- cation for prompt learning under a limited budget

Shi, C., Yang, K., Yang, J., and Shen, C. Best arm identifi- cation for prompt learning under a limited budget. arXiv preprint arXiv:2402.09723,

arXiv
[19]

Trans- formers learn temporal difference methods for in-context reinforcement learning

Wang, J., Blaser, E., Daneshmand, H., and Zhang, S. Trans- formers learn temporal difference methods for in-context reinforcement learning. arXiv preprint arXiv:2405.13861, 2024a. Wang, L., Ma, C., Feng, X., Zhang, Z., Yang, H., Zhang, J., Chen, Z., Tang, J., Chen, X., Lin, Y ...

arXiv
[20]

The rise and potential of large language model based agents: A survey

Xi, Z., Chen, W., Guo, X., He, W., Ding, Y ., Hong, B., Zhang, M., Wang, J., Jin, S., Zhou, E., et al. The rise and potential of large language model based agents: A survey. arXiv preprint arXiv:2309.07864,

arXiv
[21]

Agentgym: Evolving large language model-based agents across di- verse environments

Xi, Z., Ding, Y ., Chen, W., Hong, B., Guo, H., Wang, J., Yang, D., Liao, C., Guo, X., He, W., et al. Agentgym: Evolving large language model-based agents across di- verse environments. arXiv preprint arXiv:2406.04151,

arXiv
[22]

Beyond numeric awards: In-context dueling bandits with llm agents.arXiv preprint arXiv:2407.01887,

Xia, F., Liu, H., Yue, Y ., and Li, T. Beyond numeric awards: In-context dueling bandits with llm agents.arXiv preprint arXiv:2407.01887,

arXiv
[23]

Unlock- ing black-box prompt tuning efficiency via zeroth-order optimization

Zhan, H., Chen, C., Ding, T., Li, Z., and Sun, R. Unlock- ing black-box prompt tuning efficiency via zeroth-order optimization. In Findings of the Association for Com- putational Linguistics: EMNLP 2024, pp. 14825–14838,

2024
[27]

The different components in the prompt are explained in detail in App

A complete example of the prompt in MAB. The different components in the prompt are explained in detail in App. B.3.1. runs per setting. Each experiment consists of 100 iterations, with the LLM-based agents making decisions and updating prompts iteratively to optimize performa...

2024
[28]

Results of different algorithms in the Linear Regression task and TSP task (Sec. 4.1). We have additionally included the original OPRO (which selects all 8 actions using a temperature of 1), as well as its enhanced variant. Lower is better. Krishnamurthy et al. (2024)) and tho...

2024
[1995]

A., Zhang, M., Mei, Q., and Ben- dersky, M

Kong, W., Hombaiah, S. A., Zhang, M., Mei, Q., and Ben- dersky, M. Prewrite: Prompt rewriting with reinforcement learning. arXiv preprint arXiv:2401.08189,

arXiv
[2020]

Wan, X., Sun, R., Nakhost, H., and Arik, S. O. Teach better or show smarter? on instructions and exem- plars in automatic prompt optimization. arXiv preprint arXiv:2406.15708,

arXiv
[2021]

Lin, X., Dai, Z., Verma, A., Ng, S.-K., Jaillet, P., and Low, B. K. H. Prompt optimization with human feedback. arXiv preprint arXiv:2405.17346, 2024a. Lin, X., Wu, Z., Dai, Z., Hu, W., Shu, Y ., Ng, S.-K., Jaillet, P., and Low, B. K. H. Use your INSTINCT: Instruction optimiza...

arXiv
[2022]

Promptbreeder: Self-referential self- improvement via prompt evolution

Fernando, C., Banarse, D., Michalewski, H., Osindero, S., and Rockt¨aschel, T. Promptbreeder: Self-referential self- improvement via prompt evolution. arXiv:2309.16797,

arXiv
[2023]

Efficient sequential deci- sion making with large language models

Chen, D., Zhang, Q., and Zhu, Y . Efficient sequential deci- sion making with large language models. arXiv preprint arXiv:2406.12125,

arXiv
[2024]

InstructZero: Efficient instruction optimization for black- box large language models

Chen, L., Chen, J., Goldstein, T., Huang, H., and Zhou, T. InstructZero: Efficient instruction optimization for black- box large language models. arXiv:2306.03082,

arXiv

Pith tools

Reviewed August 9, 2026 · model on record in the stance chip above.

[1] [1]

M., Longpre, S., Lambert, N., Wang, X., Muennighoff, N., Hou, B., Pan, L., Jeong, H., Raffel, C., Chang, S., Hashimoto, T., and Wang, W

Albalak, A., Elazar, Y ., Xie, S. M., Longpre, S., Lambert, N., Wang, X., Muennighoff, N., Hou, B., Pan, L., Jeong, H., Raffel, C., Chang, S., Hashimoto, T., and Wang, W. Y . A survey on data selection for language models. arXiv:2402.16827,

arXiv

[2] [2]

3.2, there are two major differences compared to the way in which our EXPO algorithm optimizes the task description and meta-instruction (Algo

As we have discussed in Sec. 3.2, there are two major differences compared to the way in which our EXPO algorithm optimizes the task description and meta-instruction (Algo. 1). Firstly, our domain of kES arms (i.e., every arm corresponds to a randomly sampled exemplar sequence) changes in every iteration (line 8). Secondly, as a result of the time-varying...

work page 2024

[3] [4]

Ex- ploring large language model based intelligent agents: Definitions, methods, and prospects

Cheng, Y ., Zhang, C., Zhang, Z., Meng, X., Hong, S., Li, W., Wang, Z., Wang, Z., Yin, F., Zhao, J., et al. Ex- ploring large language model based intelligent agents: Definitions, methods, and prospects. arXiv preprint arXiv:2401.03428,

arXiv

[4] [5]

In-context exploration- exploitation for reinforcement learning

Dai, Z., Tomasi, F., and Ghiassian, S. In-context exploration- exploitation for reinforcement learning. arXiv preprint arXiv:2403.06826,

arXiv

[5] [7]

Ambiguity-aware in-context learning with large language models

Gao, L., Chaudhary, A., Srinivasan, K., Hashimoto, K., Ra- man, K., and Bendersky, M. Ambiguity-aware in-context learning with large language models. arXiv:2309.07900,

arXiv

[6] [8]

Task Facet Learning: A Structured Approach to Prompt Optimization

Juneja, G., Natarajan, N., Li, H., Jiao, J., and Sharma, A. Task facet learning: A structured approach to prompt optimization. arXiv preprint arXiv:2406.10504,

work page Pith review arXiv

[7] [9]

An example of the summarized observation history used by the LLM-based MAB algorithm from Krishnamurthy et al. (2024). (2024) (Sec. 4.2), we make two modifications to our standard EXPO-ES algorithm described in Algo

work page 2024

[8] [10]

J., Zhang, C., and Slivkins, A

Krishnamurthy, A., Harris, K., Foster, D. J., Zhang, C., and Slivkins, A. Can large language models explore in-context? arXiv preprint arXiv:2403.15371,

arXiv