Progressive Content Refinement with Decaying Reward Joint LinUCB

# Progressive Content Refinement with Decaying Reward Joint LinUCB
Source: [https://arxiv.org/html/2608.06750](https://arxiv.org/html/2608.06750)
Shion Ishikawa Rakuten Group, Inc\. Tokyo, Japan &Pablo Loyola Rakuten Group, Inc\. Tokyo, Japan &Young\-joo Chung Rakuten Group, Inc\. San Mateo, USA &Yun Ching Liu Rakuten Group, Inc\. Tokyo, Japan

###### Abstract

Iterative refinement has significantly enhanced Large Language Model \(LLM\) performance; however, existing methods—ranging from feedback\-based Self\-Refine to traditional bandit approaches—often rely on static options or overlook the “saturation effect”\. This neglect leads to over\-exploitation, where the continuous use of identical prompts or arms results in diminishing rewards over time\.

To address this challenge, we propose a novel contextual bandit algorithm that explicitly incorporates reward decay modeling\. Utilizing an Expectation\-Maximization \(EM\) algorithm, our method simultaneously estimates both arm\-specific and decay parameters\. Furthermore, by embedding prompts as arms, we facilitate the joint learning of arm values, distinguishing our approach from the traditional disjoint Linear Upper Confidence Bound \(LinUCB\) framework\.

Experimental results on Sentiment Reversal and GSM8K benchmarks demonstrate that our method achieves significant performance gains over strong baselines\. Finally, our ablation study confirms that the integration of reward decay modeling within the bandit framework is crucial for mitigating over\-exploitation and optimizing the iterative refinement process\.

Progressive Content Refinement with Decaying Reward Joint LinUCB

Shion IshikawaRakuten Group, Inc\.Tokyo, JapanPablo LoyolaRakuten Group, Inc\.Tokyo, JapanYoung\-joo ChungRakuten Group, Inc\.San Mateo, USAYun Ching LiuRakuten Group, Inc\.Tokyo, Japan

## 1Introduction

In recent years, Large Language Models \(LLMs\) have revolutionized the field of natural language processing, demonstrating remarkable performance across a wide array of tasks such as text generation, summarization, translation, and complex reasoningBrownet al\.\([2020](https://arxiv.org/html/2608.06750#bib.bib1)\); Chunget al\.\([2024](https://arxiv.org/html/2608.06750#bib.bib2)\)\. To further unlock the full potential of these models and obtain higher\-quality, more reliable outputs, iterative refinement techniques have become increasingly crucialMadaanet al\.\([2023](https://arxiv.org/html/2608.06750#bib.bib3)\); Heinet al\.\([2025](https://arxiv.org/html/2608.06750#bib.bib4)\)\. These methods aim to systematically enhance LLM\-generated content by applying successive improvements based on various feedback mechanisms\.

While initial iterative refinement approaches like Self\-RefineMadaanet al\.\([2023](https://arxiv.org/html/2608.06750#bib.bib3)\)have shown promise by allowing LLMs to critique and improve their own outputs, they often rely on pre\-defined or heuristically chosen refinement prompts\. This static selection of prompts can lead to suboptimal performance, as the effectiveness of a refinement strategy can vary significantly across different contexts and over time\. More sophisticated methods have begun to incorporate multi\-armed bandit \(MAB\) frameworks\. These frameworks treat different refinement strategies \(e\.g\., prompt design strategies, contents to refine\) as "arms" to be pulledAshizawaet al\.\([2025](https://arxiv.org/html/2608.06750#bib.bib6)\); Tanget al\.\([2024](https://arxiv.org/html/2608.06750#bib.bib5)\)\. These bandit\-based approaches effectively balance the exploration of novel refinement strategies with the exploitation of known effective ones, optimizing the overall refinement process\.

However, a critical limitation in existing iterative refinement paradigms, particularly prevalent in bandit\-based methods, is the implicit assumption of stationary reward distributions for each refinement strategy \(arm\)\. In reality, repeatedly applying the same refinement prompt or exploiting a single arm can lead to a "saturation effect\." For instance, an LLM might quickly exhaust the utility of a specific grammatical correction prompt after a few iterations, or a mathematical reasoning prompt might become redundant once a certain level of accuracy is achieved\. Continuing to apply such a prompt results in diminishing returns, or even negative impacts, akin to over\-editing\. Empirical evidence for this decay phenomenon is presented in Figure 4 ofMadaanet al\.\([2023](https://arxiv.org/html/2608.06750#bib.bib3)\)\. This phenomenon, termed "reward decay" by prior work like Rotting BanditLevineet al\.\([2017](https://arxiv.org/html/2608.06750#bib.bib7)\), leads to inefficient over\-exploitation of diminishingly effective strategies, hindering overall refinement efficiency\. Traditional bandit algorithms, designed for stationary environments, fail to adequately capture and adapt to this dynamic decay in reward\.

While the concept of decaying rewards has been explored by Rotting Bandit, this approach suffers from inefficiencies due to their initial exploration strategies, such as relying on round\-robin sampling to estimate decay rates\.

To address these fundamental challenges, we propose a novel bandit algorithm that explicitly models and adapts to the reward decay phenomenon in LLM iterative refinement\. Furthermore, our approach abstracts arms as embeddings, treating these as the context for each arm\. Traditional LinUCB\-like approachesLiet al\.\([2010](https://arxiv.org/html/2608.06750#bib.bib8)\)often have arm features that are disjoint with each other \(e\.g\., assuming distinct arm models for how arm context affects click\-through rates in sports and political news recommendations\)\. In contrast, our method assumes a unified underlying model regarding how prompt embeddings influence rewards\. This means that when a new prompt \(arm\) is generated, its embedding representation allows for a more informed initial estimation of its parameters, effectively mitigating the LLM\-specific “cold start” problem often encountered with new prompts\.

Finally, by introducing an Expectation\-Maximization \(EM\) algorithmMoon \([1996](https://arxiv.org/html/2608.06750#bib.bib19)\), we achieve simultaneous learning of both decay and contextual parameters, thereby circumventing the inefficient exploration phase associated with round\-robin sampling in methods like Rotting Bandit\.

These techniques allow our system to dynamically balance exploration of potentially effective but less\-used prompts with the exploitation of currently high\-performing prompts, while actively accounting for their diminishing utility over time\.

Our technical contributions are threefold:

- •We propose a novel bandit algorithm DR\-LinUCB111Source code attached for review\. GitHub repository will be available at https://github\.com/\{anonymous\_org\} upon acceptance\.that explicitly incorporates a reward decay model for each arm, enabling adaptive exploration\-exploitation in dynamic LLM refinement environments\.
- •We introduce a method to embed refinement prompts as contextual features for our bandit arms, enabling the joint learning of arm values\. Unlike traditional disjoint LinUCB, our method assumes a unified arm model for each LLM task, which allows for a more informed initial estimation of parameters for new prompts, thereby mitigating the LLM\-specific "cold start" problem\.
- •We leverage an Expectation\-Maximization \(EM\) algorithm for the simultaneous learning of both arm contextual parameters and their associated decay parameters from observed rewards\. This approach avoids inefficient initial exploration strategies such as round\-robin sampling\.

![Refer to caption](https://arxiv.org/html/2608.06750v1/overall.png)Figure 1:DR\-LinUCB’s Progressive Content Refinement\. This flowchart details its core components: reward decay modeling, UCB\-based arm selection and joint EM\-based parameter learning\.
## 2Related works

### 2\.1Iterative Refinement for Large Language Models

The ability of LLMs to perform iterative self\-correction has emerged as a key technique for enhancing generation quality\. SELF\-REFINEMadaanet al\.\([2023](https://arxiv.org/html/2608.06750#bib.bib3)\)introduced LLMs generating, critiquing, and refining their own outputs using natural language feedback, significantly improving performance across tasks\. This concept extended to specific domains: Chen et al\. \(2024\) applied it to machine translation for human\-preferred fluencyChenet al\.\([2024](https://arxiv.org/html/2608.06750#bib.bib23)\), and Hein et al\. \(2025\) developed high\-accuracy clinical information extraction pipelines, emphasizing task definition and human\-in\-the\-loop refinementHeinet al\.\([2025](https://arxiv.org/html/2608.06750#bib.bib4)\)\. Despite these advances, a key limitation of existing methods is their limited prompt diversity, which our work mitigates through bandit explore\-exploitation\.

### 2\.2Bandit Algorithms for Large Language Model

In multi\-step tasks, LLMs need to balance using proven prompts \(exploitation\) with trying new ones \(exploration\)\. Bandit algorithms help by intelligently guiding this choice, preventing over\-reliance on old prompts and efficiently discovering better ones\.

In code refinement, the REx \(REfine, Explore, Exploit\) algorithmTanget al\.\([2024](https://arxiv.org/html/2608.06750#bib.bib5)\)frames iterative LLM\-based code repair as an arm\-acquiring bandit problem\. Each generated code is an arm, and refining it yields a reward \(passing tests\)\. REx uses Thompson Sampling with heuristic\-informed priors to balance exploring new code and exploiting promising ones\. It significantly improved problem\-solving and reduced LLM calls across diverse coding tasks\.

For prompt optimization, OPTS \(Optimizing Prompts with sTrategy Selection\)Ashizawaet al\.\([2025](https://arxiv.org/html/2608.06750#bib.bib6)\)explicitly selects prompt design strategies using bandit algorithms\. Traditional methods often rely on LLMs implicitly choosing strategies, which can be suboptimal\. OPTS\(TS\), its most effective variant, treats each strategy as an arm, learning its efficacy via Thompson SamplingThompson \([1933](https://arxiv.org/html/2608.06750#bib.bib10)\)\. This approach improved prompt performance by up to 50% by making strategy selection adaptive and data\-driven\.

Unlike REx and OPTS, which respectively refine content candidates with a fixed prompt and optimize a single prompt, our approach dynamically selects generated prompts\. This enables prompt selection to be adapted based on the current output state, allowing for contextual content refinement\.

### 2\.3Bandit Algorithms with Decaying Rewards

The "Rotting Bandits" frameworkLevineet al\.\([2017](https://arxiv.org/html/2608.06750#bib.bib7)\)addresses Multi\-Armed Bandit \(MAB\) problems where an arm’s expected reward decays with its pull count, departing from classical stationary assumptions\. They proposed non\-parametric methods like Sliding\-Window Average and parametric approaches such as Closest To Origin for this setting\. However, their reliance on initial round\-robin exploration for decay rate estimation can be inefficient\.

Our work enhances this by introducing an Expectation\-Maximization \(EM\) algorithm, enabling simultaneous learning of decay and contextual parameters, thus circumventing the inefficient initial exploration inherent in traditional Rotting Bandit approaches\.

### 2\.4Action embeddings

Large action spaces demand efficiency and scalability\. action embeddings schemes address this by simplifying action representations\. Action embedding is vital for Off\-Policy Evaluation \(OPE\)\. Marginalized IPS \(MIPS\)Saito and Joachims \([2022](https://arxiv.org/html/2608.06750#bib.bib9)\)uses embeddings to reduce OPE variance in large action spaces, enhancing generalizability\. Furthermore, action embeddings are useful in position bias estimationIshikawaet al\.\([2024](https://arxiv.org/html/2608.06750#bib.bib20)\)\.

Our work applies action embeddings for efficiency in large LLM prompt spaces\. Further, using action embeddings within an arm\-acquiring bandit framework, we enable adaptation to new “arms” \(e\.g\., novel prompt strategies\), facilitating robust LLM optimization\.

## 3Problem Setting

We consider an arm\-acquiring contextual bandit problem with decaying rewards, where an agent’s objective is to maximize cumulative reward overTmaxT\_\{\\text\{max\}\}timesteps\. At each timesteptt, an agent selects an armi​\(t\)i\(t\)from the available set𝒜t\\mathcal\{A\}\_\{t\}according to a policyπ\\pi\. Each armi∈𝒜ti\\in\\mathcal\{A\}\_\{t\}is characterized by add\-dimensional embedding𝐞i∈ℝd\\mathbf\{e\}\_\{i\}\\in\\mathbb\{R\}^\{d\}\. We assume these arm embeddings lie within a compact subset ofℝd\\mathbb\{R\}^\{d\}, for example, a unit sphere or a hypercube\. The set of available arms𝒜t\\mathcal\{A\}\_\{t\}can dynamically expand over time \(𝒜t\+1⊇𝒜t\\mathcal\{A\}\_\{t\+1\}\\supseteq\\mathcal\{A\}\_\{t\}\) with arm acquisition\. Upon selection, the agent observes a real\-valued rewardrt∈\[0,Rmax\]r\_\{t\}\\in\[0,R\_\{\\max\}\]for someRmax\>0R\_\{\\max\}\>0\.

The observed rewardrrfor armii, after being pulledNiN\_\{i\}times, follows an exponentially decaying model:

r=μ~i⋅exp⁡\(−Ni⋅fi\)r=\\tilde\{\\mu\}\_\{i\}\\cdot\\exp\(\-N\_\{i\}\\cdot f\_\{i\}\)\(1\)whereμ~i=𝐞i⊤​𝜽\\tilde\{\\mu\}\_\{i\}=\\mathbf\{e\}\_\{i\}^\{\\top\}\\bm\{\\theta\}is the initial expected reward \(linearly modeled by a global parameter𝜽∈ℝd\\bm\{\\theta\}\\in\\mathbb\{R\}^\{d\}\), andfi=max⁡\(0,𝐞i⊤​𝐰f\)f\_\{i\}=\\max\(0,\\mathbf\{e\}\_\{i\}^\{\\top\}\\mathbf\{w\}\_\{f\}\)is the decay rate \(determined by a global decay parameter𝐰f∈ℝd\\mathbf\{w\}\_\{f\}\\in\\mathbb\{R\}^\{d\}\)\.

The agent’s ultimate objective is to find a policyπ\\pithat maximizes the cumulative reward∑t=1Tmaxrt\\sum\_\{t=1\}^\{T\_\{\\text\{max\}\}\}r\_\{t\}, equivalent to minimizing the cumulative regretR​\(Tmax\)R\(T\_\{\\text\{max\}\}\):

R​\(Tmax\)=∑t=1Tmax\(rt∗−rt\)R\(T\_\{\\text\{max\}\}\)=\\sum\_\{t=1\}^\{T\_\{\\text\{max\}\}\}\\left\(r\_\{t\}^\{\*\}\-r\_\{t\}\\right\)\(2\)Here,rt∗r\_\{t\}^\{\*\}denotes the reward from an oracle selecting the optimal arm at timestepttconsidering its current decay\.

## 4Decaying Reward Joint LinUCB \(DR\-LinUCB\)

DR\-LinUCB is the core arm selection and parameter learning algorithm\. It integrates a reward decay model and an EM algorithm into a joint linear UCB framework, where parameters are shared or learned across arms through their embeddings\. Pseudo algorithm of DR\-LinUCB is given by Algorithm 1\.

DR\-LinUCB consists of several key elements, detailed below sections\.

#### 4\.0\.1UCB Selection with Reward Decay

At each timesteptt, DR\-LinUCB selects an armi​\(t\)∈𝒜ti\(t\)\\in\\mathcal\{A\}\_\{t\}from the available arms that maximizes the following criterion:

i​\(t\)=argmaxi∈\[Kt\]⁡\(𝐞i⊤​𝜽^\+C​𝐞i⊤​𝐀−1​𝐞i\)⋅dii\(t\)=\\operatorname\{argmax\}\_\{i\\in\[K\_\{t\}\]\}\\left\(\\mathbf\{e\}\_\{i\}^\{\\top\}\\hat\{\\bm\{\\theta\}\}\+C\\sqrt\{\\mathbf\{e\}\_\{i\}^\{\\top\}\\mathbf\{A\}^\{\-1\}\\mathbf\{e\}\_\{i\}\}\\right\)\\cdot d\_\{i\}\(3\)wheredi=exp⁡\(−Ni​max⁡\(0,𝐞i⊤​𝐰f\)\)d\_\{i\}=\\exp\\left\(\-N\_\{i\}\\max\(0,\\mathbf\{e\}\_\{i\}^\{\\top\}\\mathbf\{w\}\_\{f\}\)\\right\)\.

The first term,𝐞i⊤​𝜽^\\mathbf\{e\}\_\{i\}^\{\\top\}\\hat\{\\bm\{\\theta\}\}, represents the estimated undecayed expected reward for armii, based on its embedding𝐞i\\mathbf\{e\}\_\{i\}and the globally learned parameter𝜽^\\hat\{\\bm\{\\theta\}\}\. The second term,C​𝐞i⊤​𝐀−1​𝐞iC\\sqrt\{\\mathbf\{e\}\_\{i\}^\{\\top\}\\mathbf\{A\}^\{\-1\}\\mathbf\{e\}\_\{i\}\}, is the exploration term \(UCB term\) that accounts for uncertainty, whereCCis a hyperparameter controlling the degree of exploration\. Finally, the exponential term,exp⁡\(−Ni​max⁡\(0,𝐞i⊤​𝐰f\)\)\\exp\\left\(\-N\_\{i\}\\max\(0,\\mathbf\{e\}\_\{i\}^\{\\top\}\\mathbf\{w\}\_\{f\}\)\\right\), models the decay of reward based on the number of times armiihas been pulled,NiN\_\{i\}, and its specific decay rate𝐞i⊤​𝐰f\\mathbf\{e\}\_\{i\}^\{\\top\}\\mathbf\{w\}\_\{f\}\. Themax⁡\(0,⋅\)\\max\(0,\\cdot\)operation ensures the decay factor is non\-negative\. This comprehensive criterion considers the saturation effect from excessive exploitation, thereby encouraging the algorithm to explore new arms when existing ones show diminishing returns\.

#### 4\.0\.2Expectation\-Maximization \(EM\) Algorithm for Parameter Learning

DR\-LinUCB employs an EM algorithm to simultaneously learn both the global reward model parameters𝜽^\\hat\{\\bm\{\\theta\}\}and the global decay model parameters𝐰f\\mathbf\{w\}\_\{f\}\. This approach is particularly effective for estimating the hidden variable, the undecayed rewardμ~i​\(t\)\\tilde\{\\mu\}\_\{i\(t\)\}, from the observed decayed rewardrtr\_\{t\}\.

Algorithm 1Decaying Reward Joint LinUCB \(DR\-LinUCB\)1:

𝒜0,h0,Tmax,C,λ,λf,ϵlog,ϵdecay\\mathcal\{A\}\_\{0\},h\_\{0\},T\_\{\\text\{max\}\},C,\\lambda,\\lambda\_\{f\},\\epsilon\_\{\\text\{log\}\},\\epsilon\_\{\\text\{decay\}\}
2:Initialize:

Ni=0N\_\{i\}=0for

i∈𝒜0i\\in\\mathcal\{A\}\_\{0\}
3:

𝐀=λ​𝐈d\\mathbf\{A\}=\\lambda\\mathbf\{I\}\_\{d\},

𝐛=𝟎d\\mathbf\{b\}=\\mathbf\{0\}\_\{d\},

𝜽^=𝟎d\\hat\{\\bm\{\\theta\}\}=\\mathbf\{0\}\_\{d\}
4:

𝐀f=λf​𝐈d\\mathbf\{A\}\_\{f\}=\\lambda\_\{f\}\\mathbf\{I\}\_\{d\},

𝐛f=𝟎d\\mathbf\{b\}\_\{f\}=\\mathbf\{0\}\_\{d\},

𝐰f=𝟎d\\mathbf\{w\}\_\{f\}=\\mathbf\{0\}\_\{d\}
5:for

t=1,2,…,Tmaxt=1,2,\\dots,T\_\{\\text\{max\}\}do

6:

𝒜t←𝒜t−1∪ArmGenerator​\(𝒜t−1,ht−1\)\\mathcal\{A\}\_\{t\}\\leftarrow\\mathcal\{A\}\_\{t\-1\}\\cup\\text\{ArmGenerator\}\(\\mathcal\{A\}\_\{t\-1\},h\_\{t\-1\}\)
7:

𝑬←\{Embed​\(a\)∣a∈𝒜t\}\\bm\{E\}\\leftarrow\\\{\\text\{Embed\}\(a\)\\mid a\\in\\mathcal\{A\}\_\{t\}\\\}
8:

di=exp⁡\(−Ni​max⁡\(0,𝐞i⊤​𝐰f\)\)d\_\{i\}=\\exp\\left\(\-N\_\{i\}\\max\(0,\\mathbf\{e\}\_\{i\}^\{\\top\}\\mathbf\{w\}\_\{f\}\)\\right\)
9:

i​\(t\)←argmaxi∈𝒜t⁡\(𝐞i⊤​𝜽^\+C​𝐞i⊤​𝐀−1​𝐞i\)⋅dii\(t\)\\leftarrow\\operatorname\{argmax\}\_\{i\\in\\mathcal\{A\}\_\{t\}\}\(\\mathbf\{e\}\_\{i\}^\{\\top\}\\hat\{\\bm\{\\theta\}\}\+C\\sqrt\{\\mathbf\{e\}\_\{i\}^\{\\top\}\\mathbf\{A\}^\{\-1\}\\mathbf\{e\}\_\{i\}\}\)\\cdot d\_\{i\}
10:Observe reward

rtr\_\{t\}for arm

i​\(t\)i\(t\)
11:while

𝜽^\\hat\{\\bm\{\\theta\}\},

𝐰f\\mathbf\{w\}\_\{f\}not convergeddo

12:

μ~i​\(t\)←rt/di​\(t\)\\tilde\{\\mu\}\_\{i\(t\)\}\\leftarrow r\_\{t\}/d\_\{i\(t\)\}
13:

𝜽^←\(𝐀\+𝐞i​\(t\)​𝐞i​\(t\)⊤\)−1​\(𝐛\+μ~i​\(t\)​𝐞i​\(t\)\)\\hat\{\\bm\{\\theta\}\}\\leftarrow\(\\mathbf\{A\}\+\\mathbf\{e\}\_\{i\(t\)\}\\mathbf\{e\}\_\{i\(t\)\}^\{\\top\}\)^\{\-1\}\(\\mathbf\{b\}\+\\tilde\{\\mu\}\_\{i\(t\)\}\\mathbf\{e\}\_\{i\(t\)\}\)
14:if

rt\>0r\_\{t\}\>0and

μ~i​\(t\)\>0\\tilde\{\\mu\}\_\{i\(t\)\}\>0and

rt≠μ~i​\(t\)r\_\{t\}\\neq\\tilde\{\\mu\}\_\{i\(t\)\}then

15:

y←log⁡\(μ~i​\(t\)\+ϵlog\)−log⁡\(rt\+ϵlog\)y\\leftarrow\\log\(\\tilde\{\\mu\}\_\{i\(t\)\}\+\\epsilon\_\{\\text\{log\}\}\)\-\\log\(r\_\{t\}\+\\epsilon\_\{\\text\{log\}\}\)
16:

𝐱←Ni​\(t\)​𝐞i​\(t\)\\mathbf\{x\}\\leftarrow N\_\{i\(t\)\}\\mathbf\{e\}\_\{i\(t\)\}
17:

𝐰f←\(𝐀f\+𝐱​\(𝐱\)⊤\)−1​\(𝐛f\+y​𝐱\)\\mathbf\{w\}\_\{f\}\\leftarrow\(\\mathbf\{A\}\_\{f\}\+\\mathbf\{x\}\(\\mathbf\{x\}\)^\{\\top\}\)^\{\-1\}\(\\mathbf\{b\}\_\{f\}\+y\\mathbf\{x\}\)
18:endif

19:endwhile

20:

𝐀←𝐀\+𝐞i​\(t\)​𝐞i​\(t\)⊤\\mathbf\{A\}\\leftarrow\\mathbf\{A\}\+\\mathbf\{e\}\_\{i\(t\)\}\\mathbf\{e\}\_\{i\(t\)\}^\{\\top\}
21:

𝐛←𝐛\+μ~i​\(t\)​𝐞i​\(t\)\\mathbf\{b\}\\leftarrow\\mathbf\{b\}\+\\tilde\{\\mu\}\_\{i\(t\)\}\\mathbf\{e\}\_\{i\(t\)\}
22:

𝐀f←𝐀f\+𝐱​\(𝐱\)⊤\\mathbf\{A\}\_\{f\}\\leftarrow\\mathbf\{A\}\_\{f\}\+\\mathbf\{x\}\(\\mathbf\{x\}\)^\{\\top\}
23:

𝐛f←𝐛f\+y​𝐱\\mathbf\{b\}\_\{f\}\\leftarrow\\mathbf\{b\}\_\{f\}\+y\\mathbf\{x\}
24:

ht←ht−1∪\{i​\(t\),rt\}h\_\{t\}\\leftarrow h\_\{t\-1\}\\cup\\\{i\(t\),r\_\{t\}\\\}
25:

Ni​\(t\)←Ni​\(t\)\+1N\_\{i\(t\)\}\\leftarrow N\_\{i\(t\)\}\+1
26:endfor

The E\-Step \(Line 11\) uses the current global decay model parameters𝐰f\\mathbf\{w\}\_\{f\}to*undecay*the observed rewardrtr\_\{t\}, thereby estimating the undecayed rewardμ~i​\(t\)\\tilde\{\\mu\}\_\{i\(t\)\}\. The calculation is performed asμ~i​\(t\)←rt/exp⁡\(−Ni​\(t\)⋅max⁡\(0,𝐞i​\(t\)⊤​𝐰f\)\)\\tilde\{\\mu\}\_\{i\(t\)\}\\leftarrow r\_\{t\}/\\exp\\left\(\-N\_\{i\(t\)\}\\cdot\\max\(0,\\mathbf\{e\}\_\{i\(t\)\}^\{\\top\}\\mathbf\{w\}\_\{f\}\)\\right\)\. A small constantϵdecay\\epsilon\_\{\\text\{decay\}\}is introduced for numerical stability, treating the decay rate as 1 if it’s very small\.

The M\-Step \(Lines 12\-16\) then updates the global reward model parameters𝜽^\\hat\{\\bm\{\\theta\}\}and the global decay model parameters𝐰f\\mathbf\{w\}\_\{f\}using theμ~i​\(t\)\\tilde\{\\mu\}\_\{i\(t\)\}estimated in the E\-Step\. Specifically,𝜽^\\hat\{\\bm\{\\theta\}\}is updated using standard linear ridge regression, with the undecayed rewardμ~i​\(t\)\\tilde\{\\mu\}\_\{i\(t\)\}as the target:𝜽^←\(𝐀\+𝐞i​\(t\)​𝐞i​\(t\)⊤\)−1​\(𝐛\+μ~i​\(t\)⋅𝐞i​\(t\)\)\\hat\{\\bm\{\\theta\}\}\\leftarrow\(\\mathbf\{A\}\+\\mathbf\{e\}\_\{i\(t\)\}\\mathbf\{e\}\_\{i\(t\)\}^\{\\top\}\)^\{\-1\}\(\\mathbf\{b\}\+\\tilde\{\\mu\}\_\{i\(t\)\}\\cdot\\mathbf\{e\}\_\{i\(t\)\}\)\. The decay model parameters𝐰f\\mathbf\{w\}\_\{f\}are updated by transforming the exponential decay into a linear regression problem, a process detailed in the subsequent subsection\.

### Transformation to a Linear Regression Problem for𝐰f\\mathbf\{w\}\_\{f\}Estimation

To estimate the global decay parameter𝐰f\\mathbf\{w\}\_\{f\}, the exponential decay modelrt=μ~i​\(t\)⋅exp⁡\(−Ni​\(t\)⋅\(𝐞i​\(t\)⊤​𝐰f\)\)r\_\{t\}=\\tilde\{\\mu\}\_\{i\(t\)\}\\cdot\\exp\\left\(\-N\_\{i\(t\)\}\\cdot\(\\mathbf\{e\}\_\{i\(t\)\}^\{\\top\}\\mathbf\{w\}\_\{f\}\)\\right\)is transformed into a linear regression problem\. Taking the natural logarithm of both sides yields:

log⁡\(rt\)=log⁡\(μ~i​\(t\)\)−Ni​\(t\)⋅\(𝐞i​\(t\)⊤​𝐰f\)\\displaystyle\\log\(r\_\{t\}\)=\\log\(\\tilde\{\\mu\}\_\{i\(t\)\}\)\-N\_\{i\(t\)\}\\cdot\(\\mathbf\{e\}\_\{i\(t\)\}^\{\\top\}\\mathbf\{w\}\_\{f\}\)log⁡\(μ~i​\(t\)\)−log⁡\(rt\)=Ni​\(t\)⋅\(𝐞i​\(t\)⊤​𝐰f\)\\displaystyle\\log\(\\tilde\{\\mu\}\_\{i\(t\)\}\)\-\\log\(r\_\{t\}\)=N\_\{i\(t\)\}\\cdot\(\\mathbf\{e\}\_\{i\(t\)\}^\{\\top\}\\mathbf\{w\}\_\{f\}\)\(4\)
Rearranging this equation, we define the target variabley′y^\{\\prime\}and feature vector𝐱′\\mathbf\{x\}^\{\\prime\}for a linear regression of the formy′=𝐱′⁣⊤​𝐰fy^\{\\prime\}=\\mathbf\{x\}^\{\\prime\\top\}\\mathbf\{w\}\_\{f\}:

y′=\\displaystyle y^\{\\prime\}=log⁡\(μ~i​\(t\)\+ϵlog\)−log⁡\(rt\+ϵlog\)\\displaystyle\\log\(\\tilde\{\\mu\}\_\{i\(t\)\}\+\\epsilon\_\{\\text\{log\}\}\)\-\\log\(r\_\{t\}\+\\epsilon\_\{\\text\{log\}\}\)𝐱′=\\displaystyle\\mathbf\{x\}^\{\\prime\}=Ni​\(t\)⋅𝐞i​\(t\)\\displaystyle N\_\{i\(t\)\}\\cdot\\mathbf\{e\}\_\{i\(t\)\}\(5\)
Here, for numerical stability in computation, we introduce a small positive constantϵlog≪rt,μ~i​\(t\)\\epsilon\_\{\\text\{log\}\}\\ll r\_\{t\},\\tilde\{\\mu\}\_\{i\(t\)\}, preventing issues withlog⁡\(0\)\\log\(0\)\.

The online update of𝐰f\\mathbf\{w\}\_\{f\}proceeds as follows\. First, a crucial condition is checked in Line 15: ‘Ifrt\>0r\_\{t\}\>0andμ~i​\(t\)\>0\\tilde\{\\mu\}\_\{i\(t\)\}\>0andrt≠μ~i​\(t\)r\_\{t\}\\neq\\tilde\{\\mu\}\_\{i\(t\)\}then‘\. This ensures that logarithmic transformation is valid and that actual decay has occurred, making the update meaningful\.

If the conditions are met,y′y^\{\\prime\}and𝐱′\\mathbf\{x\}^\{\\prime\}are computed using the formulas in Equations \([4](https://arxiv.org/html/2608.06750#S4.Ex2)\)\. Then we update the global decay parameter𝐰f\\mathbf\{w\}\_\{f\}through a standard online ridge regression framework \(Line 16\)\. After the loop of EM algorithm, sufficient statistics𝐀\\mathbf\{A\},𝐀f\\mathbf\{A\}\_\{f\}𝐛\\mathbf\{b\}and𝐛f\\mathbf\{b\}\_\{f\}are updated \(Lines 19\-23\), utilizing the closed\-form solutions for online ridge regressionLiet al\.\([2010](https://arxiv.org/html/2608.06750#bib.bib8)\)\.

### Application to Progressive Content Refinement

In the preceding sections, we introduced DR\-LinUCB, a versatile bandit algorithm designed for dynamic environments where rewards decay, and both arm context and decay parameters are learned using an EM algorithm\. Now, we will demonstrate how this general algorithmic framework can be specifically applied to enhance LLMs through progressive content refinement\.

We represent an LLM task as a tuple\(pinit,Evaluator​\(\)\)\(p\_\{\\text\{init\}\},\\text\{Evaluator\}\(\)\), wherepinitp\_\{\\text\{init\}\}is the original prompt that defines the LLM’s primary objective \(e\.g\., "Summarize the following article"\), andEvaluator​\(\)\\text\{Evaluator\}\(\)is a function that quantifies the quality or utility of the LLM’s output \(yty\_\{t\}\) in response to a given prompt\.

To apply DR\-LinUCB to LLM tasks, each refinement prompt is treated as an "arm" within its framework\. The process initializes𝒜0\\mathcal\{A\}\_\{0\}withpinitp\_\{\\text\{init\}\}\. In each step, theArmGeneratorfunction \(Algorithm 2\) expands the set of available arms\.

Algorithm 2ArmGenerator for Content Refinement1:functionArmGenerator\(

𝒜t−1,ht−1\\mathcal\{A\}\_\{t\-1\},h\_\{t\-1\}\)

2:if

t\>1t\>1then

ht−1←ht−1∪\{yt−1\}h\_\{t\-1\}\\leftarrow h\_\{t\-1\}\\cup\\\{y\_\{t\-1\}\\\}
3:elsereturn

\{\}\\\{\\\}
4:endif

5:

pfeedback←LLM​\(ht−1\)p\_\{\\text\{feedback\}\}\\leftarrow\\text\{LLM\}\(h\_\{t\-1\}\)
6:

pnew←LLM​\(pinit,pfeedback,ht−1\)p\_\{\\text\{new\}\}\\leftarrow\\text\{LLM\}\(p\_\{\\text\{init\}\},p\_\{\\text\{feedback\}\},h\_\{t\-1\}\)
7:return

\{pnew\}\\\{p\_\{\\text\{new\}\}\\\}
8:endfunction

This function leverages the LLM to generate a feedback promptpfeedbackp\_\{\\text\{feedback\}\}from the historyht−1h\_\{t\-1\}, and then generate a new refinement promptpnewp\_\{\\text\{new\}\}based onpinitp\_\{\\text\{init\}\},pfeedbackp\_\{\\text\{feedback\}\}, andht−1h\_\{t\-1\}\. This self\-refinement process draws inspiration fromMadaanet al\.\([2023](https://arxiv.org/html/2608.06750#bib.bib3)\)\.

Additionally, we introduce anEvoArmGeneratorthat employs EvoPromptGuoet al\.\([2025](https://arxiv.org/html/2608.06750#bib.bib16)\)as a variant of arm generator\. This evolutionary algorithm\-based strategy explores a broader, more diverse set of refinement prompts\. While self\-refinement generation can converge to local optima, evolutionary algorithms excel at systematic exploration of wider solution spaces through mutation and crossover\. This diversity is crucial for ablation studies comparing DR\-LinUCB’s learning\-based selection against simpler strategies like random selection, especially when a rich pool of diverse arms is needed\.

In Algorithm 1, the step for "Observe rewardrtr\_\{t\}" works as follows: First, the chosen prompt,i​\(t\)i\(t\), is given to the LLM, which then generates an output,yty\_\{t\}\. The rewardrtr\_\{t\}is subsequently calculated by feeding this outputyty\_\{t\}into the task’s predefinedEvaluator​\(\)\\text\{Evaluator\}\(\)function, resulting inrt←Evaluator​\(yt\)r\_\{t\}\\leftarrow\\text\{Evaluator\}\(y\_\{t\}\)\. These steps enable the application of the DR\-LinUCB framework to LLM tasks for progressive content refinement\.

### Prompt Embedding

To leverage our refinement prompts as arms within the DR\-LinUCB framework, we employ a prompt embedding strategy\. We begin by utilizing a fine\-tuned MINILMWanget al\.\([2020](https://arxiv.org/html/2608.06750#bib.bib14)\)model222[https://huggingface\.co/sentence\-transformers/all\-MiniLM\-L6\-v2](https://huggingface.co/sentence-transformers/all-MiniLM-L6-v2)to transform prompts into a high\-dimensional embedding space\. Then, we embed 200 prompts from the ‘awesome\-chatgpt\-prompts‘333[https://huggingface\.co/datasets/fka/awesome\-chatgpt\-prompts](https://huggingface.co/datasets/fka/awesome-chatgpt-prompts)dataset into this space\. Following this, we apply Principal Component Analysis \(PCA\)Maćkiewicz and Ratajczak \([1993](https://arxiv.org/html/2608.06750#bib.bib13)\)to these embeddings to reduce their dimensionality, obtaining a 5\-dimensional principal component vector\. In this research, we leverage this fine\-tuned sentence transformer model and the trained PCA model to embed new prompts and compress their dimensions before use in our bandit algorithm\.

Table 1:Performance summary \(mean±\\pmstandard deviation\) for each task, algorithm, and model\. Metrics are defined in Section 5\.

## 5Evaluation

We study two different domains that each involve complex natural language reasoning and generation\.

1. 1\.Math Reasoning: GSM8K \(Grade School Math 8k\)Cobbeet al\.\([2021](https://arxiv.org/html/2608.06750#bib.bib17)\)is a challenging dataset of elementary\-level math word problems\. The task is to read a natural\-language problem description and generate a step\-by\-step solution, involving numerical calculations and logical reasoning, to find the final numerical answer\. It assesses a model’s multi\-step mathematical reasoning and its ability to convert linguistic information into a solvable procedure\. As a metric, we report the average success rate\. A "success" is defined as generating the exact numerical answer defined in the dataset\.
2. 2\.Sentiment Reversal: Sentiment Reversal is a long\-form text style transfer taskMadaanet al\.\([2023](https://arxiv.org/html/2608.06750#bib.bib3)\); Zhanget al\.\([2015](https://arxiv.org/html/2608.06750#bib.bib18)\)\. Given a text passage with a specific sentiment \(e\.g\., negative\), the goal is to rewrite the entire passage to a target sentiment \(e\.g\., very positive\), not merely reversing it\. This task evaluates a model’s ability for fine\-grained content editing, requiring not only a complete shift in emotional tone but also an adjustment of sentiment intensity\. It necessitates understanding the original meaning and tone, and then systematically altering vocabulary, phrasing, and narrative to achieve the specified opposing sentiment and intensity while maintaining coherence\. As a metric, we report the average scores\. We first calculate the sentiment using a ModernBert\-based Multilingual Sentiment Classification Modeltabularisaiet al\.\([2025](https://arxiv.org/html/2608.06750#bib.bib15)\)\. If the predicted sentiment matches the target sentiment, a score of 1\.0 is assigned\. Otherwise, we employ an LLM as a judge to calculate a score reflecting the alignment of the generated text’s sentiment to the target\. The LLM model version used for judging in each experiment matches the version employed within that experiment\.

We use these tasks to study following research questions:

RQ1:Can iterative\-refinement achieve higher performance than a single\-call strategy?

RQ2:Canreward decayreduce over\-exploitation and contribute to total performance?

RQ3:Doesreward decayaccelerate the convergence and performance improvement of iterative refinement?

RQ4:Which approach provides better performance: ArmGenerator or EvoArmGenerator?

RQ5:Does the combination of joint LinUCB and reward decay achieve superior overall performance?

To investigate these questions, we study a range of baselines:

- •Single Call: LLM output from initial prompt only\. Serves as a performance lower bound\.
- •Random Exploration: UsesEvoArmGeneratorbut selects prompts uniformly at random\. Evaluates the benefit of learning over pure exploration\.
- •JointLinUCB: UsesEvoArmGeneratorand LinUCB for prompt selection, but assumes stationary rewards, lacking decay modeling\. Isolates decay’s contribution\.
- •EvoLinUCB: This is a variant of the DR\-LinUCB method that usesEvoArmGenerator\. This approach offers diverse prompt generation, but unlike theArmGenerator, it does not use LLM feedback during generation\.
- •Self\-RefineMadaanet al\.\([2023](https://arxiv.org/html/2608.06750#bib.bib3)\): Iterative refinement where LLM generates feedback and prompts\. The prompt selection is greedy, typically choosing the latest generated prompt without adaptive learning\. This corresponds to repeatedArmGeneratoruse without sophisticated selection\.
- •REx\(REfine, Explore, Exploit\)Tanget al\.\([2024](https://arxiv.org/html/2608.06750#bib.bib5)\): Uses Thompson Sampling for content refinement\. The refinement prompt is fixed, unlike our dynamic prompt selection\.

For each experiment, we evaluated the models on 100 distinct samples for each of three random seeds\. The reported results are averaged over these three independent runs, effectively evaluating performance on a total of 300 samples for each task and algorithm\. For each sample, algorithm has up to six time steps\.

### The Value of Iterative LLM Interaction

The comparison between Single Call and Random Exploration in Table[1](https://arxiv.org/html/2608.06750#S4.T1)demonstrates that multi\-step iterative processes significantly enhance performance\.

The Single Call baseline consistently yields the lowest scores\. For instance, in GSM8K with ChatGPT3\.5\-turbo, Single Call scored 0\.187\. In contrast, Random Exploration shows a substantial improvement\. For the same task, "Random Exploration" achieves 0\.310, an approximate 65% increase over Single Call\.

This clearly indicates that engaging the LLM in a multi\-step iterative process leads to significant performance improvement over a single\-shot approach\. This observation answers RQ1, confirming that iterative LLM usage, even in its most basic form, yields higher performance than a single call strategy\. It underscores the fundamental value of employing LLMs iteratively to refine and optimize their outputs\.

### DR\-LinUCB Outperforms Baselines and SOTA

The results in Table[1](https://arxiv.org/html/2608.06750#S4.T1)demonstrates that our proposed DR\-LinUCB consistently achieves superior performance against both our ablation study baselines and state\-of\-the\-art \(SOTA\) methods like Self\-Refine and REx\.

Specifically, with ChatGPT3\.5\-turbo, DR\-LinUCB leads in both GSM8K \(0\.7900\.790\) and Sentiment Inverse \(0\.9520\.952\), significantly surpassing Self\-Refine \(0\.6870\.687for GSM8K,0\.8790\.879for Sentiment Inverse\) and REx \(0\.5300\.530for GSM8K,0\.9310\.931for Sentiment Inverse\)\. This highlights DR\-LinUCB’s capability in enhancing less powerful LLMs\. With ChatGPT4o, DR\-LinUCB achieves0\.9000\.900for GSM8K, outperforming REx \(0\.8800\.880\) and closely trailing Self\-Refine \(0\.9130\.913\)\. In particular, for Sentiment Inverse with ChatGPT4o, DR\-LinUCB achieves a perfect score of1\.0001\.000, outperforming all other methods\. We further discuss the feasibility and implications of this perfect score in Section 6\.

These results unequivocally answer RQ5\. The integration of these mechanisms allows DR\-LinUCB to effectively learn optimal prompt arms while preventing over\-exploitation, leading to robust and often best\-in\-class performance\.

![Refer to caption](https://arxiv.org/html/2608.06750v1/score_history_combined_sentiment_reversal.png)Figure 2:History of average scores in the Sentiment Reversal Task for ChatGPT\-3\.5 Turbo \(top\) and ChatGPT\-4o \(bottom\)\. EvoLinUCB incorporates both arm decay and arm learning, while JointLinUCB only features arm learning\. Random Exploration uniformly selects arms generated by EvoArmGenerator\. Only instances not correctly answered in the first attempt are included, allowing for a comparison of iterative improvement effects\. The shaded area indicates the standard error from three experimental runs\.
### Addressing RQ2 and RQ3: Insights from Algorithmic Component Analysis

To ensure consistent conditions for prompt generation, our comparison focuses on three models that utilize the EvoPrompt Generator\. Furthermore, only instances answered incorrectly in the first attempt are included to allow a comparison of iterative improvement effects\.

As depicted in Figure[2](https://arxiv.org/html/2608.06750#S5.F2), all three algorithms show comparable improvements up to the second iteration\. However, from the third iteration onwards, EvoLinUCB consistently outperforms the others for both ChatGPT\-3\.5 Turbo and ChatGPT\-4o\. This superior performance of EvoLinUCB can be attributed to its incorporation of both reward decay and arm learning\.

In particular, JointLinUCB performs worse than Random Exploration in the case of ChatGPT\-4o\. This observation supports our hypothesis that mechanisms preventing over\-exploitation, like EvoLinUCB’s decay or Random Exploration, improve effectiveness over solely exploiting estimated "good" arms\. This finding directly addresses RQ2, indicating that reward decay effectively mitigates over\-exploitation, leading to enhanced performance\.

Moreover, by observing the score history, we can see that the scores converge relatively quickly\. This rapid convergence provides an answer to RQ3, suggesting that effective improvements can be achieved within a limited number of iterative steps\.

### Suitability of Arm Generation Approaches

DR\-LinUCB \(withArmGenerator\) significantly outperforms EvoLinUCB in Sentiment Inverse \(0\.9520\.952vs\.0\.9440\.944with GPT\-3\.5\) and achieves a substantial gain in GSM8K over JointLinUCB \(0\.7900\.790vs\.0\.3230\.323\)\. These results suggest that feedback\-driven prompt exploration is generally more effective than evolutionary modification\.

However, this effectiveness is task\-dependent; while Self\-Refine excels in GSM8K with GPT\-4o \(0\.9130\.913\), it underperforms JointLinUCB in Sentiment Inverse, likely because iterative correction can introduce noise or suboptimal steering in simpler tasks\. We conclude thatArmGeneratoris most robust when integrated with exploration\-exploitation strategies\.

## 6Conclusion

This paper introduces Decaying Reward Joint LinUCB \(DR\-LinUCB\), a novel bandit algorithm designed for iterative LLM content refinement\. DR\-LinUCB explicitly models the "saturation effect" through reward decay and jointly learns contextual and decay parameters\. Our experiments on GSM8K and Sentiment Reversal tasks demonstrate DR\-LinUCB’s superior performance compared to various baselines and state\-of\-the\-art methods\. We confirmed that incorporating reward decay effectively prevents over\-exploitation, leading to enhanced performance and accelerated convergence\.

DR\-LinUCB offers a significant advancement in optimizing LLM iterative refinement, providing a principled approach to balance exploration and exploitation in dynamic environments where the utility of refinement strategies can diminish over time\.

## 7Limitations

While our proposed DR\-LinUCB framework shows promising results, several limitations remain to be addressed in future work\.

##### Feasibility of Score 1\.0 in Sentiment Reversal Task

Historically, LLMs have struggled to achieve 100% accuracy on simple tasks, largely due to inherent flaws in existing benchmarks\. The Platinum benchmarkVendrowet al\.\([2025](https://arxiv.org/html/2608.06750#bib.bib12)\)demonstrates that many benchmarks contain significant errors; for instance, in SVAMPPatelet al\.\([2021](https://arxiv.org/html/2608.06750#bib.bib11)\), a question was mislabeled with an incorrect solution\. In contrast, our sentiment reversal task evaluates performance using a pretrained sentiment analysis model and an LLM judge, effectively eliminating the issue of mislabeled ground truth\.

While the task is relatively simple—with even the Self\-Refine model achieving a high score of 0\.989—the fact that 100% accuracy is achievable aligns with the findings of the Platinum Benchmarks paper regarding carefully curated tasks\. However, it remains a limitation that our current evaluation is focused on this feasible task, and further validation on more complex benchmarks where 100% accuracy is not yet reachable is required\.

##### Minimizing Cost of LLM Interactions

The iterative nature of our approach, combined with multiple LLM calls for ArmGenerator and reward evaluation within each timestep, can lead to significant computational overhead and increased API costs\. In real\-world, high\-throughput scenarios, the latency and expenses associated with these repeated inferences could be limiting factors\. While our reward decay model implicitly helps minimize unnecessary calls by discouraging the over\-exploitation of ineffective prompts, the framework is not yet explicitly optimized for this purpose\. Future research should investigate how to leverage decay modeling more strategically to reduce the total number of LLM interactions required, improving overall cost\-effectiveness\.

##### Sensitivity to Hyperparameters

Like many bandit algorithms, DR\-LinUCB relies on hyperparameters such asCC,λ\\lambda,λf\\lambda\_\{f\},ϵlog\\epsilon\_\{\\text\{log\}\}, andϵdecay\\epsilon\_\{\\text\{decay\}\}\. The performance of the algorithm can be sensitive to the tuning of these parameters\. While we have identified effective settings for our specific tasks, optimal tuning for diverse LLM applications might require extensive experimentation\. The development of adaptive or self\-tuning mechanisms for these hyperparameters remains an important direction to enhance the robustness and ease of use of DR\-LinUCB\.

## References

- Bandit\-based prompt design strategy selection improves prompt optimizers\.InFindings of the Association for Computational Linguistics: ACL 2025,W\. Che, J\. Nabende, E\. Shutova, and M\. T\. Pilehvar \(Eds\.\),Vienna, Austria,pp\. 20799–20817\.External Links:[Link](https://aclanthology.org/2025.findings-acl.1070/),[Document](https://dx.doi.org/10.18653/v1/2025.findings-acl.1070),ISBN 979\-8\-89176\-256\-5Cited by:[§1](https://arxiv.org/html/2608.06750#S1.p2.1),[§2\.2](https://arxiv.org/html/2608.06750#S2.SS2.p3.1)\.
- T\. Brown, B\. Mann, and e\. al\. Ryder \(2020\)Language models are few\-shot learners\.InAdvances in Neural Information Processing Systems,e\. al\. H\. Larochelle \(Ed\.\),Vol\.33,pp\. 1877–1901\.External Links:[Link](https://proceedings.neurips.cc/paper_files/paper/2020/file/1457c0d6bfcb4967418bfb8ac142f64a-Paper.pdf)Cited by:[§1](https://arxiv.org/html/2608.06750#S1.p1.1)\.
- P\. Chen, Z\. Guo, B\. Haddow, and K\. Heafield \(2024\)Iterative translation refinement with large language models\.InProceedings of the 25th Annual Conference of the European Association for Machine Translation \(Volume 1\),C\. Scarton, C\. Prescott, C\. Bayliss, C\. Oakley, J\. Wright, S\. Wrigley, X\. Song, E\. Gow\-Smith, R\. Bawden, V\. M\. Sánchez\-Cartagena, P\. Cadwell, E\. Lapshinova\-Koltunski, V\. Cabarrão, K\. Chatzitheodorou, M\. Nurminen, D\. Kanojia, and H\. Moniz \(Eds\.\),Sheffield, UK,pp\. 181–190\.External Links:[Link](https://aclanthology.org/2024.eamt-1.17/)Cited by:[§2\.1](https://arxiv.org/html/2608.06750#S2.SS1.p1.1)\.
- H\. W\. Chung, L\. Hou, and e\. al\. Longpre \(2024\)Scaling instruction\-finetuned language models\.J\. Mach\. Learn\. Res\.25\(1\)\.External Links:ISSN 1532\-4435Cited by:[§1](https://arxiv.org/html/2608.06750#S1.p1.1)\.
- K\. Cobbe, V\. Kosaraju, M\. Bavarian, M\. Chen, H\. Jun, L\. Kaiser, M\. Plappert, J\. Tworek, J\. Hilton, R\. Nakano, C\. Hesse, and J\. Schulman \(2021\)Training verifiers to solve math word problems\.arXiv preprint arXiv:2110\.14168\.Cited by:[item 1](https://arxiv.org/html/2608.06750#S5.I1.i1.p1.1)\.
- Q\. Guo, R\. Wang, J\. Guo, B\. Li, K\. Song, X\. Tan, G\. Liu, J\. Bian, and Y\. Yang \(2025\)EvoPrompt: connecting llms with evolutionary algorithms yields powerful prompt optimizers\.External Links:2309\.08532,[Link](https://arxiv.org/abs/2309.08532)Cited by:[§4](https://arxiv.org/html/2608.06750#S4.SSx2.p5.1)\.
- D\. Hein, A\. Christie, M\. Holcomb, B\. Xie, A\. Jain, J\. Vento, N\. Rakheja, A\. H\. Shakur, S\. Christley, L\. G\. Cowell, J\. Brugarolas, A\. R\. Jamieson, and P\. Kapur \(2025\)Iterative refinement and goal articulation to optimize large language models for clinical information extraction\.npj Digital Medicine8\(1\),pp\. 301\.External Links:[Document](https://dx.doi.org/10.1038/s41746-025-01686-z),[Link](https://doi.org/10.1038/s41746-025-01686-z)Cited by:[§1](https://arxiv.org/html/2608.06750#S1.p1.1),[§2\.1](https://arxiv.org/html/2608.06750#S2.SS1.p1.1)\.
- S\. Ishikawa, Y\. C\. Liu, Y\. Chung, and Y\. Hirate \(2024\)Position bias estimation with item embedding for sparse dataset\.InCompanion Proceedings of the ACM Web Conference 2024,WWW ’24,New York, NY, USA,pp\. 895–898\.External Links:ISBN 9798400701726,[Link](https://doi.org/10.1145/3589335.3651546),[Document](https://dx.doi.org/10.1145/3589335.3651546)Cited by:[§2\.4](https://arxiv.org/html/2608.06750#S2.SS4.p1.1)\.
- N\. Levine, K\. Crammer, and S\. Mannor \(2017\)Rotting bandits\.InProceedings of the 31st International Conference on Neural Information Processing Systems,NIPS’17,Red Hook, NY, USA,pp\. 3077–3086\.External Links:ISBN 9781510860964Cited by:[§1](https://arxiv.org/html/2608.06750#S1.p3.1),[§2\.3](https://arxiv.org/html/2608.06750#S2.SS3.p1.1)\.
- L\. Li, W\. Chu, J\. Langford, and R\. E\. Schapire \(2010\)A contextual\-bandit approach to personalized news article recommendation\.InProceedings of the 19th International Conference on World Wide Web,WWW ’10,New York, NY, USA,pp\. 661–670\.External Links:ISBN 9781605587998,[Link](https://doi.org/10.1145/1772690.1772758),[Document](https://dx.doi.org/10.1145/1772690.1772758)Cited by:[§1](https://arxiv.org/html/2608.06750#S1.p5.1),[§4](https://arxiv.org/html/2608.06750#S4.SSx1.p7.7)\.
- A\. Maćkiewicz and W\. Ratajczak \(1993\)Principal components analysis \(pca\)\.Computers & Geosciences19\(3\),pp\. 303–342\.External Links:ISSN 0098\-3004,[Document](https://dx.doi.org/https%3A//doi.org/10.1016/0098-3004%2893%2990090-R),[Link](https://www.sciencedirect.com/science/article/pii/009830049390090R)Cited by:[§4](https://arxiv.org/html/2608.06750#S4.SSx3.p1.1)\.
- A\. Madaan, N\. Tandon, and e\. al\. Gupta \(2023\)SELF\-refine: iterative refinement with self\-feedback\.InProceedings of the 37th International Conference on Neural Information Processing Systems,NIPS ’23,Red Hook, NY, USA\.Cited by:[§1](https://arxiv.org/html/2608.06750#S1.p1.1),[§1](https://arxiv.org/html/2608.06750#S1.p2.1),[§1](https://arxiv.org/html/2608.06750#S1.p3.1),[§2\.1](https://arxiv.org/html/2608.06750#S2.SS1.p1.1),[§4](https://arxiv.org/html/2608.06750#S4.SSx2.p4.6),[item 2](https://arxiv.org/html/2608.06750#S5.I1.i2.p1.1),[5th item](https://arxiv.org/html/2608.06750#S5.I2.i5.p1.1)\.
- T\.K\. Moon \(1996\)The expectation\-maximization algorithm\.IEEE Signal Processing Magazine13\(6\),pp\. 47–60\.External Links:[Document](https://dx.doi.org/10.1109/79.543975)Cited by:[§1](https://arxiv.org/html/2608.06750#S1.p6.1)\.
- A\. Patel, S\. Bhattamishra, and N\. Goyal \(2021\)Are NLP models really able to solve simple math word problems?\.InProceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies,Online,pp\. 2080–2094\.External Links:[Link](https://aclanthology.org/2021.naacl-main.168),[Document](https://dx.doi.org/10.18653/v1/2021.naacl-main.168)Cited by:[§7](https://arxiv.org/html/2608.06750#S7.SS0.SSS0.Px1.p1.1)\.
- Y\. Saito and T\. Joachims \(2022\)Off\-policy evaluation for large action spaces via embeddings\.External Links:2202\.06317,[Link](https://arxiv.org/abs/2202.06317)Cited by:[§2\.4](https://arxiv.org/html/2608.06750#S2.SS4.p1.1)\.
- tabularisai, S\. Gyamfi, V\. Borisov, and R\. H\. Schreiber \(2025\)Multilingual\-sentiment\-analysis \(revision 69afb83\)\.Hugging Face\.External Links:[Link](https://huggingface.co/tabularisai/multilingual-sentiment-analysis),[Document](https://dx.doi.org/10.57967/hf/5968)Cited by:[item 2](https://arxiv.org/html/2608.06750#S5.I1.i2.p2.1)\.
- H\. Tang, K\. Hu, J\. P\. Zhou, S\. Zhong, W\. Zheng, X\. Si, and K\. Ellis \(2024\)Code repair with llms gives an exploration\-exploitation tradeoff\.InProceedings of the 38th International Conference on Neural Information Processing Systems,NIPS ’24,Red Hook, NY, USA\.External Links:ISBN 9798331314385Cited by:[§1](https://arxiv.org/html/2608.06750#S1.p2.1),[§2\.2](https://arxiv.org/html/2608.06750#S2.SS2.p2.1),[6th item](https://arxiv.org/html/2608.06750#S5.I2.i6.p1.1)\.
- W\. R\. Thompson \(1933\)On the likelihood that one unknown probability exceeds another in view of the evidence of two samples\.Biometrika25\(3/4\),pp\. 285–294\.External Links:ISSN 00063444,[Link](http://www.jstor.org/stable/2332286)Cited by:[§2\.2](https://arxiv.org/html/2608.06750#S2.SS2.p3.1)\.
- J\. Vendrow, E\. Vendrow, S\. Beery, and A\. Madry \(2025\)Do large language model benchmarks test reliability?\.External Links:2502\.03461,[Link](https://arxiv.org/abs/2502.03461)Cited by:[§7](https://arxiv.org/html/2608.06750#S7.SS0.SSS0.Px1.p1.1)\.
- W\. Wang, F\. Wei, L\. Dong, H\. Bao, N\. Yang, and M\. Zhou \(2020\)MINILM: deep self\-attention distillation for task\-agnostic compression of pre\-trained transformers\.InProceedings of the 34th International Conference on Neural Information Processing Systems,NIPS ’20,Red Hook, NY, USA\.External Links:ISBN 9781713829546Cited by:[§4](https://arxiv.org/html/2608.06750#S4.SSx3.p1.1)\.
- X\. Zhang, J\. Zhao, and Y\. LeCun \(2015\)Character\-level convolutional networks for text classification\.InProceedings of the 29th International Conference on Neural Information Processing Systems \- Volume 1,NIPS’15,Cambridge, MA, USA,pp\. 649–657\.Cited by:[item 2](https://arxiv.org/html/2608.06750#S5.I1.i2.p1.1)\.

## 8Appendix

### 8\.1Implementation Details

This appendix provides a comprehensive overview of the experimental setup and specific hyperparameter configurations used in our study to ensure reproducibility\.

#### 8\.1\.1Hardware and Software Environment

All experiments were conducted on a MacBook Pro \(13\-inch, 2020\) equipped with a 1\.7 GHz Quad\-Core Intel Core i7 processor, Intel Iris Plus Graphics 645 \(1536 MB\), and 16 GB of 2133 MHz LPDDR3 memory\. For the LLM interactions, we used OpenAI’s API and client library\.

#### 8\.1\.2Hyperparameters

The specific hyperparameters used for each algorithm are detailed below\.

- •DR\-LinUCB:For the DR\-LinUCB algorithm, we set the maximum number of iterations tomax\_itr=5, and the early stopping score toearly\_stop\_score=1\.0\.The number of iterations for parameter learning wasT\_em=2\. The dimension of the context vector wasd\_dim=5, and the constant for the confidence bound wasC\_constant=0\.5\. Regularization parameters were set tolambda\_theta=0\.1andlambda\_wf=0\.1\. Small epsilon values for logarithmic and decay calculations wereepsilon\_log\_val=1×10−61\\times 10^\{\-6\}andepsilon\_decay\_val=1×10−61\\times 10^\{\-6\}respectively\.
- •Rex:The Rex algorithm utilized a confidence parameterC=20\.0, a maximum ofmax\_llm\_calls=5to the LLM, and an early stopping score ofearly\_stop\_score=1\.0\.
- •Self\-Refine:For the Self\-Refine process, we configuredmax\_iterations=5and anearly\_stop\_score=1\.

### 8\.2Prompts

#### 8\.2\.1GSM8K

For the GSM8K \(Grade School Math 8K\) task, we employ a similar multi\-stage prompting framework designed to enhance the accuracy and robustness of problem\-solving\. This framework consists of an initial generation prompt, a feedback generation prompt, and a refinement prompt, iteratively improving the mathematical reasoning\.

#### 8\.2\.2Initial Problem Solving Prompt

The first stage aims to generate an initial solution to the mathematical word problem\. The prompt guides the LLM to provide a detailed Chain\-of\-Thought \(CoT\) before stating the final answer:

Listing 1:Initial Problem Solving PromptSolvethefollowingmathematicalwordproblem\.Outputthefinalansweronlyaftershowingyourdetailedstep\-by\-stepreasoning\(Chain\-of\-Thought\)\.

Question:\{question\}

Answer:

This prompt instructs the LLM to solve the given ‘question‘ by first producing a step\-by\-step reasoning process, followed by the final numerical answer\.

#### 8\.2\.3Feedback Generation Prompt

After the initial solution attempt, a critical feedback stage is introduced\. This prompt directs the LLM to act as a reviewer, identifying potential issues in the generated reasoning without revealing the correct answer:

Listing 2:Feedback Generation PromptReviewthegivenmathematicalwordproblemandthecurrentreasoning/answer\.Providedetailed,step\-by\-stepfeedbackfocusedonidentifyingpotentialcalculationerrors,logicalflaws,ormisinterpretationsofthequestion\.Donotstatethefinalanswer\.Currentreasoning/answer:

The LLM is tasked with providing constructive feedback on the ‘current reasoning/answer‘, specifically looking for ‘calculation errors‘, ‘logical flaws‘, or ‘misinterpretations‘ of the problem\. A crucial directive is to ‘not state the final answer‘, ensuring the feedback mechanism does not directly provide the solution\.

Refinement Prompt The refinement stage utilizes the generated feedback and the history of previous attempts to iteratively improve the solution\. This prompt is designed to guide the LLM towards a correct and well\-structured answer:

Listing 3:Refinement Prompt\*\*\[RefinementTask:MathWordProblem\(GSM8K\)\]\*\*

\*\*Question:\*\*\{question\}

Reviewtheprovidedquestion,thepreviousattemptsatsolvingit,andthedetailedfeedbackhistory\.Yourtaskisto\*\*refinetheentirereasoningchainandthefinalanswer\*\*\.

\*\*RefinementDirectives:\*\*

\*\*\*CalculationAccuracy:\*\*Strictlyre\-checkeveryarithmeticstep\.Identifyandcorrectanycalculationerrors\(miscounts,incorrectmultiplication/division,etc\.\)\.

\*\*\*LogicalConsistency:\*\*VerifythelogicalflowoftheChain\-of\-Thought\(CoT\)\.Ensureeachstepisderivedcorrectlyfromthepreviousoneandalignswiththequestion’spremise\.

\*\*\*AnswerFormat:\*\*Aftertherefinedstep\-by\-stepreasoning,outputthefinalnumericalanswerclearly\.Thefinaloutputmustconcludewiththephrase:\*\*’Thefinalansweris\[NUMBER\]’\*\*\.

\*\*HistoryofAttemptsandFeedback:\*\*

\-\-\-

\{history\}

\-\-\-

\*\*RefinedReasoningandFinalAnswer:\*\*

This comprehensive refinement prompt explicitly defines the task as ‘\[Refinement Task: Math Word Problem \(GSM8K\)\]‘ and provides specific ‘Refinement Directives‘\. These directives guide the LLM to focus on ‘Calculation Accuracy‘, ‘Logical Consistency‘ of the Chain\-of\-Thought \(CoT\), and ‘Answer Format‘\. It emphasizes the need to re\-check all arithmetic steps and ensure the logical flow aligns with the ‘question‘’s premise\. Crucially, it mandates a specific output format for the final answer:’The final answer is \[NUMBER\]’\. The prompt also incorporates a ‘History of Attempts and Feedback‘, allowing the LLM to learn from past errors and improve its reasoning iteratively\.

#### 8\.2\.4Sentiment Reversal

Our approach to sentiment reversal leverages a multi\-stage prompting strategy with a Large Language Model \(LLM\)\. This strategy involves an initial sentiment inversion prompt, a feedback generation prompt, and a refinement prompt, designed to iteratively improve the quality and accuracy of the inverted review\.

#### 8\.2\.5Initial Sentiment Inversion Prompt

The first stage involves generating an initial inverted review\. The prompt is structured to clearly instruct the LLM on the primary task:

Listing 4:Initial Sentiment Inversion PromptInvertthesentimentofthefollowingreview\.

OriginalReview:\{original\_review\_text\}

InvertedReview:

This prompt directly asks the LLM to perform the sentiment reversal on the providedoriginal\_review\_textand to output theInverted Review\.

#### 8\.2\.6Feedback Generation Prompt

Following the initial inversion, a feedback mechanism is employed to evaluate the generated inverted review\. This feedback is crucial for guiding subsequent refinements\. The prompt for generating feedback is as follows:

Listing 5:Feedback Generation PromptReviewthegivenoriginalreview\(\{original\_review\_text\}\.\.\.\)andthecurrentinvertedreview\.

Provideconcretesuggestionsforimprovement,focusingonwhetherthesentimentisproperly

invertedandiftheexpressionisnatural\.

ConsidertheOriginalSentiment:\{original\_sentiment\}andtheTargetSentiment:\{target\\\_sentiment\}\.

Currentinvertedreview:

This prompt instructs the LLM to act as a critic, providing constructive feedback\. It explicitly asks for suggestions focusing on sentiment inversion accuracy and naturalness of expression, taking into account theoriginal\_sentimentand the desiredtarget\_sentiment\.

#### 8\.2\.7Refinement Prompt

The final stage utilizes the feedback to refine the inverted review\. This iterative refinement process aims to converge on a high\-quality, sentiment\-inverted text\. The refinement prompt is designed to guide the LLM through this process:

Listing 6:Refinement PromptPleasereturnonlyinvertedreviewsanddon’treturnsuggestions\.

ForthetaskofinvertingthesentimentoftheOriginalReview:\{original\\\_review\\\_text\}\.\.\.,

refinethereviewbasedonthehistoryofpreviousinvertedreviewsandfeedback\.

Considerallprovidedfeedbackandensuretherefinedtexthasa\{target\\\_sentiment\}sentiment\.

Currentsentimentis\{self\.sentiment\}\.

ifsentimentisnotenough\(e\.g\.,targetisverypositiveiscurrentispositive\),

changesentimentpolarityandchangeIntensifiers/Amplifiers

Pleaseconsidercurrenthistory:

This prompt emphasizes that the LLM should only output the refined inverted review, without additional suggestions\. It directs the LLM to leverage thehistory of previous inverted reviews and feedbackto ensure the refined text aligns with thetarget\_sentiment\. It also provides explicit instructions for cases where the current sentiment is not sufficiently strong, suggesting the modification of sentiment polarity and the use of intensifiers/amplifiers, thereby promoting more robust sentiment manipulation\. The prompt also implicitly references an internalself\.sentimentvariable and encourages consideration of thecurrent historyof refinements\.

#### 8\.2\.8Prompts for generating arms

#### 8\.2\.9EvoArmGenerator

This meta\-prompt guides the Large Language Model \(LLM\) to perform evolutionary operations \(mutation and crossover\) on a target prompt\. It leverages information from three "donor" prompts and an experimental history to create a refined prompt\. The process is designed to optimize existing prompts while preserving their core objective\.

Listing 7:EvoArmGeneratorYouareanexpertpromptoptimizer\.Yourtaskistoperformanevolutionaryoperation

onthetargetpromptusingthreedonorprompts\.

1\.IdentifythekeyelementsandstyledifferencesbetweenDonor1andDonor2\.

Donor1\(Pr1\):\{donor1\_prompt\}

Donor2\(Pr2\):\{donor2\_prompt\}

2\.Mutatethedifferentparts,consideringthehistoryofexperiment:\{history\}

3\.CombinethedifferentpartswithPrompt3,selectivelyreplaceitwiththedifferentpartsinStep2andgenerateanewprompt\.Don’tuseDonar1andDoner2aspronoun

4\.CrossoverthepromptintheStep3withthefollowingbasicpromptandgenerateafinalpromptbracketedwith<prompt\>and</prompt\>

5\.Donotbreakoriginalgoal\(ifit’smathmaticalcalculation,don’tmutatenumberandformula\)\.Mutateexpressionandapproachtoaccomlishoriginalgoal\.

6\.Whenmutating,simplifypromptaswell\(especiallyformathmaticalcalculation\)

The LLM, acting as an "expert prompt optimizer," is instructed to analyze the stylistic and elemental differences between ‘donor1\_prompt‘ and ‘donor2\_prompt‘\. It then mutates relevant parts based on the ‘history‘ of experiments, combines these with an implicit "Prompt 3," and performs a crossover operation with a "basic prompt\." Critical directives include maintaining the ‘original goal‘ \(e\.g\., preserving numerical values and formulas in mathematical calculations\) while focusing on mutating ‘expression and approach‘\. Additionally, simplification of the prompt during mutation is encouraged, particularly for mathematical tasks\. The final output prompt is required to be enclosed within ‘<prompt\>‘ and ‘</prompt\>‘ tags\.

#### 8\.2\.10History\-Based Novel Prompt Generator \(ArmGenerator\)

This meta\-prompt aims to generate entirely new prompts that fundamentally deviate from previous solutions, ensuring novelty while strictly adhering to the original task’s objective\. It leverages the full ‘Experiment History‘ to strategically guide the LLM towards innovative approaches\.

Listing 8:ArmGeneratorYouareaseasonedstrategistoverseeingpromptevolution\.Forthegiven"originalprompt,"leveragethefollowinghistoricalinformationtoitsfullestextentandgeneratea\*\*novelpromptthatdistinctlydeviatesfrompreviousapproaches\*\*\.

ExperimentHistory:\{history\}

Instructionsforgeneratingthenewprompt:

1\.\*\*FundamentalShiftinApproach\*\*:Deeplyanalyzethehistoryaboveanddeviseacompletelynewapproachthatintentionallydepartsfromtheexpressions,structures,orthoughtpatternsadoptedinpreviousattempts\.

2\.\*\*AbsoluteMaintenanceofGoal\*\*:Theultimategoaldefinedbytheoriginalprompt,includingspecificnumbers,formulas,ordatainmathematicalcalculations,mustnotbealteredforanyreason\.Thesemustbeentirelypreservedinthenewprompt\.

3\.\*\*RefinementandSimplificationofExpression\*\*:Thenewapproachshouldbemorerefinedandconcisetoachievetheoriginalgoal\.Especiallyincasesinvolvingcomplexcalculationsorlogic,eliminateredundancyandpursuethemostefficientandclearexpressionpossible\.

4\.Generateafinalpromptbracketedwith<prompt\>and</prompt\>

Acting as a "seasoned strategist," the LLM is tasked with generating a ‘novel prompt‘ that ‘distinctly deviates from previous approaches‘ by thoroughly analyzing the ‘Experiment History‘\. The core instructions emphasize a ‘Fundamental Shift in Approach‘, meaning a deliberate departure from past expressions, structures, or thought patterns\. Despite this push for novelty, the ‘Absolute Maintenance of Goal‘ is paramount, ensuring that critical elements like numbers and formulas in mathematical contexts remain unchanged\. Furthermore, the new approach should exhibit ‘Refinement and Simplification of Expression‘, eliminating redundancy and promoting efficiency, especially for complex tasks\. As with the evolutionary prompt, the final output must be enclosed within<p​r​o​m​p​t\><prompt\>and</prompt\></prompt\>tags\.