When Greedy Wins: Emergent Exploitation Bias in Meta-Bandit LLM Training
Authors: Sanxing Chen
Xiaoyin Chen
Yukun Huang
Roy Xie
Bhuwan Dhingra
Venue: ICLR 2026 Poster (2026)
Keywords: Large Language Model
Exploration
Primary area: foundation or frontier models, including LLMs

Abstract: While Large Language Models (LLMs) hold promise to become autonomous agents, they often explore suboptimally in sequential decision-making. Recent work has sought to enhance this capability via supervised fine-tuning (SFT) or reinforcement learning (RL), improving regret on the classic multi-armed bandit task. However, it remains unclear how these learning methods shape exploration strategies and how well they generalize. We investigate both paradigms by training LLMs with SFT on expert trajectories and RL with a range of tailored reward signals including a strategic, regret-shaped reward to reduce variance, and an algorithmic reward that enables oracle imitation. The resulting agents outperform pre-trained models and achieve performance comparable to Upper Confidence Bound (UCB) and Thompson Sampling, with robust generalization to 6$\times$ longer horizons and across bandit families. Behavioral analysis reveals that gains often stem from more sophisticated but greedier exploitation: RL/SFT agents are more prone to early catastrophic failure than pre-trained models, prematurely abandoning exploration. Furthermore, agents trained to imitate UCB learn to outperform their teacher by adopting more exploitative variants. Our findings clarify when each training paradigm is preferable and advocate tailored reward design and evaluation beyond average regret to promote robust exploratory behavior.

Published as a conference paper at ICLR 2026
WHEN GREEDY WINS: EMERGENT EXPLOITATION BIAS IN META-BANDI LLM TRAINING
Sanxing Chen', Xiaoyin Chen Yukun Huang', Roy Xie', Bhuwan Dhingra' Duke University, "Mila- Québec AI Institute, 'Université de Montréal sanxing. chen duke edu, bahingra@cs. duke.edu
ABSTRACT
While Large Language Models (LLMs) hold promise to become autonomous agents, they often explore suboptimally in sequential decision-making. Recent work has sought to enhance this capability via supervised fine-tuning (SFT) reinforcement learning (RL), improving regret on the classic multi- aalti- bandit task. However, it remains unclear how these learning methods shape exploration strategies and how well they generalize. We investigate both paradigms by train- ing LLMs with SFT expert trajectories and RL with range of tailored reward signals including a strategic, regret-shaped reward to reduce variance, and an algo- rithmic reward that enables oracle imitation. The resulting agents outperform pre- trained models and achieve performance comparable to Upper Confidence Bound (UCB) and Thompson Sampling, with robust generalization zons and across bandit families. Behavioral analysis reveals that gains often stem from more sophisticated but greedier exploitation: RL/SFT agents more prone to early catastrophic failure than pre- pre-traine models, prematurely abandoning ex- ploration. Furthermore, agents trained imitate UCB learn to outperform their teacher by adopting more exploitative variants. Our findings clarify when each training paradigm preferable and advocate tailored reward design and evalua- tion beyond average regret to promote robust exploratory behavior.
6x longer hori-
INTRODUCTION
fundamental challenge in sequential decision pocision-maaingg making problems lies in the exploration-exploice trade-off, where an agent must balance exploiting known good actions with exploring new ones to discover potentially better options. The multi-armed bandit (MAB) problem serves as a classic, formalized testbed for studying this critical behavior. Despite their sophisticated capabilities, Large Language Models (LLMs) often struggle here, defaulting to short-sighted, greedy behavior that over-exploits known rewards at the expense of exploration (Krishnamurthy
al. 2024 Schmied ct al. 2025). While certain prompting configurations can elicit better performance from frontier models like GPT-4, this inherent suboptimal bias remains significant hurdle for most models.
To address this, two primary training paradigms have emerged for shaping LLM exploration be- havior: Supervised Vine-Tuning (SFT) and RI. SFT teaches the LLM mimic the behavior of an optimal exploration algorithm, such as Upper Confidence Bound (UCB), by training on trajectories of expert demonstrations. In contrast, RL enables the model to learn an effective policy directly from environmental rewards. When trained to solve bandit instances that differ from those they encountered during training, LLMs effectively become meta-bandit agents, acquiring meta-polics peta-policy capable of exploring novel environments (Kveton et al.] 2020). Prior works suggest that both meth- ods can improve exploration capabilities in LLMS on in-distribution tasks, with SFT showing more consistent results (Nie et al.) 2024 [Schmied et al. 2025). However, deeper understanding of how these training methods shape an agent's is strategy lacking. is unclear whether the policies induced by SFT and RL differ mechanistically. More critically, how do these policies generalize to longer horizons and out-of-distributiin environments?
In this work, we train LLMs to perform MAB tasks using both SFT on expert trajectories and RL with a spectrum of task specifcc reward signals. We evaluate the performance learned policies
Our code and data released in http:///tt///gtgt.././/////aaaaa

---

Published as a conference paper at ICLR 2026
on range of MAB environments, under length generalization and cross-distribution transfer (e.g., Gaussian to Bernoulli). In addition to the standard stochastic reward of bandits, we propose two additional reward signals: strategic reward based the notion of regret to reduce training vari- ance, and an algorithmic reward, which incentivizes imitation learning of an oracle policy like UCB via RI. We find that both SFT and RL improve the base model's performance in achieving lower regret and higher rewards, achieving comparable performance to theoretical op- timal baselines like UCB and Thompson Sampling. For RL, the strategic reward improves training efficiency in figh-variance environments, while the algorithmic reward consistently outperforms other learned policies due the ease of credit assignment. Moreover, RL policies yield more robust generalization across different bandit families compared to SFT. The policies also exhibit strong generalization on 6x longer (compared to training) and cut-of-distribution environments.
MAB tasks
While achieving lower regret is the canonical measure of success in MAB, classical literature cau- tions that relying solely on this aggregate statistic can obscure important characteristics of the agent's behavior (Lattimore & Szepesvári 2020). An agent might achieve superior average performance with a high-risk policy prone to catastrophic failure, a nuance that the expected outcome can over- look. This prompts deeper question: does lower average regret achieved by the LLM policies indicate the acquisition of a robust exploration strategy?
analyze the agents' action patterns and compare them to pre- traierd models and baselines like UCB and Greedy policies. We utilize surrogate statistics such as suf- fix failure rate, which is highly suggestive of the long-term prospects of the agent (Krishnamurthy et al. 2024). We find that the agents' impressive improvements in performance are linked to learning more sophisticated forms of exploitative behavior. For instance, agents trained via RL imitate an optimal UCB policy often outperform their teacher by implementing variants of UCB that can pre- maturely stop exploring an action after unsatisfactory short-term rewards. This suggests that while the training process maximizes average performance with reasonable generalization, it incentivizes short-term reward seeking that can be counterproductive in the long run. The suitability of these learned policies ultimately depends on whether an application prioritizes long-term robustness over immediate returns, or average performance over worst-case scenarios.
To answer this question,
In summary, we present unified study of how SFT and RL shape LLM exploration in MAB, treat- ing trained models as meta-bandit agents. We introduce two principled reward designs Beggret-hhapd) rewards that stabilize learning in high- sighanerinnce settings and algorithmic rewards that enable efficient RL- based imitation of oracle policies, which both improve over baselines from prior work (Schmied et al. 2025), with algorithmic rewards yielding the most consistent gains. Eval- uations demonstrate robust generalization to 6x longer horizons and across bandit families, with RL policies transferring more reliably than SFT. Beyond aggregate regret, our behavioral analysis reveals mechanistic differences: learned policies often implement exploitative strategies that boost average returns but can sacrifice long-term robustness.
2 RELATED WORK
The multi-armed bandit problem, despite being a classical abstraction, embodies the fundamental exploration-exploitaion trade-off central sequential preissionmaking and has wide real-world applications (Bouneffouf et al. 2020 Bouneffout & Feraud 2025). As LLMs are increasingly deployed in interactive settings, the MAB problem has become key testbed for evaluating their ability to incrementally gather information and improve over time, a paradigm known as In-Context Reinforcement Learning (ICRL) (Moeini al. 2025).
Bandit problems have long been used to evaluate the generalizable ICRL capabilities of sequential models like RNNs and Transformers (Duan et al., 2016 Laskin et al.) 2023 Lee et al. 2023). In
the L.M era, initial benchmarks found that pre-trained models can learn to explore simple MAB
problems in-context (Binz & Schulz, 2022 Wu et al. 2024: Coda-Forro et al., 2023 Park et al.)
2025). However, they exhibit unsatisfactory exploratory behavior complex environments without careful prompt engineering (Krishnamurthy et al.] 2024; Monea et al. 2024). Subsequent work has sought to address this through activation steering (Rahn et al. 2024) and fine-tuning (Tajwar) ctt al. 2025). Nie et al. (2024) uses supervised fine-tuning (SFT) on expert trajectories to improve performance, demonstrating successful generalization different reward distributions within the
2

---

Published as a conference paper at ICLR 2026
same bandit class. More recently, Schhmied et al. (2025) applies reinforcement learning to train LLMs for bandit tasks, showing positive but weaker in-distribution results compared to SFT.
Our work provides systematic comparison of these two learning paradigms. We demonstrate that RL-trained agents, while matching SFT performance in-distribution, generalize more effectively to move beyond simple performance compar-
out-of-distribution environments. More importantly, isons to conduct a behavioral analysis that uncovers subtle but critical failure modes in how LLMs learn to explore, highlighting previously unaddressed challenges.
METHODOLOGY
Prompt with summary statistics
In a 5-armed bandit problem, here are the results of previous arm pulls:
A MAB problem B = (A, R) is defined as set of arms A = {I....,KK) where each arm E A is associated with reward distribution R2 and mean lt. The goal of the agent is to maximize the expected cumulative re-
Arm O: I pull, avg. reward -0.249
Arm 2 pulls, avg. reward 0.281
Arm 2: 7 pulls, avg. reward 0.790
ward E|E r'] over T trials. During training, the agent learns from bandit instances sampled from an unknown task distribution D. We can evaluate the learning agent's performance in-distribution by sampling bandit instances from D or a different distribution D'. In training an agent to solve various bandit instances from task distribution, we are effectively searching for a meta-bandit policy (Kveton al. 2020), which is reinforcement learning problem.
Arm 3: 3 pulls, avg. reward 0.279
Arm 4: 7 pulls, avg. reward 1.015
Which arm should be pulled next?
Show vour reasoning in <think>>
(OOD) on instances from
</think> tags and your final answer
in <answer> </answer> tags.
Figure 1: An instruction provided to the LLM agent for the MAB task.
3.1 REINFORCEMENT LEARNING OF META-BANDIA LLM AGENTS
At each bandit turn i, the LLM agent takes input the interaction history consisting of past actions and rewards in the observation or, and generates a sequence of tokens 8 which contains the action of the next arm to pull dN The environment then returns the stochastic reward interaction history is then updated with 0++1 f(o,, de, rz),, where f can be a simple concatenation or, in our case, summarizer that extracts sufficient statistics as shown in Figure I The process is repeated for T turns for each episode. As the agent learns over a history to build its belief about the environment (c.g., distribution family and variance), this process forms Partially Observable Markov Decision Process (POMDP). It can be trained using on-policy RL to maximize episodic return and thus learns amortized exploration strategy over histories.
Ra. The
Unlike traditional RL policies that directly select actions, LLM agents operate in the token space. This implementation converts the problem into two-level hierarchical MDP (Hauskrecht et al.) 2013 et al. 2025), where a high-level policy operates at the turn level to select a local policy that generates the entire response s; and receives the external reward rg. The low-level policy operates at the token level to implement the selected local policy. The probability of generating the token $t, at position j is given by: To (St.j or, St,<;) where St,<j is the sequence of tokens generated in turn up to position 1-1. 1. At turn f, the token index j ranges from Jt,ean |o,| + 1 to Jr.end = |o+| + |syl- We pass r, as the reward signal to the low-level policy at Jr,ent, while there is no reward signal for intermediate tokens.
To learn Te, we adopt PPO (Schulman et al.) 2017) and compute token-level advantages with a dual- (7. A) Generalized Advantage Estimator (Schulman et al. 2016). We use separate discount factors and trace-decay coefficients for intra-turn and inter-turn steps, denoted Tintra Nater and Ainta. Appters respectively. For simplicity, we define the token-level state step j as hes 8t,55) The one-step temporal difference (TD) error for each generated token index j is:
{ Viintra (he.s++) - V(hes) ( + Yimer V (or+1) (hr,, if = Jr.end
if Je.saan S j < Jr.end
de.j
For the final token at index Jr,end. the error incorporates the external reward re and bootstraps from the value of the next turn's 's initial state, ((o+1),, using the inter-turn discount factor Yimer. In prac- tice, since we can only optimize over a truncated horizon for this infinite-hore horizen problem, we infer the value of one more turn, ((or+1) for the last turn T.
3

---

Published as a conference paper at ICLR 2026
The GAE advantage for token index now accumulates TD errors all subsequent generated- token positions across the entire episode. Let x(T) denote the starting generated index in turn
{ ( Jr.stant
if r =
as seen from (t, x(T) =
Define the step-weighting product from (f,j) to
(r, k) as:
paard
P(,,j.,,))
II (Nintrr
II (amm(f))
Nintra Tintra
Xintra Tintra
(=m(()
The token-level GAE advantage for (t, then:
Je
A
Σ
P(G,i.T,)) 87,
T=t k==(()
With token-level advantages defined only for generated tokens, the clipped PPO objective is:
pPO (0) = Re.sj min (0) Aejj, clip(r., - -, +c) A.s)]
ma(ss,ylbr,)) Here Osia is the reference policy where the per-token probability ratio is (0) Houe ( Re.5)" parameter at the previous iteration. This objective trains the policy at token level using the two-scale GAE that respects intra-turn and inter-turn dynamics. We intentionally omit the KL-divergence term, which often employed PPO as we find it to be unnecessary for our setting without learned reward model.
3.2 REWARD DESIGN
As described above, the meta-bandit agent relies solely on the past interaction history o, generate the next action. The interaction history o, is summary of the past actions and rewards, which is tied to the stochastic bandit rewards r; and cannot be changed. We can however opt for different reward signal for the PPO optimization in Equation The original bandit rewards (RL (RI-OG), although natural choice of reward signal for PPO optimization, contribute to credit assignment difficulty and learning inefficiency due their intrinsic stochasticity.
On the other hand, we can more accurately measure the optimality an action based on the notion of immediate regret. At each time step, the immediate regret is defined the difference between the expected reward of the optimal arm and the expected reward of the arm selected by the agent. A, jr" ,AA, We define the strategic reward (RL-STG) based the immediate regret of the agent's 's action:
A.
PA. min, μ E [0.
P =
Amax μ min; #4
This reward signal directly optimizes an action's utility, which simplifies credit assignment. Using the realized regret as the reward is form of baseline subtraction (Kveton et al. 2020). We further use the (pseudo) regret, which is analogous to introducing a control variate. While this approach reduces variance, theoretically does not alter the optimal policy which the agent converges.
A third approach moves beyond extrinsic environmental rewards, instead using a reward function optimized by an expert oracle (Ciosek] 2022). While this reward function often needs to be learned via inverse reinforcement learning (Abbecl & Ng 2004), we can bypass this by deriving it directly from well-established optimal algorithms for MAB. We select the Upper Confidence Bound (UCB) algorithm as the oracle policy, as its deterministic and distribution-agnostie properties provide con- sistent and unambiguous learning signal. We therefore define the algorithmic reward (RL-AL)) as binary signal r, 1 if the agent's action matches the oracle's decision Toracle(Or), and r; otherwise. Because the UCB oracle is a reactive algorithm, this myopic reward is sufficient for on-policy learning and sidesteps the need for return- etturd-based credit assignment. This imitation leamn ing setup leaves the agent free to discover its own internal algorithm for processing the interaction history match the oracle's choice at each step, without any supervision the reasoning process.

---

Published as a conference paper at ICLR 2026
Demonstration of UCB calculation
<think> Let calculate the UCB value for each arm after (1 + + 20 pulls:
Arm O: Uncertainty bonus /m(20)/1 x 22.996/1 & 1.731; UCB = -..24-0..11111 1.731 0.616
Details of Arm 1-3 omiited for brevity.
Arm 4: Uncertainty bonus - /lm200)/7 = v 2.996/ = 0.654; UCB 1.015 + 1/2 x 0.654 1.342
Based on these calculations, choose arm 4 as it has the highest UCB value. </think> <answer>> Arm 4 </answer>
Figure 2: An example of the UCB calculations for the state in Figure 1 used in SFT.
On top of these task specific rewards, we also consider a reward shaping term that encourages the LLM agent to generate valid responses. Specifically, we set reward to zero if our parser cannot extract valid action and rationale from the response. For the stochastic reward setting (RL-OG), because the unbounded reward sometimes negative, we subtract 0.5 from the reward as the penalty for invalid responses.
3.3 SUPERVISED LEARNING
We also consider supervised fine-tuning (SFT) baseline, where the LLM agent trained on observation-responee pairs. The response includes synthetic CoT demonstrations to explicitly cal- culate UCB values and the UCB action (Figure 2). Here, both the rationales and the actions are directly supervised. Since the states embodied by the observation are sampled from the UCB policy, the learning process is off-policy.
4 EXPERIMENTAL SETUP
Language Model Configuration. We use Qwen 2.5 3B and 7B Instruct (Qwen et al. (024) as the base model for fine-tuning. The observation at each time step consists of a natural language instruction of the MAB task and the interaction history presented pulls and average reward for each arm FFigure I). We use this sufficient statistics to summarize the interaction history, which has been shown to more effective than using cumulative context, e.g., a raw list of actions and rewards (Krishnamurthy et al. 2024). In the instruction, the agent is asked think step-by-step using chain-of-thought reasoning. which critical for eliciting the sequential decision-makin ability of LLMs (Yao et al. 2023).
summary of the number of
RL Configuration. We build our RL training code top of the VeRL framework (Sheng et al., 2024). At each training iteration, we first sample a batch training task distribution D. From each environment,
random environments from the collect rollout of length T 50, resulting in batch of 64 x 50 transitions (O,, St, Tt). This batch then used to compute policy gradients and perform PPO updates. We sample another set of environments for the next batch of rollouts.
Supervised Fine-Tuning (SFT). For the SFT experiments, we train the model for 6 epochs 32k transitions sampled from UCB rollouts in environments drawn from the training task distribution D. Transitions are uniformly sampled across the length of training horizon T. We synthesize templated response for each transition by demonstrating the step-by-step UCB value calculation for each arm and the comparison process which leads the final action. We perform full fine-tuning minimizing the cross cross-entropy loss between the predicted and ground- -ound-truthhh responses.
Bandit Environments. We primarily consider MAB environments listed in Table Our ap- proaches are also generalizable to a popular contextual bandit setup described in Appendix D The environments can be generally grouped into two families: Gaussian and Bernoulli, based on the reward distribution. The Gaussian environments have continuous reward distributions, while the Bernoulli environments have discrete binary reward distributions. We select one from each family (i.e.. Bernoulls 1ills Uni form and Gauss ian5 Varl MeanNO) as the two training task distri- butions, under which train two set of policies to test out-of-distribution generalization.

---

Published as a conference paper at ICLR 2026
Table 1: Generic families of k-armed MAB environments and some specific parameterizations used in our study. Asterisk indicates the training task distributions.
Family
Reward Dist.
Mean Dist.
Example Instantiation
Gaussiank: Varo² McanNm
N(u, o²)
N(m,
Gaussian5 Varl MeanNOO
Gaussiank: Varo² _MeanU
r ~ N(u, o²)
1)
Gaussian5 Varl_Mai _MeanU
Bernoullik. Uniform Uniffol
B(u,)
1(0
Bernoulli5. Uniffrm"
Bemoullik Delta
r ~ B(us)
= p.
BernoulliS 2ellta..
u, p A. A.
Baselines. We compare learning agents against the following standard baselines: 1) Upper Confidence Bound (UCB) (Auer et al.) 2002) selects the action A = where Qr(a) is the mean reward of action a up to time t, (a) is the number of times action has been selected up to time t. and C' constant. 2) Thompson Sampling (TS) (Thompson 1933) is Bayesian method that samples from the posterior reward distribution of each action and selects the one with the highest sample. We use Beta and Gaussian posteriors for Bernoulli and Gaussian rewards, respectively. 3) c-Greedy chooses random action with probability c and the action with the highest current mean reward otherwise. While simple, its constant exploration leads to linear regret. The purely exploitative Greedy policy a special case where e = 0 and we perform a round-robin start.
arg max, (Qr(a)+ + Cx Cx V Ni(a)
log(t)
For UCB, which sometimes serves as teacher, we use exploration constant of C = 0.5, which performs well for both training environments. For e-Greedy, we use a standard = 0.1; while likely suboptimal, it provides consistent anchor for comparison. The direct performance comparison between learned agents and baselines not the central focus of this study. The one exception the evaluation of our imitation learning agents against their UCB teacher.
Evaluation. We evaluate the policy over 64 episodes, each with maximum of 300 steps. We use a fixed set of 64 different seeds for initialization of evaluation environments and bascline policies. To compare the policies and test for length generalization, we follow standard practice to report cumulative regret
E {50, 300). MAB instances, even when they are drawn from the same distribution, can be quite different in terms of challenge level. Conventional empirical evaluation aggregates from exccessive number of rollouts (e.g.. ten of thousands) and long horizons, which although provides more stable estimate is prohibitively costly for LLM inference. We therefore utilize distribution plots to visualize this variation in regret and focus on the typical performance in comparison. To provide more comprehensive evaluation, supplement this with two additional metrics: time-averaged reward and best arm frequency, which measure the proportion of times the optimal arm is selected.
EXPERIMENTAL RESULTS
5.1 LLM AGENTS ARE BAATDT LEARNERS
As shown in Figure across both training setups, RL-trained policies improve upon pre-trained models to be comparable with classical baselines (UCB, TS. e-Greedy), achieving lower cumulative regret and length generalization to a 6x longer horizon (50 + 300). The time-averaged reward (AvgReward) and best arm frequency (BestArmFreq)) in Table 2 indicate steady performance gains over time. Learning agents remain competitive under OOD evaluation, exhibiting non-trivial cross- distribution transfer from momussinnttriinee policies to Bernoulli environments and vice versa. How- ever, RL agents that trained on environmental feedback (i.e., RL-OG and RL-STG) show weaker cross-distribution generalization, with greater variability in worst-case performance. Following Nie et al. (2024), adopt function fitting to measure the linearity versus sub- lub-iinearity of cumulative gret through time. We find that pretrained LLM exhibits linear regret (similar to Greedy), while fine- tuning greatly reduces the linearity, reaching levels comparable to lower to UCB (Appendix B).

---

Published as a conference paper at ICLR 2026
Gousaland
10-
56-
46
20
Berroulis, Un Unifamm
Gauedens, Vel MeanNo
Bertoull5, D.
Debat22
Gauscant Meani
200
60-
30
300
Epsilon Greedy e-0.1 Sampling
UCB c-0.5 Protrain
7b
I. RL STG RL-ALG
RL-L-G
Figure 3: Comparison of LLM policies against baselines cumulative regret at 300 steps. The first row shows the results of 7B models trained on 1ar. MeanNO,, and the second row shows the results of 7B models trained on Bernoullis Uniform. Evaluation is performed both in- (first column) and cutto--distribution (other columns). The boxplots depict the median, interquartile range (IQR) from the 25th to the 75th percentile, and whiskers extending to 1.5 x.R 3B model results can be found in Appendix B
Learning from UCB signals. Overall, policies optimized using teacher UCB signals, whether through reinforcement learning (RL ALG) or supervised fine-tuning (SFT), consistently outperform policies trained solely on the task reward signal (RL-OG), This underscores the difficulty of training RL LLM policies for Long-horizon exploration where credit assignment is challenging. The imita- tion policies match or achieve lower cumulative regret compared the teacher UCB policy in all evaluation environments, revealing seemingly exciting result: policies trained on expert-generated data can ultimately outperform the very expert policy that produced the data.
Improving training with strategic rewards. To learn RL poli- cies from environmental feedback, while theoretically aligned with the original bandit reward signal (RL-OG) optimizing for strate- gic rewards (RL-STG) empirically improves the performance the policy in the Gaussian training setup, despite certain instabilities observed in OOD evaluation. As the variance of the reward distribu- tion decreases, RL-STG becomes equivalent RL-OG, which ex- plains why their performance more closely matched when train- ing the Bernoul 1elllii5UUp 1nn form environment.
0.8
Brequancy
0.7
K
0.6
3b RL-LG
Tranning 125
SFT vs RL for imitation. SFT with UCB expert demonstrations achieve similar regret UCB in-domain, consistent with prior work (Schmied et al. 2025). We additionally find SFT policies to be surprisingly competitive oft-o--distribution. Part of the reason that UCB is a distribution-agnoe agnostic policy-the same calculation can be applied to different reward distributions as long as the LIM fol- lows the arithmetic operations. This generalization is however frag- ile. SFT policies can overfit to the training distribution and cause degradation of basic arithmetic capability. Together, these factors lead to higher variability and worst-case regret in OOD evaluation. For example, in Figure 3. the SFT policy trained in the Bernoulln S_nniff Uniioot form environment exhibits unsatisfactory worst-case performance in Gauss an5 Varl MeanNO, while the RL-ALG policy based on UCB reward sig- nal remains robust.
Figure 4: Training perfor-
mance of RL-STG policy on Gauss ann_Varll Wa with 3B and 7B models. We additionally include RL-ALG of 3B model (5 arms) for comparison.

---

Published as a conference paper at ICLR 2026
Varl_ MeanNo K-5
BermouliKK Uniform
BernoulIK _elttllliKDelea..22
K-10
K-5
K-10
K-5
K-10
0.8
0.8
0.7
0.6
0.5
BestArmee
0.6
0.4
0.6
0.4
0.3
0.4
0.2
0.1
0.2
0.1
200 Time stops
200 Time stops
200 Time stops
200 Time stops Time steps
200
200 Time stops
R1-00
To ALALG
Figure 5: Generalization to environments with 10 arms of 7B LLM policies trained on SeussianS..arrlMeaannn Best arm selection frequency reported.
Table 2: Analytics of baselines and 7B LLM policies trained on Gaussian5.Vas waw.iiinnn.aaalMMaaaaa evaluated in-distribution. Except rewards, statistics are shown percentages. Note that suffix failures emerge from every fine-tuned LLM agents.
Type
Metric
AvgReward
BestArmFreq
GreedyFreq
SuffixFail
MinFrac
@t
50
300
50
300
50
300
50
150
50
300
Baselines
Greedy
0.91
1.01
65.4
71.7
90.0
98.3
25.0
25.0
10.2
1.7
e-Greedy
0.76
0.90
47.9
67.6
91.3
91.6
0.0
0.0
2.5
8.5
TS
0.77
1.00
55.8
78.5
67.0
0.0
UCB
0.91
1.04
67.7
80.6
83.3
95.4
3.1
4.7
10.5
1.8
LLM Agents
Pretrain
0.55
0.79
45.4
63.1
48.7
0.0
35.2
18.1
SFT
0.92
1.05
69.4
81.3
83.5
95.5
6.2
6.2
10.5
1.8
RL-OG
0,81
1.01
61.1
79.8
78.3
91.7
1.6
4.7
13.3
3.6
RL-STG
0.84
1.01
63.7
81.1
83.7
95.8
3.1
6.2
10.9
2.4
RL-ALG 0.92
1.05
70.7
85.7
85.4
97.0
7.8
1.7
Small models struggle to learn without teachers. Figure 4 illustrates the training dynamics of __MMeNOO environment using 3B and 7B parameter
the RL-STG policy on the CaussianK_vas Varnn-aaa-MMMaa models, measured by the frequency of selecting the best arm. For the 7B models, performance improves over iterations across varying numbers of arms (K=2, 3. 5), with higher accuracy for smaller K. In contrast, the 3B model exhibits stagnant accuracy, starting comparably or even higher than the 7B counterpart in simpler and 3-arm settings pre-training but failing improve with RL updates. Nevertheless, we observe that the 3B model can learn with teacher guidance using RL-ALG or SFT. This highlights the challenges of training smaller models with RL on task rewards, as learning effective exploration policies from environmental feedback demands long-horizon credit assignment.
Generalization to Larger Action Space. The pre-trained model's performance degrades signif- icantly as the action space increases. three 10-arm environments, exhibits excessive regret, while the policies we trained maintain stable performance. Figure 5jillustrates this failure: the base LLM's best-arm selection frequency stops improving at an early stage and degrades to near random performance. All the trained agents do not suffer from this collapse, suggesting that the training process has successfully enhanced the policy's 's generalization to an increased action space.
We will explore in the following section why the LLM policies excel, what strategies drive their success, and how different learning paradigms lead to different behaviors, to better understand their potential and limitations.
5.2 ANALYZING LLM EXPLORATION STRATEGIES
We additionally include three surrogate statistics used Krishnamurthy et al. (024)) as diagnos- ties for long-term exploration failure: GreedyFreg @ measures the relative frequency of rounds that
8

---

Published as a conference paper at ICLR 2026
Geussiens, Vart Meanni Suffix Falkure
Bemoulis Uniform Suffix Fallure
BestAr Histogram
Arm Histogram
0.8
0.8
0.2
0.4
0.4
0.05
0.1
0.00
0.0
0.0
109
209
5.0
150
150
200
250
100
200
50
100
150
200
250
Time step
Aloust LITT sefected per apiiord
Time step
Abaut aET selected apisode
Sampiing
Figure 6: Suffix failure frequency and best arm selection histogram of the two sets of LLM policies described in Figure 3] evaluated in-distribution. We observe that the distributions of best selec- tion frequency of learned policies shifts from approximately normal distributions of the pretrained model bimodal distributions.
selects the greedy action up to time t; 1t measures the frequency of suffix failures; and MinFrackt diagnoses uniform-like failures. Specifically, a suffix failure at t indicates that the policy never selects the optimal arm again for rounds t, ..... T, while Mi nF ca tracks the mini- mum fraction of rounds any arm is chosen up to L, rescaled by K to the range [0, 1]. For MinFrac, sustained large values indicate a failure to converge (uniform selection).
Learned policies exhibit greedy tendencies. While learned LLM policies achieve lower regret and less uniform failures compared to the pretrained model, our qualitative analysis reveals con- cerns about suboptimal exploration. The first warning sign, shown in Table 2] is that the learned agents exhibit higher suffix failure frequency than both the pre-trained model and theoretical optimal policies. This indicates premature abandonment of the best arm, pattern absent in the pretrained model. Learning also alters the distribution of best arm selection frequency from an approximately normal distribution for the pretrained model to bimodal distribution, where the agent either almost always selects or very rarely selects the best arm within an episode, characteristic of Greedy be- havior (Figure 6). Direct measurement of greedy-arm selection frequency further confirms that the learning agents reach the exploitation phase more quickly than the pre-trained model.
Dissecting imitation of the UCB oracle: RL vs. SFT. Although the UCB policy it- self greedy in construction, student policies trained under UCB teacher often amplify this tendency. This partially explains why LLM policies trained to imitate UCB decisions can sometimes perform better than the oracle. To analyze this phenomenon, we compare how of- the choices of each UCB-mimicking pol- icy diverge from the oracle's decision given the same state, metric we refer to the "match rate". For SFT policies that explicitly calcu- late confidence-bound values, we additionally report the absolute difference between the pol- icy's predicted UCB value and the correspond- ing oracle value, averaged across the arms.
Gosseret Meoolt Mewooi
Maan Sore
100
100
Geuumird Vari Mariit
Bemooil8 Usiform
5F1
0.3
80
110
UCB UCB-v1
Aug Abe Datts
Figure 7: Match rates of the RL-ALG policy against decisions of the oracle UCB and a UCB- like algorithm discovered in LLM rationales, at different timesteps. SFT policy shows jump in calculation errors at the 51st step.
when both policies trained with UCB supervision in the same en- vironment Gaussians walaaannSaalllll MeanNN. the SFT policy maintains a higher match rate than the RL policy from the beginning, indicating that it more faithfully imitates the teacher's decisions. Both sustain high match rate above 80% in the first 50 steps di-distribttion, with the SFT policy tracks the oracle's UCB decisions more closely. However, this stronger imitation capability also makes the SFT policy more susceptible to
As shown in Figure 7

---

Published as a conference paper at ICLR 2026
overfitting, meaning its high match rates are only guaranteed when evaluation conditions closely resemble the training data.
This sensitivity becomes apparent when training different data. While the SFT policy trained on Gaussians Varl MeanNO sustains high match rates across all tested environments, an SFT policy trained on Bernoull 1irouul15... 1.n.nniniii.. fniform achieves this only within the same Bernoulli family of tasks (Figure 20). We find this failure is a result of systematic errors in simple calculations involving negative rewards, which are unseen during training-a sign of catastrophic forgetting of basic arith- metic skills (Chu et al., 2025 Shenfeld et al. 2025). The agent frequently miscalculates the UCB values and subsequently disregards its own calculations. This leads to asymmetric generalization, where performance degrades sharply outside the training distribution, consistent with the higher worst-case regret we previously observed in Figure 3] These results highlight the critical importance of training data selection to balance imitation fidelity with robustness.
What incentivizes RL-ALG to prioritize exploitation over imitation? The adaptive behavior of the RL-ALG policy is subtle consequence of the bandit learning structure and fundamental change in the UCB teacher's behavior over an episode. Initially, the UCB algorithm balances high uncertainty (exploration) and high observed rewards (exploitation). As episode progresses, the uncertainty bounds shrink, and the teacher's policy converges. Its decisions become increasingly dominated by the empirical means, causing it to select the greedy arm. In this regime, the RL objective, though formally defined in terms of imitation, becomes highly correlated with a reward for exploitation. The agent discovers that it can optimize more easily by directly picking the greedy arm, rather than faithfully internalizing the teacher's complex exploration logic.
LLM rationales reveal flawed, exploitative heuristics. The LLM's generated rationales veal its underlying decision-making process. RL policies trained on bandit rewards converge to templated heuristies that most oftenly compare and choose the arm with the highest mean reward. Their explorative actions are driven by rationales that explicitly evaluate the uncertainty of the arms, sometimes with UCB-like calculation. RI-ALG trained in GaussianS 1arr 1_MeanNo however converges to a UCB-like algorithm and mentions in its rationales 98% of the time:
Qe(a) V +1)) In the standard UCB algorithm, the numerator of the exploration term (a)
log(t) grows with the total number of pulls, ensuring that no action is ever abandoned permanently. In contrast, this learned variant's ss exploration term depends only (a)a), the pulls of specific arm. This allows the policy to prematurely stop exploring an action it appears unprofitable in the short run, embodied exploitative tendency.
Figure shows that this UCB-like algorithm describes the LLM policy better than the oracle UCB. However, the LLM does not follow the algorithm strictly, as its decisions are also affected by fre- quent numerical inaccuracies such as miscalculating the log term. We can also observe that when the policy diverges from the UCB variant's decisions, it opts for the greedy action more than 86% of the time. In Bernoullis www.oouli..Unnfffor.o the LLM converges to another variant (a + (N.(a)
with similar greedy behavior. These findings reveal that the RL-ALG policy learns approximate, crror-tolerant variants of UCB, blending imitation with opportunistic exploitation that lowers regret in certain environments. Intriguingly, with inaccurate calculations during early training stages. Its eventual convergence to greedy variants suggests failures in credit assignment.
observe that the LLM generates the correct UCB formula
6 CONCLUSION
We fine-tune LLM agents via SFT and RL with novel reward signals, achieving strong performance with lower regret and robust generalization to 6x longer horizons and new reward distributions in the multi-armed bandit task. However, behavioral analysis reveals that training elicits short-sighted, exploitative policies. This emergent greediness is a consequence of the fundamental imbalance in training data, where sparse exploration signals are easily overwhelmed by frequent exploitation. Compounded by the complex credit assignment problem, this challenge highlights the need for methods that explicitly amplify exploration signals. Future work could explore focused replay tech- niques that re- weight experiences based on information gain and surprise or design adversarial and curriculum- based environments that make robust hog-hooiizon planning necessity for success.
10

---

Published as a conference paper at ICLR 2026
REPRODUCIBILITY
To support the reprodueibility of our results, we provide more implementation details in Appendix A We commit sharing the code, pre-trained models and data to the general public upon publication.
ACKNOWLEDGMENTS
We thank Ronald Parr, Shuyan Zhou, and Fan Yao for providing insightful feedback and suggestions to the manuscript. We also thank Qian Liu, Weiting Tan, and Junlin Wang for helpful discussions. This work was supported by NSF award IIS22211526.
REFERENCES
Pieter Abbeel and Andrew Y. Ng. Apprenticeship learning via inverse reinforcement learning. In Carla E. Brodley (ed.), Machine Learning, Proceedings of the Twenty-first International Conference (ICMI. 2004), Banff. Alberta, Canada, July 4-8, 2004, volume of ACM Inter-
national Conference Proceeding Series. ACM, 2004. doi: 10.1145/1015330.011.. 101.300.0114330 URL
https: /ttps://doi..o org/10. 01t.:00.1111111130011
Peter Auer, Nicolo problem. Machine learning, 47(2):235-25 256, 2002.
and Paul Fischer. Finite-time analysis of the multiarmed bandit
Marcel Binz and Eric Schulz. Using cognitive psychology to understand gpt-3, arXiv preprint arXiv: 2206. 14576. 2022.
Djallel Bouneffouf and Raphael Feraud. Multi-armed bandits meet large language models. arXiv preprint arXiv: 2505. 13355, 2025.
Djallel Bouneffouf, Irina Rish, and Charu Aggarwal. Survey on applications of multi-armed and contextual bandits. In 2020 IEEE congress evolutionary computation (CEC), pp- 1-8. IEEE, 2020.
Tianzhe Chu, Yuexiang Zhai, Jihan Yang, Shengbang Tong, Saining Xie, Dale Schuurmans, Quoc V. Le, Sergey Levine, and Yi Ma. Sft memorizes, generalizes: comparative study of foundation model post-training. arXiv preprint arXiv: 2501.17161, 2025.
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff func- tions. Proceedings of the fourteenth international conference on artificial intelligence and statistics, pp. 208-214, JMLR Workshop and Conference Proceedings, 2011.
Kamil Ciosek. Imitation learning by reinforcement learning. In The Tenth International Conference on Learning Representattonss, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022. URL [Rtppsss://ppeeeeee
net wttt//oormmiiddde www.:iidddwwweeetppppee.
Julian Coda-Forno, Marcel Binz, Zeynep Akata, Matt M. Botvinick, Jane X. Wang, and Eric Schulz. Meta-in-context learning in large language models. In Alice Oh, Tristan Nau- mann, Amir Globerson. Kate Saenko, Moritz Hardt, and Sergey Levine (eds.), Advances in Neural Information Processing Systems 36: Annual Conference Neural Informa- tion Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023. URL cda04d7ea67ea1
nips ce/pape: wwweffilisaaeee wtw.es//pppprr//22//aaaa html
Yan Duan, John Schulman, Xi Chen, Peter L. Bartlett, Ilya Sutskever, and Pieter Abbeel. RI2: Fast reinforcement learning via slow reinforcement learning. arXiv preprint arXiv: 1611.02779, 2016.
Maxwell Harper and Joseph Konstan. The movielens datasets: History and context. Acm fransactions on interactive intelligent systems (täs), 5(4):1 2015.
Milos Hauskrecht, Nicolas Meuleau, Leslie Pack Kaelbling, Thomas L. Dean, and Craig Boutilier. Hierarchical solution markov decision processes using macro-actions. arXiv preprint arXiv: 1301.7381, 2013.
11

---

Published as a conference paper at ICLR 2026
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun (eds.), ), 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA. May 7-9, 2015, Conference Track Proceedings. 2015. URLhttp: //arxiv. //arxiv.org/abs /41// 1412. 6980
Akshay Krishnamurthy, Keegan Harris, Dylan J. Foster, Cyril Zhang, and Aleksandrs Slivkins. Can large language models explore in-context? Amir Globersons, Lester Mackey, Danielle Belgrave, Angela Fan, Ulrich Paquet, Jakub M. Tomczak, and Cheng Zhang (eds.), Ad- vances in Neural Information Processing Systems 38: Annual Conference on Neural Infor- mation Processing Systems 2024, NeurIPS 2024, Vancouver, BC, Canada, December 10 15, 2024, 2024, URL http: http://pappraaaa / http:/pppss...ppppoooppapeaaaaaa wttp:pppprr..eeeeeeppeeeeeeeeeee
Branislav Kveton, Martin Mladenov, Chih-Wei Hsu, Manzil Zaheer, Csaba Szepesvari, and Craig Boutilier. Meta-learning bandit policies by gradient ascent. arXiv preprint arXiv: 050945 2020.
Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph E, Gonzalez, Hao Zhang, and Ion Stoica. Efficient memory management for large language model serving with pagedattention. In Proceedings of the ACM SIGOPS 29th Symposium on Operating Systems Principles, 2023.
Michael Laskin, Luyu Wang. Junhyuk Oh, Emilio Parisotto, Stephen Spencer, Richie Steiger- wald, DJ Strouse, Steven Stenberg Hansen, Angelos Filos, Ethan A. Brooks, Maxime Gazeau, Himanshu Sahni, Satinder Singh, and Volodymyr Mnih. In-context reinforcement learning with algorithm distillation. In The Eleventh International Conference Learning Represen- tations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023. URL https: //openzeview.... net/pett/tede poedffid==yyaal id=hh0aa5MMUUV
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Jonathan Lee, Annie Xie, Aldo Pacchiano, Yash Chandak, Chelsea Finn, Ofir Nachum, and Emma Brunskill. Supervised pretraining can learn in-context reinforcement learning. In Al- ice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine (eds.), Advances in Neural Information Processing Systems 36: Annual Conference Neural Information Processing Systems 2023, NewrlPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023. httpttt:::p/ppaaaaaeaaaa nips 9bc8 7bw ott.:p/:00.....a.oo.0oooooooooor
http:
Amir Moeini, Jiuqi Wang, Jacob Beck, Ethan Blaser, Shimon Whiteson, Rohan Chandra, and Shang- tong Zhang. A survey of in-context reinforcement learning. arXiv preprint arXiv: 2502.07978, 2025.
Giovanni Monea, Antoine Bosselut, Kianté Brantley, and Yoav Artzi Llms are in-context reinforce- ment learners. arXiv preprint arXiv: 2410.05362, 2024.
Allen Nie, Yi Su, Bo Chang, Jonathan N Lee, Ed H Chi, Quoe V Le, and Minmin Chen. Evolve: Evaluating and optimizing llms for exploration. ArXiv preprint, abs/2410.06238, 2024. URL httpss://arxiv.
06238
Chanwoo Park, Xiangyu Liu, Asuman E. Ozdaglar, and Kaiqing Zhang. Do LLM agents have regret? A case study in online learning and games. In The Thirteenth International Conference on Learning Representations, ICLR 2025, Singapore, April 24-28, 2025. OpenReview.net, 2025. URL https: http:://ppeeeeviiie net forum? id= B
Qwen, An Yang, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chengyuan Li, Dayiheng Liu, Fei Huang, Haoran Wei, Huan Lin, Jian Yang, Jianhong Tu, Jianwei Zhang, Jianxin Yang. Jiaxi Yang, Jingren Zhou, Junyang Lin, Kai Dang, Keming Lu, Keqin Bao, Kexin Yang, Le Yu, Mei Li, Mingfeng Xue, Pei Zhang, Qin Zhu. Rui Men, Runji Lin, Tianhao Li, Tianyi Tang, Tingyu Xia. Xingzhang Ren, Xuancheng Ren, Yang Fan, Yang Su, Yichang Zhang, Yu Wan, Yuqiong Liu, Zeyu Cui, Zhenru Zhang, and Zihan Qiu. Qwen2.5 technical report. arXiv preprint arXiv: 34/2.15115 2024.
12

---

Published as a conference paper at ICLR 2026
Nate Rahn, Pierluca D' D'Oro, and Mare G. Bellemare. Controlling large language model agents with entropic activation steering, 2024. URL http:ttst///xi..oottt abs/ /206. 00244
Thomas Schmied, Jörg Bornschein, Jordi Grau-Moya, Markus Wulfmeier, and Razvan Pascanu. Lims are greedy agents: Effects of fine-tuning decision-making abilities. ArXiv preprint, 0as/2504.16078 2025. URL
abs 2504. 16078
John Schulman, Philipp Moritz, Sergey Levine, Michael I. Jordan, and Pieter Abbeel. High- dimensional continuous control using generalized advantage estimation. In Yoshua Bengio and Yann LeCun (eds.), 4th International Conference Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016. URL http:
7/arxiv. abs 10t./1506...0 02438
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 1707.06347, 2017.
Idan Shenfeld, Jyothish Pari, and Pulkit Agrawal. RI's razor: Why online reinforcement learning forgets less. arXiv preprint arXiv: 2509.04255 2025.
Guangming Sheng, Chi Zhang, Zilingfeng Ye, Xibin Wu, Wang Zhang, Ru Zhang, Yanghua Peng, Haibin Lin, and Chuan Wu. Hybridflow: A flexible and efficient rihí framework. arXiv preprint arXiv: 2409.19256, 2024.
Richard S Sutton, Andrew Barto, et al. Reinforcement learning: An introduction. MIT Press, 1998.
Fahim Tajwar, Yiding Jiang. Abitha Thankaraj. Sumaita Sadia Rahman, J Zico Kolter, Jeff Schneider, and Ruslan Salakhutdinov. Training a generally curious agent. ArXiv preprint, abs/2502. 17543, 2025. //////ttts////ariiiirrrr///////
William R Thompson. On the likelihood that one unknown probability exceeds another view of the evidence of two samples. Biometrika, 25(3/4):285-22) 294, 1933.
Yue Wu, Xuan Tang. Tom M. Mitchell, and Yuanzhi Li. Smartplay: A benchmark for lims intel- ligent agents. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenRevvew.net, 2024. URL https://openreviex:
net
Zhenghai Xue, Longtao Zheng, Qian Liu, Yingru Li, Xiaosen Zheng, Zejun Ma, and Bo An. Sim- pletir: End-to-end reinforcement learning for multi-turn tool-integrated reasoning. arXiv preprint arXiv: 2509.02479, 2025.
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik R. Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models. In The Eleventh International Conference on Learning Representattinss ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenRe- view.net, 2023. URL htt.hhtps://cc /tttt:::///penrevieww net /ptf widd:iddw............... WWE-vuuYUU 1uYUL-UX
Yanli Zhao, Andrew Gu, Rohan Varma, Liang Luo, Chien-Chin Huang, Min Xu, Less Wright, Hamid Shojanazeri, Myle Ott, Sam Shleifer, Alban Desmaison, Can Balioglu, Pritam Damania, Bernard Nguyen, Geeta Chauhan, Yuchen Hao, Ajit Mathews, and Shen Li. Pytorch FSDP; experiences on scaling fully sharded data parallel. Proc. VLDB Endow, 16(12):3848-8866 2023. doi: 10. 10.14477/6611540.661 p3848 8- Sto-huang.ppe .df.
BtLhtttp:: /www///wwwww/////////////// vldb. wwwpooggpppw.bboooooooooo
13

---

Published as a conference paper at ICLR 2026
A
IMPLEMENTATION DETAILS
We report additional details for the environment settings, the RI. and SFT training of LLM policies.
A.1
ENVIRONMENT SETTINGS
Table 3: Generie families of k-armed MAB environments and a complete list of 15 parameterizations used in our study. Asterisk indicates the training task distributions.
Family
Reward Dist.
Mean Dist.
Example Instantiation
Gaussiank Varo² McanNm
T ~ (u,,
~ ((m,
Gaussian5 Varl McanNO
Gaussian 10 Varl MMennN
Gaussian5
Gaussian5. Varl _MeanN
Gaussian Rar3_MeanN
Gaussiank: Varo MeanU
r r~ M~~N NN
u u~ 100,1)
Gaussian5 Varl MeanU
Gaussian5
Gaussian5 Var5 _Mcan
Beroullik: Uniform
r ~ B(u,)
1(0
Bernoulli5 Uniform"
Bernoulli 10 Uniform
SenoullikkDDetaa.
r ~ B(u,))
U,- = p. U; A, Vi i
Bernoulli5 Deeta0.22
Bernoulli 10 0.Dett00.2
Bernoulli5 Delta0.
We evaluate our policies on a comprehensive set of environments from the Gaussian and Bernoulli families, as listed Table 3 The Bernoulling www.lllk..eetaa... class, studied by Krishnamurthy et al. (2024), allows for instance difficulty to be easily adjusted by changing the reward gap between the optimal and sub-optimal arms. However, this environment unsuitable for training, as policy can simply explore each action sequentially until finding one with a mean reward above 0.5. The Gauss s sianniiaaaaasee later used by Nie et al. (2024). In these environments, the variances of both the reward and mean distributions are tied to single hyperparameter, o². Increasing the variance does not necessarily make the environment more challenging; while the rewards become noisier, the means also become more dispersed. These two effects offset each other, so this comparison group primarily tests pol- icy's robustness multiplicative rescaling and shifts in rewards. The Gauss
MeanNm class a popular benchmark introduced in Sutton et al. (1998) and
MMaanU class, from Schmied et al. 22025), maintains a fixed uniform distribution for the means, allowing the reward variance to adjusted via o² control for different difficulty levels.
The diverse distribution shifts across these test environments -nniolument--nncluiinnng changes in mean, variance, and distributional family-are designed ablate different aspects of generalization. For instance, transitioning from Gauss 5 MeanNO to Gaussian5.V Varl MManNNt1 provides tar- geted test of policy's 's ability to handle shifted reward distributions while all other properties remain constant. To assess scalability, we additionally test the policies on environments with an increasing number arms (from
11).
A.2 RL SETTINGS
Table 4 presents the hyperparameters used for PPO training of the LLM policies (RL-OG and RL-STG). For the algorithmic -ewwrrd variant (RL-ALG) we retain all settings except that we set the episode-level discount factor and GAE lambda to zero, since cumulative rewards are not required.
We use vLLM (woon et al., 2023) for asynchronous rollouts across parallel environments and FSDP (Zhao a 2023) for fully sharded training under the VeRL framework. At the start of each iteration, all environments are reinitialized with fresh random seeds to ensure diverse experi- collection.
14

---

Published as a conference paper at ICLR 2026
Table 4: Hyperparameters for the PPO training of LLM policies (RL-OG and RL- STG).
Category
Hyperparameter
Value
Model Environment
Model
Base Language Model
Qwen/Qwenn.553377-mmmes
Max Response Length
1024 tokens
Temperature
1.0
Environment
Type
Various (Gaussian, Bernoulli)
Number of Arms (k)
Episode Length (7) Number of Parallel Environments
50
64
PPO Algorithm
Optimization
Optimizer
AdamW
KKngmaa & Ba
2015
Actor Learning Rate (ats)
x 10
Critic Learning Rate (arv)
x 10-5
Gradient Clipping
1.00
Response-level Discount Factor (Cintra) Response-level GAE Lambda (Aintr)
1.00
1.00
Episode-level Discount Factor (Cinter)
0.95
Episode-level GAE Lambda (Ainter)
0.95
PPO Clipping Coefficient (c)
0.20
PPO Mini-batch Size
128
Regularization
Weight Decay
1 X 10
Entropy Coefficient
X 10
Training Infrastructure
Training Hardware
Total Training Steps
500
Number of GPUs Tensor Parallelism (Rollout)
Model checkpoints are saved every 100 training steps. Each checkpoint is evaluated on the same set of environments (matching the training type) to guarantee fair comparison. The checkpoint with the lowest cumulative regret is selected as the final model.
A.3 SFT SETTINGS
We generate training data for supervised fine-tuning by sampling N trajectories from the environ- ment using UCB policy. To expose the model to a broad spectrum of environment configurations and exploration behaviors, we uniformly sample states and actions across each trajectory's 's horizon.
As in our reinforcement learning experiments, we save model checkpoints at the end of every epoch and evaluate them on the same of environments to ensure a fair comparison.
15

---

Published as a conference paper at ICLR 2026
Table 5: Hyperparameters for Supervised Fine-Tuning (SFT).
Category
Hyperparameter
Value
Model & Data
Model Data
Base Language Model
Type
Various (Gaussian, Bernoulli)
Number of Arms (k)
5
Max Episode Length (T)
Number of Examples (N)
32768
Optimization
Optimizer
Type
AdamW 1 x 10-5 (0.9, 0.95) 0.01 Cosine Decay 0.1 1.0
Learning Rate Betas (31, 32) Weight Decay
LR Scheduler
Warmup Ratio
Gradient Clipping
Training Details
Batch Size
256
Epochs
16

---

Published as a conference paper at ICLR 2026
Goussland Varl Measfo
Semsulii Uniomm
Sarnoul Dubai.2
Gouns and Vark Nearii
0.59
1.31
0.80
ECE
3.01
2.04
1.2-
6.44
6.4
0.8
1.1
0.90
6.08
0.00
330
BernoultS, Uniferm
Casasand Vark MeanW:
Sursout Dehul.1
Couss and Vark Neart
3.3
0.9
3.3
6.5
0.12
0.22
3.1
0.00
0.09
130
2.5
064- (44-)o4bas)
Erers NL-00
BALG
Thamason Semoling
Greedy
Figure 8: Comparison of LLM policies against baselines on cumulative regret function fitting results. The first row shows the results of 7B models trained Gaussian second row shows the results of 7B models trained on bernoulli5.Oniff Evaluation is performed both in- (first column, highlighted) and out-of-distribution (other columns) as in Figure 3
and the
B DETAILS OF PERFORMANCE COMPARISON
We provide comprehensive experimental results of the LLM policies compared against baselines over range of environments and model sizes on cumulative regret at 50 and 300 steps. The obser- vation is consistent with the analysis in main text.
B. 7B MODEL COMPARISONS
The cumulative regret trends are consistent across evaluations at 50 and 300 steps. However, the longer 300-step horizon more prominently exposes the weaknesses of simple heuristics like e- greedy. At 50 steps, the imitation learning policies (RL-ALG and SFT) show some instability, likely due to the stronger mimicking effect of the UCB oracle in the initial exploratory phase.
The learned policies demonstrate effective generalization Gaussian5.Varf 3. environment, where the difficulty of identifying the optimal arm is comparable the GaussianS Varl MeanNO training setting. This generalization fails, however, when increased variance makes the task harder, as is the case in the Gaussians Varg" Meant environments. Here, exploration strategies developed in low-variance settings are hindered by their greedy bias, leading to poor performance under high uncertainty. Amidst this, the RL-OG policy begins to show a slight advantage. Finally, we note that the SFT policy, when trained on Bernoulli5.un form, consistently fails generalize any Gaussian environment (Figure 12).
higher variance in the
To quantify the asymptotic behavior the cumulative regret within 300 steps, we follow Nie et al. (2024) employ function fitting approach. We model the cumulative regret through time as v(() A log(1 (0g(1+1)) +1)a + 31, where 33 captures linear failure modes and the logarithmic term captures exploration costs. In Figure 8 find that pretrained L.LMs exhibit high linear coefficient (3), comparable to the Greedy baselines, indicating a failure to converge to the optimal arm. Learned policies instead show significant reduction 3 across both in-distribution and out-of-distribution evaluations, suggesting that fine-tuning minimizes asymptotic linear regret in-average. The consis- tently low MSE values and the visual alignment of the fitted curves validate that this parametric model accurately captures the regret dynamics of the evaluated agents (examples in Figure 9). We note that, similar to other regret-based analysis, this function-fitiing approach less sensitive to early failure signals than, for example, suffix fail rate. Since cumulative regret is averaged across episodes, early failures can be disguised by carly wins resulting from over-exploitation.
17

---

Published as a conference paper at ICLR 2026
94
180
256
240
50
178
359
170
150
200
350
119
33
3.6
159
200
250
76
ALALG
Mas
Not -00
Figure 9: Comparison of LLM policies against baselines on cumulative regret function fitting re- sults. The second row shows the results of 7B models trained on Gaussian5 -arl5 MeanNO. Evaluation is performed in-distribution.
18

---

Published as a conference paper at ICLR 2026
Serred It form
Bersul 5, ferm
Bersull t0 PeRtoZ
Serred P.
Bemou 6s petrao
20+
Gevorian3 vil Nen
Gaseoaet Ve: Neyrt""
Cauec art 1ar1 Mearill
Guger sef. War1, Mearlee]
Gacedinn, (ar2 Vienle
154
390-
Soursans, Wid Mortll
Sausian5, Vari Veanke
Saustien, Werl Veaws
Gasssions ve's Meard
Clans snt, Vars, Mearti
102
190
Thamosen Sampling
RLALO
Figure 10: Comparison of LLM policies (7B base model) against baselines on cumulative regret at 300 steps (outliers are trimmed). Results training environment has colored border.
Derroul 10 Unitom
Berredl C. Unitoom
Barnoul 1D, De tud
Semmel I., Delto
Berred r. Celso
Couss 10 Wirl Fronko
Saveees Well NisiNo"
Goustinn yer Heavi
Camss ani Vir1, Meanvi-
Cours onn Warkt Privko
150
Gluustart 2
Sauisso Meari-1
Cono Mrr. Meart
Dosssarr: Moant
Ceusiurs Mearti
132-
Apelt
Epallen Gready
Figure 11: Comparison of LLM policies (7B base model) against baselines on cumulative regret at 50 steps (outliers are trimmed). Results on training environment has a colored border.
19

---

Published as a conference paper at ICLR 2026
Berred 122 Untfrm
Ruresrs Infer"
Burnol PefudZ
Serral D.D.eall.2
Petut
Govstiants Wirl Hown
0asos an3, Vart, Mearlid
Causs ar5 Vert, Mearu
Goand s66 Var1 Mearlte)
Oasesiin5 Ver's Vovile
306
543-
390
143
Gourdann Wel Nesnk-1
Gaveree Ver Veanh-1
Gauerbed Vell Feawl:
Gauetieed Verl Neari
Gapne snf Ves Vearti
390
309
1990
530
diredy Thamazen Sumpling
1L-00
TLAAC
Figure 12: Comparison of LLM policies (7B base model) against baselines on cumulative regret at 300 steps (outliers are trimmed). Results training environment has colored border.
Bensal 20 Uniosm
Zereo is Unfoom
Barooiaa PetuRiz
Serrodl D Pelutz
Borod & pelur
Couso 10 Vark, Yaueh0
Gasolend Yolk Mauntt)
Gaowlard Var Muar
Caso end Verl, Vanni -
Curso Wer Pounho
122
Cousaaa55 16/3 MaarNis
Sousalnnd Ver Meani-1
Causs and Vari Meunti
Goundaan Wir Neant
Cousdard Mid MeanU
200
150
Figure 13: Comparison of LLM policies (7B base model) against baselines on cumulative regret at 50 steps (outliers are trimmed). Results on training environment has a colored border.
20

---

Published as a conference paper at ICLR 2026
B.2 3B MODEL COMPARISONS
Table 6: Analytics of baselines and 3B LLM policies trained on Gaussian5 Varl MeanNO, evaluated in-distribution.
Metric
AvgReward
BestArmFreq
GreedyFreg
SuffixFail
@1
50
300
50
300
50
300
50
150
Baselines
Apsilon-GGredd c=0.1
0.76
0,90
47.9
67.6
91.3
91.6
0.0
0.0
Thompson Sampling
0.77
1.00
55.8
78.5
67.0
85.2
0.0
0.0
Greedy
0.91
1.01
65.4
71.7
90.0
98.3
25.0
25.0
UCB c=0.5
0.91
1.04
67.7
80.6
83.3
95.4
3.1
4.7
Learned Agents
3b Pretrain
0.39
0.43
29.3
32.7
85.9
67.8
12.5
12.5
3b SFT
0.92
1.04
69.7
80.8
83.5
93.9
6.2
9.4
3b RL-OG
0.41
0.69
31.5
49.1
81.0
76.0
6.2
7.8
RL-STG
0.51
0.75
39.3
56.9
77.7
71.5
0.0
1.6
RL-ALG
0.81
0.95
60.2
71.2
81.7
89.0
14.1
17.2
Consistent with our main findings, results in Figure 13 and Figure 17 confirm that smaller models benefit less from reinforcement learning optimized directly for environmental reward signals. The RL-OG and RL-STG policies trained this way perform on par with the pre-trained model at 50 steps and achieve only small gains 300 steps with RL-STG generally outperforming RL-OG.
In contrast, both the imitation learning policies, RL-ALG and SFT, demonstrate a significant im- provement the pre-trained model. The SFT policy, in particular, emerges as the rop-performing method, achieving reliably lower regret across nearly all environments. This suggests that, even in the imitation learning setting, smaller models struggle with reinforcement learning optimization process itself. According to Table 6) SFT achieves AvgReward and BestArmFreg comparable to the UCB teacher in-distribution. Its performance identifying the best arm continues improve with more trials, even in most -istr---distiibution environments (Figure 14). We once again ob- serve the previously noted generalization failure of SFT this model size, where it fails transfer from the Bernoul 1il innn faaiffoo form environment to Gaussian environments with negative rewards Figure 17).
The pre-trained Qwen 2.5 3B model exhibits distinct exploration pattern compared to its 7B coun- terpart. While the pre-trained 7B model starts an episode with high exploration and becomes more exploitative over time, the 3B model begins with highly greedy strategy (GreedyFreg = 86%) and becomes more explorative. This causes its ability to identify the best arm plateaus very early in the caussian5 Varl MM environment. These behavioral differences lead different training dynamics: the 7B model consistently reduces exploration throughout the training iterations, while the 3B model first undergoes a phase of increasing exploration before reducing it until convergence.
Across the board, all learned agents show lower GreedyFreq at 50 steps than the pre-trained model. As trials progress, the two successful imitation learning policies (RL (RL-ALG and SFT) adopt a more greedy exploitation strategy. As result, they both suffer from higher suffix failure rate com- pared to RL policies trained on environmental feedback. This reinforces our conclusion that their performance gains are associated with more sophisticated greedy policies.
21

---

Published as a conference paper at ICLR 2026
Gaussiank Varl MeanNO K-5
BernuulIK Uniform
BermouliKK Delta0.2
K-10
K-5
K-10
K-5
K-10
0.7
0.7
0.5
0.5
0.6
BestAmire
0.6
0.5
0.5
0.3
0.4
0.3
0.2
0.3
0.2
0.2
0.1
0.2
200
200
200
200
200
steps
steps
steps
Figure 14: Generalization to environments with 10 arms for Gaussian-traines LLM policies (3B base model). Best arm selection frequency is reported.
22

---

Published as a conference paper at ICLR 2026
Oerrest It, Form
Bensul 5, ferm
Bersull to PerooZ
Serred D_Pe266.2
Bemou 15 petra
230
30-
Gevorban1 1M1 Nen
Gaseonet Ve: Novrt""
Cauec Sr5 Sar1 Mearü1
Guuee sef. Var1, Mearlie]
Gacedinn (er3 Vien
406
206
290
190-
Coursans, Var Mosrle
Sausaan Var Veank
Saustian, Vorl Veaw
Gasssiors Ve3s Weand
Cans srt, Vars, Mearti
1209
800
Thamosen Sampling
RLAAL
Figure 15: Comparison of LLM policies (3B base model) against baselines on cumulative regret at 300 steps (outliers are trimmed). Results training environment has colored border.
Di 10 Unitom
Derredlff C. Unitomm
Barnout I0O, De tud
Semeul IT, Delto
Berrod r. Celso
Causs 10 Virl Peosko
Saveeus Ve'l Nosilo"
Gauotini yar Heavt
Carnt ani 1r11, Meani-1
Coursarts Warkt Privke
175
120
333
250
250-
Gausstrrs Mord Moanti MordtMa
Savisoo Mard Meari-1
Cuas Maree_Wr.MMMaa Meat.M
Dosssarr Muart
Ceusaurs Mars Meanti
300
190
Apell
Epailon Sready
Figure 16: Comparison of LLM policies (3B base model) against baselines on cumulative regret at 50 steps (outliers are trimmed). Results on training environment has a colored border.
23

---

Published as a conference paper at ICLR 2026
Berred I22 Un
Rererrs Infer"
Brrnoll PefudZ
Serral D.D.eau6.2
15 Pulut
290
Govstiants Wirl Mour
davos an3 Vart, Yearlid
Causs ar5 Verl Mearu
Goand s66 Var1) Mearlte)
Davesiin5 Ver's Veanle
300
437
Gourdann Wrl Nennk-
Gaveaee Ver Veanh-1
Gauerbed Vell Feael:
Gauetieed Verl Neyri
Gupne snf Ver Vearti
1790
2250
150
106
500
Spolin diredy Thanazen Sumpling
10-00
PLALC
Figure 17: Comparison of LLM policies (3B base model) against baselines on cumulative regret at 300 steps (outliers are trimmed). Results training environment has colored border.
Bansal 20 Uniosm
Zereo is Vnfuum
Barou Fu Perutiz
Berrodd D Pelut
Borodd & peluut
Couso 10 Vark Yaueh0
Gasolent Nol Mauntt)
Gaowlard Var Muark
Caso end Verl VanV -
Corso ur5. Wes Younh
17-
350-
100
230
190
Cousaaa55 16/3 MaarNi
Sousllnnd Ver Peani-1
Caus and Vari Meunti
Gauadard Wir Neant
Gausdard Mid Meant
30
100
Figure 18: Comparison of LLM policies (3B base model) against baselines on cumulative regret at 50 steps (outliers are trimmed). Results on training environment has a colored border.
24

---

Published as a conference paper at ICLR 2026
C DETAILS OF IMITATION LEARNING ANALYSIS
We investigate why an imitation learning policy might outperform its teacher by analyzing its ad- herence key decision-making heuristics. This section expands upon the main by presenting results from complete set of experimental environments.
A key finding is that both imitation learning policies (RL-ALG and SFT) make fewer (imitation) errors in high-variance environments, This is attributed to the teacher UCB policy (C=0.5) itself behaving more greedily in these settings, matching the exploitative bias of the imitation learning policies.
We find that the SFT agent's mistakes reveal errors in both simple arithmetic (summation, sub- traction) and complex calculations (logarithms, square roots). A prominent failure mode emerges when the Bemoulli-trainee policy observes negative rewards: often struggles with summations involving these numbers and subsequently disregards its own UCB calculations. For instance, in the Gauss s iessianS, 2a555aar3333 Var33MeanNC environment,
agent chooses an arm different from the one with the highest calculated UCB value 78% of the time. This divergence is sensitive to the reward dis- tribution; lowering the environment's 's mean reward by 1 increases this deviation rate to 89%, while raising the mean by 1 reduces it to 44%. This behavior indicates regression in the LLM's pabilities, leading to hallucinations in its reasoning. Future work can explore mixed training with mathematical data to alleviate this issue.
We previously discovered that the RL-ALG agents converge to suboptimal variants of the UCB al- gorithm. This finding is both interesting and disappointing. On one hand, it demonstrates that agents can discover novel solutions from sparse reward signals received only at the end of a response. On the other hand. suggests that either the oracle policy that credit assignment is a significant challenge. By manually inspecting rollouts from early train- ing iterations, we find that the correct UCB formula did appear, but calculations were frequently incorrect due to the base model's weakness in complex operations like square roots and logarithms (Figure 23). This points to a credit assignment issue, where the agent incorrectly attributes poor outcomes to the formula itself, rather than to flawed calculations suboptimal hyper-parameter choices. Future work could explore more fine graingd RL signals to address this problem.
encountered during RL exploration or
25

---

Published as a conference paper at ICLR 2026
iemtodie..nttmmm jnits
Ber Uniifrm
Beroulilo, Pelen2
Semouils Delbb
Bemoull Dettod
0.50
0.59
0.00
0.00
0.0
0:0
0.00
120
2.00
Gauesiadlo Vari MeanNo
1,00
Goussanns Virl Mearho
1.0
Gaussans Vell Neants)
130
Caursann Vir) Meunk+1
3,00
Gaussann Var3 MeanNo
106
200
280
300
300
360
200
238
209
033
0.79
0.72
6.7
0.00
Time Step Tajectory
Figure 19: 7B SFT agent trained on Gaussian environments: UCB error by step.
Scmoulls Eror Tate
w.. Ary, Als. Daha
Eemcolltio Uniform
Denaaa
Datab.1
0.75
0.75
0.25
022
282
.63
202
230
Caroddan10 Mearbii
Ceuosdand Hearti
Gauezarr Wen Neanle
Gauscant Newntle
Gevesians Ver Mearto
g
0.75
-10
0.25
025
335
6:75
Cousaaedd Var5 Mearti11
Gauosand Wer Mearhi11
1.33
Ga and Vart NeanU
Gasas and Vorl MearU
Cuussland Verd MaarU
03.07-
0.0
106
203
0.30
300
200
0.30
0.30
0.00
200
200
Step T.jeectoyy
Figure 20: 7B SFT agent trained on Bernoulli environments: UCB error by step.
26

---

Published as a conference paper at ICLR 2026
64
04
0.0
200
180 281
zif
130
201
60
100
201
6.0
20
1.0
Gaussoon0
Gaussion
Moarhen
3o Maann
201
206
200 280
100
200
100
200
130
200
Gauesiend
NeanN+1
Gauislar5
Traeetory
Figure 21: 7B ALG agent trained Gaussian environments optimize UCB reward signal: match by step. UCB_ here is the UCB variant Q:(a) +Cx discovered and consistently used.
log (a)+)+ which the agent
Nr(a)
Gmady
USB
Unitom
Beroulls Dabat.3
Datan.1
1.5
Goussian20 Wer1 Maanto
16
Couss und Wil MearNo
Gusssin5 We1 Mearhh1
Gaussland Wart Mearhiis
Couslard 1or3 Maunto
0.5
142
0.2
Cauredent Wel Meanlk-1
1.P
Gauedien (r7) Mnanke]
GeLoE and Veri Meant
GeLoe and Ver Meant
Gelimdand Var5 Meant
22
289
100
200
100
Time Stop Tajectory
Figure 22: 7B RL-ALG agent trained on Bernoulli environments to optimize UCB reward signal: match rate by step. UCB Var here is the UCB variant Qc(a) + C consistently used.
that the agent discovered and (a))
27

---

Published as a conference paper at ICLR 2026
D CONTEXTUAL BANDITS ON MOVIELENS
To demonstrate the generalization capabilities of our RL approaches beyond Multi-Armed Bandits (MAB), we conducted experiments on Contextual Bandit setting using the MovieLens environment from BanditBench (Nie et al. 2024).
D.I ENVIRONMENT SETUP
Using the open-source implementation of BanditBench, we construct a contextual bandit task based on the MovieLens- 100K dataset (Harper & Konstan, 2015). The dataset contains 100,000 ratings for 1,682 movies from 943 users, including demographic information such age, gender, and occupation. Only the first 100 users are seen during training, the rest of them are used for evaluation.
To align with the standard linear assumption used in baselines like LinUCB, the environment is con- structed via low-rank approximation. Specifically, the top K popular movies are selected to form the action space. A user preference matrix P E R RNN is constructed and decomposed using Singular Value Decomposition (SVD) such that P z UEVT. Here, represents the user embedding matrix, V the movie embedding matrix, and Σ the diagonal matrix of singular values. The ground-truth reward for a user and movie j is deterministic: ri.j = uu Eoj.
D.2 EXPERIMENTAL RESULTS
Following the same training setting described in the MAB task, we fine-tune the Qwen 2.5 7B model over horizon of 50 steps with 5 arms (recommending from 5 top movies). Note that as the environment has deterministic reward, RL-STG is equivalent to RL-OG. We compare our methods against the standard Pretrained LLM and LinUCB (Chu al. 201T) (exploration ratio 0.5).
As shown in Table 7 both RL with environmental feedback (RL-OG) and RL with algorithmic reward (RL-ALG) significantly reduce regret compared to the Pretrained LLM. Notably, our multi- turn RL implementation (RL-OG) outperforms the strong LinUCB baseline. We observe that RL- ALG performs worse than RL-OG; this is likely because RL-ALG attempts to approximate exact LinUCB calculation-al task more complex than standard UCB-often resulting in a greedy approximation where the model converges to the most frequently chosen action of the teacher.
Table 7: Cumulative Regret on MovieLens (Horizon=50,3 5 Arms). Results show mean and standard error across 64 episodes varying random seeds.
Method
Cumulative Regret
LinUCB
61.09 (+:2.77)
7B Pretrain
100.84 (#3.09)
7B RL-OG (full history)
46.64 (+1.70)
7B RL-OG (no history)
58.71 (#1.32)
RL-ALG
73.23 (#1.78)
D.3 ANALYSIS AND LIMITATIONS
While these results appear promising, a fundamental limitation exists in using this specific Movie- Lens setup for meta-bandit training. Unlike MAB settings where we can generate infinite environ- ments with varying parameters, this Movielens contextual bandit setup represents a single bandit instance defined by a static dataset.
Because the action set is fixed and the linear function defined by Σ is universal across all interactions, the task essentially requires the model to map user features (provided in the prompt) to a reward distribution via static function. This allows the model to memorize the underlying function during training rather than performing online exploration. This hypothesis is supported by our ablation study in Table 7 where the RL-OG (no history) agent, which has no access to previous interaction feedback, still achieves lower regret 758.71) than the LinUCB baseline (61.09). This indicates the model is relying more memorized patterns than in-context bandit learning. Consequently, while
28

---

Published as a conference paper at ICLR 2026
approach generalizes this setting, prioritize controllable MAB benchmarks in the main text to ensure rigorous evaluation of the model's online learning and exploration capabilities. We leave the veta-bandit setup of realistic contextual bandit scenarios to future work.
MovieLens Prompt Example
You are an AI movie recommendation assistant for streaming platform powered by bandit algorithm that offers wide variety of films. There are unique movies you can recommend, named
Star Wars (1977)
2. Contact (1997)
Fargo (1996)
4. Return of the Jedi (1983)
Liar Liar (1997)
When user visits the streaming platform, you assess their demographic description to choose a movie to suggest. You aim to match the user with movies they are most likely to watch and enjoy. Each time user watches recommended movie, you adjust your recommendation algorithms to better predict and meet future user preferences.
So far you have interacted 5 times with the most recent following choices and rewards:
This person a 39-year-old man, working as a scientist and live in University park of Cook county, Illinois. User preference vector: [-0.01, 0.04, -0.01, -0.04, 0.00]. Recommended movie 2
Context:
Reward: 4
Context: This person is a 29-ycar-old woman, working as administrator and live in Crofton of Anne Arundel county, Maryland. User preference vector: [-0.05, 0.04, 0.05, 0.01, 0.01]. Recommended movie
Reward: 5
Context: This person is a 36-year-old woman, working as a writer and live in Los angeles of Los Angeles county, California. User preference vector: [-0.02, -0.01, -0.07, 0.05, 0.01]. Recommended movie 1
Reward: 0
Context: This person is 45-ycar-old woman, working as educator and live in Boulder of Boulder county, Colorado. User preference vector: [-0.05, -0.01, -0.05,, Recommended movie 1
Reward: 5
Context: This person is 32-year-old man, working engineer and live in Little canada of Ramsey county, Minnesota. User preference vector: [-0.04, -0.00, -0.02, -0.04, -0.00). Recom- mended movie Reward: 4
You have a new user:
Context: This person 24-year-old woman studying as student and live in Huntsville of Madison county, Alabama. User preference vector: [-0.04, 0.03, 0.05, -0.02, -0.01].
Which movie (id) should be recommended next? Show your reasoning be- tween <think> </think> tags and the recommended movie index between <answer> </answer> tags, for example: <answer>> movie </answer>.
29

---

Published as a conference paper at ICLR 2026
RL with Algorithmic Reward (7B Gaussian; Best Checkpoint)
In 5-armed bandit problem, here the results of previous arm pulls:
Arm 0: pulls, average reward -1.421
Arm 60 pulls, average reward 1.110
Arm 2: pulls, average reward -2.903
Arm 3: pulls, average reward -1.197
Arm 4: pulls, average reward -1.842
Which arm should be pulled next? Show your reasoning <think> final answer in <answer>> </answer> tags.
</think>
tags and your
<think>> To decide which arm to pull next, we can use the Upper Confidence Bound (UCB) algorithm, which balances exploration and exploitation. UCB selects the arm with the highest upper confidence bound, which is the sum of the estimated mean reward and an exploration
term. The formula for UCB is: UCB average reward + C log(n) n number times the arm has been pulled, and (C) a tuning parameter typically set to or 2. Let's calculate the UCB for each arm using C
where n is the
1og(2-1) 1)
For Arm UCB, 11.421 + 1x
1.421 0.549 -0887
For Arm UCB, = 1.110
log(60+11
1.110 + 0.040 x 1.150
60
For Arm 2: UCB2 = 2.903 + 1
1og(2-1)
22903 + 0.549 ~ -2354
2
For Amm 3: UCB3 - 1..99 + 1
Ing(3-1 1)
-.199
0.302 ~ 0.895
For Arm 4: UCB, 1..82 + 1 loR(1-1)
-1.842
0.693 1..49
Now, we compare the UCB values:
Arm 0: -0.872
Arm 1.150
Arm 2: -2.354
Arm -0.895
Arm 4: -1.149
The highest UCB value is for Arm 1, which suggests we should pull Arm next.
</thik>> <answer>> The arm that should be pulled next is Arm 1. </answer>>
30

---

Published as a conference paper at ICLR 2026
RL with Algorithmic Reward (7B Bernoulli; Best Checkpoint)
In a 5-armed bandit problem, here are the results of previous arm pulls:
Arm O: 19 pulls, average reward 0.541
Arm 1: pulls, average reward -0.879
Arm 2: pulls, average reward -2.651
Arm 3: 46 pulls, average reward 1.240
Arm pulls, average reward -1.744
Which arm should be pulled next? Show your reasoning in <think> </hink>>
tags and your
final answer in <answer> </answer>> tags.
<think> To determine which arm to pull next, we can use the Upper Confidence Bound (UCB) algorithm, which balances exploration and exploitation by considering both the aver- age reward and the uncertainty associated with each arm. The formula for UCB is: UCB = Average Reward + Exploration Term
For simplicity, we can use a basic form where the exploration tern is inversely proportional to the square root of the number of pulls: UCB Average Reward + Number of Pulls
where k is
a constant, typically set for simplicity. Let's calculate the UCB for each arm: Arm UCB, = 0.541 + Vig
I A 0.541 + 0.229 ~ 0.770
Arm UCB: 00.89 + _ -0.879 + 0.121
VI
Arm 2: UCB2 -2.551 + 1
~ -2.651 * 1.651
vi
Arm 3: UCB, = 1.240 +
~ 1.240 + +0.120 ~ 1.360
V16
Arm 4: UCB, = 1.374 VI ~ -1.374 +1 -0.374
Now, we compare the UCB values: UCB, ~ 0.770
UCB, 0.121
UCB, -1.651
UCB; 1.360
UCB, -0.374.
Clearly, Arm 3 has the highest UCB value, indicating it is the best choice according to the UCB algorithm. </think>
<answer>> The arm that should be pulled next is Arm 3. </answer>
31

---

Published as a conference paper at ICLR 2026
RL with Algorithmic Reward (7B Gaussian; Iteration 50 Checkpoint)
In 5-armed bandit problem, here are the results of previous arm pulls:
Arm 0: pulls, average reward -0.282
Arm 10 pulls, average reward 1.723
Arm 2: 5 pulls, average reward 1.255
Arm 3: pulls, average reward -1.101
Arm 4: pulls, average reward 0.995
Which arm should be pulled next? Show your reasoning <think> final answer in <answer>> </answer>> tags.
</think>
tags and your
<think> To decide which arm to pull next, algorithm, which balances exploration and exploitation. UCB selects the arm with the high- est upper confidence bound of the expected reward. The formula for UCB is: UCB
use the Upper Confidence Bound (UCB)
Average Reward + +C
log total number of pulls
number times arm was pulled
Here, (C) is a tuning parameter that controls the trade-off between exploration and exploitation. For simplicity, we can assume C= First, calculate the total number of pulls: 2 2 10 2 21.
Now, apply the UCB formula each arm:
Arm O: UCB, 0..822 +
21
0.282 + 0.956 0.674.
2
Arm UCB: = 1.723 X
Tng21 10
1.723 + 0.302 = 2.025.
Arm 2: UCB, = 1.255 + 1 x
log 21
~ 1.255 + 0.509 = 1.764.
Arm 3: UCB3 11100
1.101
0.956 -0.145.
Arm UCB, = 0.995 +
20
0.995 + 0.956 1.951.
Comparing these UCB values, Arm has the highest upper confidence bound. </think>
<answer> The that should be pulled next is Arm 1. </answer>
Figure 23: example generated by RL-ALG policy iteration 50 (7B Gaussian)
32

---

Published as a conference paper at ICLR 2026
E LLM USE DISCLOSURE
Using LLMs to help with paper writing. Commercial LLMs were used to correct typos and grammar, suggest alternative phrasings, and provide insights on the clarity and readability. All LLM-generated text was reviewed, edited, and approved by the human authors.
Using LLMs as research assistant. LLMs assisted with brainstorming experimental designs, suggesting analysis approaches, searching potentially relevant prior work, and producing code scaf- folding and completion. The human authors provided the research context, validated the literature identified by LLMs, verfied all analysis and results, and adapted or often rewrote the LLM- LLM-generated content before inclusion.
33


Reviews:
[{"review_id": "cfXau6DJaQ", "reviewer": "Reviewer_USow", "summary": "This paper studies how different fine-tuning paradigms shape the exploration and exploitation behaviors of LLMs in multi-armed bandit (MAB) settings. The authors train Qwen-2.5 3B and 7B models on MAB tasks with different reward signals:\n> RL-OG: standard stochastic rewards, \n\n> RL-STG: regret-shaped strategic rewards, and\n\n> RL-ALG: imitation of the UCB oracle via algorithmic rewards.\n\nThe work demonstrates that both SFT and RL reduce regret and achieve performance comparable to theoretical baselines like UCB and Thompson Sampling, with generalization to unseen environments and 6$\\times$ longer horizons. However, behavioral analysis shows that these gains arise from emergent exploitative tendencies since trained agents become greedier and sometimes abandon exploration prematurely. RL-ALG agents trained to imitate UCB outperform their teacher by adopting more exploitative variants of it.\nThe paper concludes that while both SFT and RL enhance decision-making, they also introduce bias toward short-term exploitation, highlighting the need for reward and data designs that explicitly sustain exploration.", "questions": "Exploration bias mitigation – Could future training include explicit exploration bonuses (e.g., curiosity or entropy regularization) to test if the emergent greediness persists?\n\nDo the authors have an intuition of how findings might transfer to contextual or Markovian tasks where exploration requires memory and state estimation?\n\nThe finding that RL-ALG outperforms its UCB teacher is quite interesting. Could the authors analyze whether this over-exploitation emerges from token-level credit assignment or from the episodic reward structure?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "- **Originality and significance**: This work provides a unified framework comparing SFT and RL fine-tuning for LLM agents on the same controlled MAB setup. The strategic and algorithmic rewards are well-motivated and address variance and credit-assignment issues in RL with LLMs. \n- **Quality**: This paper includes experiments across Gaussian and Bernoulli bandit families, including cross-distribution generalization and longer horizons, which strengthen the empirical claims. Metrics like suffix failure and greedy frequency are used to reveal qualitative behavioral shifts alongwith quantitative evaluation.\n- **Clarity**: The paper is generally well-written with clear implementation details and code release commitments.", "weaknesses": "- Limited task diversity: Experiments are confined to simple bandit environments, therefore claims about general agentic learning remain somewhat speculative. \n\n- Model scalability: There is no discussion of whether the observed training and inference dynamics hold even with larger models and across different model families. \n\n- While the paper uncovers behavioral tendencies, it stops short of offering causal or mechanistic explanations of why greediness emerges under RL/SFT objectives.\n\n- Compared to the analysis of RL approaches in LLM training, the SFT analysis is less thorough, especially regarding data sampling effects and robustness to arithmetic errors. \n\n- No explicit exploration-promoting baseline: Methods like intrinsic reward shaping or information gain are not compared, though they would provide valuable context.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zG9T5b3CRv", "reviewer": "Reviewer_CjPh", "summary": "This submission studies how LLMs learn to balance exploration and exploitation when trained to solve multi-armed bandit (MAB) problems, using both supervised fine-tuning and reinforcement learning. They train LLMs on various MAB environments using RL with three forms of reward design: original reward (i.e. the raw environment rewards), strategic reward (a normalized, regret-shaped reward that reflects how close the agent’s action is to the optimal arm at each tilmestep), and algorithmic reward (a signal that rewards the agent for matching the decisions of an expert oracle, specifically the UCB algorithm). For supervised fine-tuning, they train the LLM on synthetic data generated from UCB expert trajectories, including step-by-step chain-of-thought demonstrations of UCB value calculations. \n\nThey evaluate the performance of these methods (when fine-tuning Qwen models) on Gaussian and Bernoulli MAB environments. They find that the fine-tuned models outperform vanilla models on these tasks, and that policies trained with UCB imitation perform best. These methods also perform comparably to UCB and Thompson sampling. \n\nUpon further analysis, the authors find that these gains often come from the models adopting greedy behaviors and under-exploring.", "questions": "What are you trying to show when evaluating these fine-tuned models on MAB tasks? It is not very surprising that a transformer will behave like UCB if you train it to.", "limitations": "", "rating": 2, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Using LLMs to solve decision-making tasks under uncertainty is an important next frontier, so the problem being studied is well-motivated. While the authors are not the first to fine-tune LLMs to solve these sorts of bandit tasks, their proposed reward designs are novel, from what I can tell. The finding that gains often stem from more greedy behavior is also interesting, and largely matches the findings of Krishnamurthy et al for vanilla models which are not fine-tuned.", "weaknesses": "I am not entirely sure what this paper is trying to accomplish. The typical motivation for studying LLMs’ ability to solve bandit tasks is because we want to design AI models capable of solving complex, text-based, decision making tasks under uncertainty. This is because we don’t currently have good algorithms for solving these types of tasks. Bandits get to the essence of the exploration/exploitation trade-off, and so they can be a useful abstraction. \n\nHowever, I am not sure what utility we get from fine-tuning LLMs to be more like existing algorithms, without evaluating their performance on some complex task that existing algorithms do not do well in (or are not even applicable to). (We don't need to reinvent the wheel to solve MAB tasks, as we have good algorithms for these types of tasks already.)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yMT7swzwuN", "reviewer": "Reviewer_pbuB", "summary": "This paper investigates how Supervised Fine-Tuning (SFT) and Reinforcement Learning (RL) training paradigms shape the exploration strategies of Large Language Models (LLMs) when solving Multi-Armed Bandit (MAB) tasks, treating the LLMs as meta-bandit agents.\n\nI currently think this paper provides a lot of value to the \"learning to learn\" / \"learning to explore\" community. However, I raised several questions and based on the authors' rebuttal response, I reserve the right to change/update my score.", "questions": "Typo 1: In Figure 3, it says RL-STG, it should be RL-STR \n\n1. RL-STR is not significantly better than RL-OG. Just comparing the average, in 3 out of 8 domains (Figure 3), it's better. It's worse in 3 out of 8. In 2 it's about the same? For people who might want to train exploration policy in a realistic setting, how would you give them suggestions on what reward design to use? \n\n2. Table 2, you did some behavioral analysis and citing a prior work. Krishnamurthy et al. (2024) also proposed MinFrac. Do you think this is a metric worth including? \n\n3. [1] also proposed to fit a function form over steps $T$ on average cumulative regret -- and try to describe the slope/speed of learning/unlearning. Would such analysis yield additional insights for your setting?\n\n4. What future directions are opened up by your analysis, besides moving to more realistic domain? In your GRPO training (with RL-OG), do you see length hacking (i.e., with training continues, the length in thinking tokens becomes longer and longer)? In appendix, we saw that RL with ALG reward learns to compute UCB. Can you:\n   - Provide sampled generations with base model but sampled using your prompt/pipeline? Do they already know that they should calculate UCB values?\n   - Can you provide sampled generation from RL-OG and RL-STR for us so we know if these also learned (on their own) to compute UCB values?", "limitations": "", "rating": 10, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. The paper has extremely clear writing\n2. The authors disambiguated different training strategies and setups very well. \n3. This paper introduced token-level reward derived from GAE, which improved upon prior work.\n4. Each reward design is principled and reasonable -- incorporating all possible learning signals. \n5. The paper is well-situated compared to prior works, investigating areas where prior works didn't, adding critical knowledge/understanding to the entire teaching LLM to explore space.", "weaknesses": "The paper doesn't have obvious flaws/weaknesses, but here is some nitpicking weaknesses:\n\n1. As a field, the learning to explore community needs to move beyond toy setting. [1] proposed and [2] included the MovieLens environment, which is a good first step. Behaviors of RL vs SFT and whether we need $\\pi^*$ (optimal exploration policy) need to be answered in slightly more realistic setting. Many algorithms (like SGD) might be flawed in constructed setups, but they work really well in practice. Even though I think this paper has enough value without exploring those more realistic settings, I would encourage the authors to extend the paper to cover those settings.\n\n2. The conclusion from the experiment seems a bit unclear (see the question part).\n\n[1] Nie, Allen, et al. \"Evolve: Evaluating and optimizing llms for exploration.\" arXiv preprint arXiv:2410.06238 (2024).\n\n[2] Schmied, Thomas, et al. \"Llms are greedy agents: Effects of rl fine-tuning on decision-making abilities.\" arXiv preprint arXiv:2504.16078 (2025).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)