Retrospective In-Context Learning for Temporal Credit Assignment with Large Language Models
Authors: Wentse Chen
Jiayu Chen
Fahim Tajwar
Hao Zhu
Xintong Duan
Ruslan Salakhutdinov
Jeff Schneider
Venue: NeurIPS 2025 poster ()
Keywords: In-Context Learning
Credit Assignment
Large Language Models
Reinforcement Learning
Primary area: reinforcement_learning

Abstract: Learning from self-sampled data and sparse environmental feedback remains a fundamental challenge in training self-evolving agents. Temporal credit assignment mitigates this issue by transforming sparse feedback into dense supervision signals. However, previous approaches typically depend on domain-specific value functions for credit assignment, which suffer from poor sample efficiency and limited generalization. In this work, we propose to leverage pre-trained knowledge from large language models (LLMs) to transform sparse rewards into dense training signals (i.e., the advantage function) through retrospective in-context learning (RICL).  We further propose an online learning framework, RICOL, which iteratively refines the policy based on the credit assignment results from RICL. We empirically demonstrate that RICL can accurately estimate the advantage function with limited samples and effectively identify critical states for temporal credit assignment. Extended evaluation on the BabyAI benchmark shows that RICOL significantly improves sample efficiency compared to traditional online RL algorithms while achieving performance comparable to imitation learning from expert demonstartions.  Our findings highlight the potential of leveraging LLMs for temporal credit assignment, paving the way for more sample-efficient and generalizable RL paradigms.

Retrospective In-Context Learning for Temporal Credit Assignment with Large Language Models
Wen-Tse Chen'
Jiayu Chen?
Fahim Tajwar'
Hao Zhu
Xintong Duan'
Ruslan Salakhutdinov
Jeff Schneider
Carnegie Mellon University
2 The University of Hong Kong
3 Stanford University
Abstract
Learning from self-sampled data and sparse environmental feedback remains a fundamental challenge in training self-evolving agents. Temporal credit assignment mitigates this issue by transforming sparse feedback into dense supervision signals. However, previous approaches typically depend on learning task-specific value functions for credit assignment, which suffer from poor sample efficiency and limited generalization. In this work, we propose leverage pretrained knowledge from large language models (LL.s) to transform sparse rewards into dense train- ing signals (i.e., the advantage function) through retrospective in-context learning (RICL). We further propose an online learning framework, RICOL, which itera- tively refines the policy based on the credit assignment results from RICL. We empirically demonstrate that RICL can accurately estimate the advantage function with limited samples and effectively identify critical states in the environment for temporal credit assignment. Extended evaluation four BabyAl scenarios show that RICOL achieves comparable convergent performance with traditional online RL algorithms with significantly higher sample efficiency. Our findings highlight the potential of leveraging I.LMs for temporal credit assignment, paving the way for more sample-efficient and generalizable RL paradigms.
1 Introduction
Online learning with LLMs, guided by self- relf-generated data and environmental feedback, offers promising research direction for advancing beyond the constraints of demonstration (Dong et al.) 2024). However, this task is inherently difficult because valuable environmental feedback is often sparse [Andrychowicz et al. 2017 Sukhbaatar et al. 2017). This challenge is particularly evident in multi-turn settings, where agents must execute a sequence of correct actions to receive a reward signal. Sparse environmental feedback increases both the sample complexity and the instability of the learning process (Chaudhari et al.) 2024 Cao et al. 2024]. In this work, explore effective temporal credit assignment methods to convert sparse feedback into dense training signals based on a creative of LLMs, enabling the identification of critical states and actions in the environment and facilitating more efficient online learning (of LLM agents).
In particular, we adopt LLMs as policies and update them using a novel Retrospective In- In-Context Learning (RICL) algorithm. RICL designed specifically for multi-turn setting. At each turn (i.e., environment time step), RICL first analyze environmental feedback (i.e., reward signals) by leveraging the pretrained knowledge of an LLM reflector, then incorporate this analysis into the prompt to perform in-context update of the LLM policy. Further, introduce novel paradigm to estimate the advantage function of an LLM policy by utilizing the log- prgbbbbbbilities both the original policy and its in-context updated version. This process is theoretically grounded, and our experiments demonstrate that it can accurately estimate the advantage function with high sample efficiency. In this way, transform sparse reward signals into advantage functions, which are
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

dense training signals facilitating both temporal credit assignment and policy training, These improvements stem from the pretrained knowledge in LLMs and our new approach estimating advantage functions using L.Mss.
Further, we introduce RICOL,, a novel online learning framework for LLMs that iteratively refines the policy based on the credit assignment results from RICL. Leveraging the accurate credit assignment performed by RICL and the strong generalization ability of LLMs, RICOL is significantly more sample-efficient than traditional online RL methods across multiple language-conditionee, sparse- reward sequential decision- becision-making tasks. This demonstrates the potential of our algorithm to enable LLMs to self- through online learning.
In summary, our main contributions as follows: (1) We propose RICL for temporal credit assignment, which transforms sparse reward signals into advantage functions by comparing the log- probabilities of L.LM policies before and after an in-context update. (2) We propose RICOL., online learning framework that uses advantage weighted regression to incorporate credit assignment results (i.e., advantage functions) from RICL into the LLMs' parameters. This integration enables LLM agents to self-improve based on sparse environmental feedback. (3) Empirical results demonstrate the effectiveness of RICL in temporal credit assignment and the efficacy and efficiency of RICOL in iterative policy improvement. Altogether, RICL and RICOL represent a more sample-efficient and generalizable RL paradigm for LLM agents.
2 Related Works
In recent studies, LLMs have demonstrated advanced capabilities in self- verifying generated responses and correcting potential issues through in-context learning (Madaan et al. 2024, Kim et al. [2023]. However, critiques have suggested that intrinsic self-correction, in the absence of ground truth environment feedback, may always enhance and could potentially degrade performance of LLMs [Huang et al., [023]] Olausson et al. [023] Valmeekam et al. [2023]. In contrast, focus is learning from environmental feedback, challenging task due its sparse and complex nature.
Intrinsic Self-Correction:
Self-Correction based on an Extra Reflector Network: Another line of research aims to improve the self-correction capability of LLMs by line-tuning it on an external dataset (Yao et al.] 2023]. It often requires to collect additional dataset especially tailored for the training of a reflector network. For instance, Chen et al. [2024) design an erroneous solution rewriting task for reflector training. In contrast, we perform self-correction using free-form environmental feedback and do not need train an extra network.
based on Induction: Prior work has explored encoding past experiences into text- form memory and incorporating this memory into prompts to enhance decision-making makinn in subsequent trials [Shinn et al.) 2024 Zhao et al. 2024 Zelikman et al. 2022). There is also a line of works leveraging LLMs to generate rewards - cither as codes or natural language prompts - and iteratively
refine these rewards based on environmental feedback through in in-context learning [Ma et al. 2023
Kwon et al.) 2023 Yu et al. 2023 Li et al. 2024). These studies assume that LLMs, through in-context learning, can infer environmental rules and adapt to new trajectories/experieeee with only a few observed transitions. In contrast to these approaches, we assume that the rewards or reflections obtained from trajectory not directly transferable to other trajectories. Thus, in this work, proposed to use in-context learning in a "retrospective" manner.
Self-Correction Through Preference Alignment: Iterative RPO [Pagg et al. 2024 labels preference data based on environmental feedback and uses this feedback as a supervised signal to fine-tune LLMs. RICO-GRPO (Wang et al., 2025] use trajectory level reward and ground normalization to estimate the advantage function for multi-tur online RL training. However, these methods don't t perform explicit temporal credit assignment. In contrast, our approach generates dense rewards by leveraging the pretrained knowledge of LLMs through in-context learning. This enables the policy to be trained with more informative supervision signals.
Temporal Credit Assignment using LLMs: The goal of temporal credit assignment is to identify the critical states and actions in sequential decision-making. A common approach to credit assignment involves estimating value or advantage function based on learning experiences (Schulman et al.)
2015, Ahmadian et al. 2024). Unlike RICO-PPO [Wang et al. 2025 training value network from

---

scratch, which can be sample inefficient, our approach leverages in-context learning with pretrained LLMs perform credit assignment more effectively. Please refer to Table for more intuitive comparison of our proposed method with related works on self-correction in LLMss
3 Preliminary
Markov Decision Process: A Markov Decision Process (MDP) can be described tuple P. Po). Here, S and A represent the state and action space, respectively; P: AxS [0, is the transition kernel; S x A + R is reward function; 7 E (0,1) 1) is the discount factor; P-(.) denotes a distribution of the initial state.
KL-Regularized Policy Updates: KL-regularized policy optimization [Abdolmaleki et al. 2018 enhances policy stability by constraining each update to remain close to the previous policy. The objec- tive is to learn new policy * that maximizes the expected advantage while penalizing deviations from the old policy: Tx+1 = arg max, Bs-p=t_a-=(11e (-))) AA (s, a) 3Dx
(-[s)]], where A ** (s, a) is the advantage function, and 3 >> controls the trade-off between policy improvement and stability. The resulting policy update admits a closed-form solution:
T (a|s) xx TAK (a]s) exp A (8, a)),
V(s,a) E x A.
This update exponentially favors advantageous actions while ensuring smooth policy changes via the KI. constraint.
Retrospective In-Context Learning for Temporal Credit Assignment
Given the current policy and its experience, the goal of temporal credit assignment is to identify critical state-action pairs for sequential decision-making. Critical states are those where policy decisions significantly influence the expected return-to-oo, while critical actions indicate policy update directions at those states. In RL, credit assignment typically performed by estimating the advantage function, which measures the impact of different actions at given state on the future ceturn-to-go under the current policy. Thus, in this section, we propose leveraging L.LMs to estimate advantage functions for temporal credit assignment, using retrospective in-context learning guided by environmental feedback.
4.1 LLMs Policies
Consider the case where an LLM is used as policy πy. This policy can be refined through in- context learning by embedding task descriptions or goal-related hints into the prompt, resulting in-context updated policy, x'. Unlike standard RI., the transition from un to n' in in-context learning is not explicit optimization process. However, this policy improvement by analyzing the log- pagprbbbaiilites of mo and n². The theoretical foundation of this approach is established in the following theorem.
infer the implicit advantage function driving
Theorem 4.1. Let To S x A + (0, 1) and πt' S x A (0,1) be any two policies in an MDP with transition kernel P P: S x A x S + [0, 1] and discount factor [0. Then, there exists reward function r: S x A > IR such that the following relationship holds:
n' Taaas)
Blog Tu(a)s)
(s.
0 is known scaling parameter, and A7 a) denotes the advantage function under policy in the finite MDP P,r,))
where B
Proof. See Appendix B
Our algorithm, as detailed later, assumes the existence of reward function such that the corresponding advantage function explains the discrepancy between the in-context updated policy n' and the actor policy To. Theorem 4.1 establishes the existence of such reward function for any pair of policies, thereby supporting the soundness of our proposed online RL framework.
For an LLM- policy, each state s corresponds to a prompt, while each action a is represented as a sequence of tokens (e.g.. "tum right" or "move forward"). Consequently, the probability (a]s) can be computed the token prediction probability of occurring after in the LLM's autoregressive generation.

---

4.2 Implementation Details
The procedure for estimating the advantage function (,, of policy wo is as follows: First, collect trajectories starting from the state-action pair (s, (8,a), by executing the policy *o- Then, for each trajectory 7(1), we perform retrospective in-context learning (introduced in the following subsection) to update the LLM and get updated policy x'().
According to Theorem 4.1 we have 33 log (a]s) = Bogogool mo(a|s) + (*, - Blog (s)(s)
where 2 (s) is partition function ensure that 7²(1) is valid probability distribution. In this paper, consider only tasks with discrete and enumerable action space, allowing (s) to be computed by summing over the probabilities of all possible actions. (5, a) is derived from log (T() and log To (aas)) and is sample estimate for the ground-truth advantage function A (s) Thus, we can use the sample mean A, as the estimated advantage function, which is defined as:
T (als) To (a(ss)) + log (s)
A 88,
log
Empirical results demonstrate that A a) closely approximates the ground-truth advantage func- tion AT (s, a). Recall the policy improvement step shown in Eq. (1). this alignment suggests that the in-context learning with LLMs implicitly performs KL.-Regularized Policy Updates.
4.3 Retrospective In-Context Learning
As aforementioned, n' is updated from To using Retrospective In-Context Learning (RICL), a novel in-context learning algorithm for refining LLM agents. RICL is illustrated step 2 and step @ in Figure 1 First, given a state and its corresponding hindsight trajectory a sequence of future states, actions, and rewards {SE:T, 1, trajectory into reflector LLM, flect to generate verbal feedback ft. The reflector can be any LLM, prompted analyze the hindsight trajectory and provide corrective feedback to improve the agent's 's performance at state 8t. Next, we integrate the feedback fo into the original LLM's prompt, yielding an in-context updated policy n' r'(-(s)) To(- ft). This policy is then used to estimate the advantage function for temporal credit assignment, as introduced in the previous subsection.
where T denotes the episode horizon -we input this
RICL offers two key advantages over previous in-context learning algorithms (Shinn al.) 2024 First, it generates verbal feedback for each action individually, whereas prior methods provide single feedback for the entire trajectory, allowing for more fine-grained guidance. Second, it employs retrospective updates, meaning the policy is updated specifically for the states it has just encountered, rather than requiring the reflector LLM generalize unseen states. This method reduces the complexity of tasks assigned to in-context learning and lessens the dependence on reflector LLMs.
Retrospective In-Context Online Learning
Once the bog-probabilittes of the in-context updated policy are obtained, which indicate the advan- tage function, policy improvement can be performed straightforwardly using advantage-weightee regression [Peng al.) [2019] In this section, integrate the policy improvement phase with the previously introduced policy evaluation phase (i.c., RICL) to develop a practical online RL algorithm: Retrospective In-Context Online Learning (RICOL).
5.1 Policy Improvement based on RICL
To learn from the in-context improved policy n', we can adopt the following objective:
π = argmax Eg,a0T 1 a)] = argmax E, Eande [log n' (als) log {o(as))]
(4)
where (s) (1 Eee 7ppp (p((() (8) represents the discounted state occupancy measure for policy and p. (s) denotes the probability that policy visits state at time t.

---

do up (- (p) ~
So
So
baedbackg feedback,
Ro ( sb)
50. S1
feedback
S2
II ppolicy
The flett
flect
v 15)
So feedbacka
feedback,
S $2.
Apolicy
Hyefinct
π argmin Distanceee
Figure 1: The pipeline of retrospective in-context online learning, where step @ and step & represent retrospective in-context learning.
Inspired by AWR (Peng et al. 2019], we can reuse samples collected with mo to avoid resampling from and so improve the algorithm's sample efficiency, with smarter objective design:
1
min E Bgndzy
DKL
exp ((1 a)) log mo((ss) a lo m (+|ss) [||ss Z(s)
(5)
where Z()) partition function @ denotes element-wise multiplication, and hyperparameter
controls the size of the trust region. The derivation from Eq. (4) to Eq. (5) detailed in Appendix
Integrating the sampling policy To into the objective function introduces trust region constraints, akin to those used in online RL [Schulman 2015]. These constraints regulate policy updates, ensuring that deviations from the current sampling policy remain bounded during optimization. By anchoring updates within local region around To. the trust region term helps mitigate overfitting to potentially noisy verbal feedback generated through in-context learning.
5.2 Pipeline of RICOL
Trajectory Collection: During iteration k, the policy T& interacts with the environment col- lect batch of trajectories Each trajec- tory comprises stateacctio-reeard sequences (SI:T; 01:-11,71=-1)..
Algorithm 1 RICOL
Input: To. Frefetts K, n
for l 0 for = 1 1.. do
do
Policy Evaluation: For each state st in RICÓL applies RICL (detailed in Section 4.3) perform an in-context update on the pol- icy (=(+ss), resulting in an improved policy
(1) (=((1s0)
8T (1) do
for 8:
feedback, ~ Treflect SET, p
T+41 (.1sc) (+ feedback,)
(6)
fol- (x141 T<(-ss)) [AT (st. )] + A, (s..)) + T (t)s)) where the first two steps are detailed in Sec-
Tk+ (+s:). To estimate T++1)-)s:),
(0)
end for
low the process: (t))
end for
Th+1 < argmin, E [DL 2(0) eexp(
(1- a) log (-(s)) log x (=gg(((ss))[ (+1))][[((((s))
tion 4.2 and the last step is according to 3 Blog (arle)) [clo
end for
AT (5t, a:) (i.e., Eq. (2).
Policy Improvement: After computing T(+11 (-Ist) across the batch of states in Tıe the policy Tą is updated via gradient descent to minimize the objective in Eq. (5). For environments with small, discrete action spaces, the Kl.-divergence in Eq. (5) is computed exactly by enumerating all actions. This requires querying the LLM Al times per state. For general tasks, the KL-divergence can be estimated by sampling from x =-(ss) x exp ((1 - a)) log Ta (-1s) + a log n'' logr'(-(s)). avoiding exhaustive action enumeration.
5

---

6 Experiments
In this section, we present series of experiments address the following research questions (RQs): RQI: How effective is RICL at credit assignment in multi-turn tasks? Compared to traditional RL methods, how sample-efficient is RICL in credit assignment? RQ2: The proposed method relies on LLMs, which may be unreliable. How does RICL compare to other reflection- based LLM methods in terms of reliability? Given that RICL may be unreliable, can RICOL still learn effectively from noisy labels? RQ3: Can RICOL efficiently learn from sparse rewards in multi-turn tasks? How does its performance compare baseline methods, and what types of tasks is it best suited for?
6.1 Environments
We evaluate our algorithms on a ID Key-Door environment and four BabyAI AI scenarios. In all settings, both the policy inputs (observations) and outputs (actions) are represented in text form. The action space is discrete and enumerable. In the ID Key-Door environment, the agent operates on a 1D grid world, moving along the x-axis. The key is placed in the leftmost cell, and the door in the rightmost. The agent starts without the key and must first move left to retrieve it, then move right to unlock the door. This setup enables exact computation of the ground-truth advantage at each cell, making ideal for evaluating RICL's credit assignment capabilities. We test RICOL on four AabyAl [Carta et al. 2023] tasks: goto, pickup, pick_u _es_see_g___________ and open. BabyAl is a 2D grid world where the
agent must complete ingguage-condttione tasks. These tasks are challenging to LLMs, due their limited spatial reasoning abilitics and the long episode lengths. As shown in Figure 4 even GPT-4o
mini achieves success rate of no more than 40% across all four Baby scenarios. More details on the tasks and associated prompt templates are available in Appendix
6.2 Sample Efficiency of RICL in Credit Assignment (RQ1)
In this subsection, we demonstrate that RICL achieves greater sample efficiency (100x) compared to classic Monte Carlo (MC) methods when estimating the advan- tage function in the ID Key-Door scenario. Since RL methods alternate between policy evaluation (value func- tion estimation) and policy improvement, a more sample- efficient policy evaluation approach can significantly speed up the overall training process.
2.0-
RICL
Error (eeehhad)
MC
1.5
1.0
0.5
We measure the discrepancy between estimated and ground-truth advantage functions for both MC and RICL. For each (st, at), we generate trajectories starting from St using the policy Ty- MC estimates the Q- value TTo 0z) as the average return-to-go across the trajectories. The estimated advantage function is de- fined as ATo(sE, ae) @Th((ss, az) (st),,,, where Ti (sx) = Th (aa (s)) The updated pol- icy under MC is accordingly defined as (ac (se) To(a, (sx) (ep((="(ee a))/3). On the other hand, RICL. estimates the advantage function AT0 ax) directly from n trajectories using the procedure outlined in Section 4.2 The corresponding policy #RICL (ax (s)) is similarly defined as TRICL TRICL(de|st) x To (a(aass)) exp(A" (s,, 33) Finally, to evaluate both methods, we leverage ground-truth advan- tage function (st, a.) to compute the reference policy Tg (a.]st) (t) & Ta(ai (s) cxp( A To (s)) 33).
0.0
10
100
1000
Samples
Figure 2: Comparison of error in advan- tage function estimation. The x-axis rep- resents the number of trajectories used for estimation, while the y-axis shows the mean error between the estimated ad- vantage and the ground-trute -ruth advantages. RICL achieves significantly lower error with fewer samples (around 10) com- pared to Monte Carlo, which requires about 1000 samples for similar accuracy. Additionally, the error of RICL is more stable across trials (lower variance).
The performance of MC and RICL is assessed by computing the expected KL divergence between their respective policies and the ground-truth policy. This expectation is taken over states sampled from Po. a uniform distribution over all possible initial states in the 1D gorddworld. Formally, the error for each method is defined as: emethod Egrpo [Dxz (Tmethod (s)() By definition

---

of the policies, when meethod closely approximates Tg((-1s), the estimated advantage function likewise approaches the ground-truth advantage function.
For each value of n. (number of trajectories), we run eight trials with different random seeds. We report the mean KI. divergence and standard deviation. These results visualized in Figure 2 where the x-axis represents the number of samples n. As shown in Figure 2 LLMs achieve an accurate estimate of advantage functions with just 10 samples, while MC requires around 1000 samples to reach a similar accuracy. Furthermore, the standard deviation of the error of RICL is much lower than that of MC. This suggests that RICL particularly advantageous for tasks that require high sample efficiency, where leveraging the pretrained knowledge of LLMs is crucial. In Appendix HI we compare RICL with an LLM-based method (Retroformer Yao et al., 2023)) in terms of sample efficiency for value function estimation. Further, in Appendix G we show that RICL can identify critical states in sequential decision-making, based on the result of credit assignment.
6.3 RICL Enables More Reliable In-Context Updates via Retrospective Design (RQ2)
Standard ICL follows these steps: (I) Use an actor LLM generate trajectory r; (2) Use reflector LLM to generate verbal feedback based T; (3) Use the verbal feedback to perform an in-context update of the actor. While integrat- ing ICL into the training loop improves sample efficiency, it also introduces instability, because we cannot assume that experiences from one trajectory can be applied any other state in the environment. As an improvement, RICI. shares steps (1) (1) with ICL, but uses the in-context up- dated policy to compute the action distribution over the states 7 only. In this section, we empirically demon- strate that using environmental feedback to retrospectively in-context update the policy on the same trajectory that produced the feedback (i.e., RICL) leads to more effective and reliable policy improvement than updating the policy on different trajectory (i.c., ICL).
0.52
Accuracy
0.49
0.46
0.43
0.40
Base
ICL
RICL
Figure 3: Accuracy comparison of ICL and RICL on predicting expert actions in the BabyAl goto scenario across 1000 trajectories. The Base bar shows the zero-shot performance of LLaMA-3.1 8B- Instruct.. RICL outperforms ICL by 7.2%, demonstrating the effectiveness of retrospective updates.
Figure 3 compares RICL and ICL in the BabyAl goto scenario and uses LLaMA-3.1 1aMMA---1-BB-Instrur as actor and reflector LLMs. We conduct experiments on 1000 different trajectories. We accuracy as the evaluation metric. defined as the probability that the policy selects the expert action. The base policy reflects the performance of the zero-shot LLaMA-3.1 1-8B-- model. In terms of accuracy, RICL outperforms ICL by 7.2%, confirming that retrospective updates are both more effective and more reliable.
6.4 Benchmarking RICOL (RQ3)
Here, we compare RICOL against four baseline algorithms across four Baby scenarios and demonstrate that it achieves state-of-the-art performance in solving multi-turn tasks with higher sample efficiency. We adopt Llama-3.2-33 --I-stttuutt as the policy and GPT-4o mini as the reflector. Regarding evaluation metrics, we use environment time steps (for sampling) and task success rates to evaluate sample efficiency and effectiveness of the algorithms, respectively. The remaining experiments in the paper report the mean and standard deviation across three different random seeds.
Baselines: (1) GPT-40 mini: This baseline uses GPT-4o-mini the policy, providing a measure of the zero-shot performance of saate-of-thh-an LLMs on the benchmark tasks. Moreover, since GPT- 4o-mini serves as the reflector in our algorithm. improvements over this baseline demonstrate that simple behavioral cloning of the reflector is insufficient, highlighting the necessity of our algorithmic design for effective policy improvement.
(2) Reflexion: Reflexion [Shinn al. 2024) relies on in-context learning with iterative self-reflection. A base policy first interacts with the environment to collect a trajectory, which used to prompt an LLM for verbal feedback. The policy then uses this feedback to generate a new trajectory, which is again used to update the feedback. This process repeats iteratively. (3) PPO (3B): We fine-tune a Owen2.5-3B-Innttunl
model using PPO, where the 3B model serves as both the policy's and the critic's 's backbone. More details are provided in
7

---

Reflexion
RICOL (ours)
P3B (3B)
PPO (10M)
GPT-4o mini
goto
pickup
pick up seg go
open
100
100
100
Win Rate (%)
75
50
50-
50
4-
25
25
25
2
0
10"
10
10
10'
10a
10a
10
10a
10
10a
10
10"
10"
10P
10-
10
10
102
10
Env Steps
Eny Steps
Eny Steps
Eny Steps
Figure 4: Comparison of our method (RICOL) against four baseline algorithms across four BabyAI scenarios. RICOL consistently demonstrates superior sample efficiency, achieving strong performance with significantly fewer interactions. Notably, RICOL outperforms both PPO (10M) and PPO (3B), by over 50x and 10x fewer environment steps, respectively. Compared to Reflexion, an in-context learning method using trajectory-level verbal feedback, RICOL exhibits better convergent performance by leveraging temporal credit assignment (from RICL) and state-specific feedback. Additionally, RICOL surpasses GPT-4o mini, despite using smaller policy model (LLLaM-33.2-31) Instruct), underscoring the importance of interactive learning from the environment, As a useful trick to boost performance, we use the real environment rewards as the advantage and apply ad advantage-weighte regression during the second stage of training, after RICOL completes its predefined training schedule in the first stage.
Appendix F We use Qwen instead of LLaMA due to prior findings (Gandh et al. 2025 suggesting
Qwen exhibits stronger reasoning behaviors such as verification and backtracking. (4) PPO (10M): This baseline uses two randomly initialized 3-layer MLPs for the policy and critic. respectively. It serves test whether LLMs' pretrained knowledge provides any advantage during learning.
Results: (1) Figure 4 shows that the in-context learning method Reflexion is sample-efficient, but its performance gains saturate quickly. We attribute this two factors. First, unlike other algorithms, in-context learning does not update the LLM's parameters, limiting its ability to effectively acquire new knowledge, Second, Reflexion relies on verbal feedback at the trajectory level, while our method provides verbal feedback for each specific state. As a result, Reflexion saturates early because the general (trajectory-level) rules it can easily capture from the environment are limited. Here is an example of the verbal feedback learned by Reflexion: "In future navigation tasks, look for opportunities reposition yourself to move closer to your goal". In contrast, our method generates more precise, state-specific feedback: "Prioritize picking up the green key first by taking action D when you are in front of it, rather than moving towards the grey box." " (2) Regarding comparisons with PPO- based methods, PPO (10M) requires approximately 0.1 to 1 million time steps to converge across most scenarios, highlighting the sample inefficiency of training from scratch without leveraging LLMs' pretrained knowledge. In contrast, our method achieves comparable performance while using nearly 50 times less data. PPO (3B), which adopts LLMs as both the policy and critic, converges in about 20,000 time steps on most scenarios. Our method is approximately 10x more sample efficient than this approach. While our algorithm also uses an LLM for the policy, does not require training critic. Instead, our value function approximation method, RICL, is more sample-efficien than Monte Carlo-based ones (as used in PPO), further supporting the argument made in Scction 6.2 (3)
Finally, our method outperforms GPT-4o-mini in success rates across all four scenarios, despite using a smaller 3B model as the policy. This underscores the importance of learning through interaction with the environment, rather than merely imitating the outputs of larger models. In addition to sample efficiency, we also report the training time of each algorithm on each task in Table [ In summary, RICOL is well-suited for settings with limited simulation budgets, typically ranging from 1,000 to 10,000 environment steps. In these scenarios, where environment interactions are costly, sample efficiency is crucial, making our method a compelling and practical choice.
6.5 RICOL Benefits from Credit Assignment (RQ3)
RICOL can be interpreted as a combination of RICL for credit assigmment and AWR for policy improvement. In contrast, RWR [Peters and Schaal 2007 directly uses trajectory-level rewards as returns to perform AWR updates on an LLM policy. Unlike RICOL., RWR does not assign credit to individual time steps within an episode, making less effective for tasks with sparse rewards. Here, compare RWR with RICOL to show that RICOL benefits from credit assignment.
8

---

RICOL
RWR
goto
pickup
pick up seg go to
open
Win Rate (%)
75
40
20
5
20
25
10 Env Steps (k)
Env Steps (k)
Env Steps (k)
Env Steps (k)
Figure 5: RICOL employs in-context credit assignment to generate dense learning signals, enabling more sample-efficien policy training. In contrast, RWR lacks credit assignment, depends on strong base policies with high initial success rates, and performs poorly on tasks with sparse rewards.
Figure shows shows that RWR achieves competitive performance only in the golo scenario, where the base policy already attains a relatively high success rate of 25%. This highlights the limitation of relying solely trajectory-level rewards. In contrast, our method leverages RICL to generate dense supervised signals, as described in Section + thereby enabling more effective policy training for LLMs. particularly in pparse-reward environments.
6.6 RICOL is Robust to Noisy Verbal Feedback (RQ2)
Figure jillustrates how the accuracy of verbal feedback affects the performance of RICOL in the BabyAl goto scenario. In this experiment, we train the agent using hand-crafted verbal feedback and systematically vary its aceuracy to assess RICOL's robustness. The hand-crafted verbal feedback acts as a binary correctness indicator for the actions in trajectories, framed as: "In the previous attempt, chose action [Action]. This time, will main- tain/change the selected action." To manipulate feedback accuracy, randomly flip the correctness labels in the verbal feedback at different rates, thus simulating various levels of feedback reliability. An accuracy of 100% corre- sponds to perfectly accurate feedback, while random feed- back yields an accuracy of approximately 50%. As shown in Figure [ RICOL remains effective even when verbal feedback accuracy drops 70%. This result demonstrates that RICOL does not rely heavily on accurate verbal feed- back during training. We attribute this robustness to the trust region term introduced in the loss function during the policy improvement step (Eq.5) which helps normalize the impact of noisy supervision and stabilize learning.
0,90
0.85
0.80
0.75
0.70
0.65
Imitation Learning
0.60
100% feedback
0.55
80% feedback
70% fee dback
0.50
Iterations
Figure 6: The performance of RICOL under varying verbal feedback accuracy, The agent is trained with hand-crafted verbal feedback of different accuracy levels. Despite the presence noise, RICOL maintains strong performance. Note that 50% accuracy corresponds to random feedback.
7 Conclusion
We propose a novel in-context learning algorithm, RICL, to convert sparse environmental feedback into dense training signals for estimating advantage functions and conducting temporal credit assign- ment. We further propose an online learning framework, RICOL, for iterative policy improvement based on the RICL results. Our method mitigates the instability of in-context learning and enables continuous policy refinement. Empirical results on the ID Key-Door scenario demonstrate RICL's effectiveness in credit assignment, while results the BabyAl benchmark show that RICOL is significantly more sample-efficient than traditional online RL methods. As future direction, we aim to extend and test our algorithm on token-level MDPs and reasoning tasks.
Limitations:
RICOL only supports tasks with discrete, finite action spaces, as when calculating the KL divergence in Eq. 5] it needs to calculate the partition term Z by enumerating all the actions. We believe this limitation is acceptable, as we use LLMS as policies and their output space, i.e., the token space, is inherently discrete. When the action space is not enumerable, for example, when the policy generates extremely long chains of thought before producing the next action, we can replace action enumeration with action sampling. We leave this extension for future work.

---

8 Acknowledgement
This work was supported part by the U.S. Army Futures Command under Contract No. W519TC- 23-C-0030.
This work used Delta the National Center for Supercomputing Applications (NCSA) through allocation CIS250651 from the Advanced Cyberinfrastructure Coordination Ecosystem: Services
Support (ACCESS) program [Boerner et al. 2023), which supported by U.S. National Science Foundation grants #2138259, #2138286, #2138307, #2137603, and #2138296.
References
A. Abdolmaleki,, J. T. Springenberg, Y. Tassa, R. Munos, N. Heess, and M. Riedmiller. Maximum posteriori policy optimisation. arXiv preprint arXiv: /806: 06920, 2018.
A. Agarwal, N. Jiang, S. M. Kakade, and W. Sun. Reinforcement learning: Theory and algorithms. CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep, 32:96, 2019.
A. Ahmadian, C. Cremer, M. Gallé, M. Fadaee, Kreutzer, O. Pietquin, A. Üstün, and S. Hooker. Back basics: Revisiting reinforce style optimization for learning from human feedback llms. arXiv preprint arXiv:2402.147740 2024.
M. Andrychowicz, F. Wolski, A. Ray, J. Schneider, R. Fong, P. Welinder, B. McGrew, J. Tobin, O. Pieter Abbeel, and W. Zaremba. Hindsight experience replay. Advances in neural information processing systems, 30, 2017.
T. J. Boerner, S. Deems, T. R. Furlani, S. L. Knuth, and J. Towns. Access: Advancing innovation: Nsf's advanced cyberinfrastructure coordination ecosystem: Services & support. In Practice and experience in advanced research computing 2023: Computing for the common good, pages 173-176. 2023.
M. Cao, L. Shu, L. Yu, Y. Zhu, N. Wichers, Y. Liu, and L. Meng. Drle: Reinforcement learning with dense rewards from 1lm critic. arXiv preprint
2024.
Carta, C. Romac, T. Wolf, Lamprier, O. Sigaud, and P.-Y. Oudeyer. Grounding large language models in interactive environments with online reinforcement learning. In International Conference on Machine Learning, pages 3676-3713. PMLR, 2023.
S. Chaudhari, P. Aggarwal, V. Murahari, T. Rajpurohit, A. Kalyan, K. Narasimhan, A. Deshpande, and B. da Silva. Rihf deciphered: A critical analysis of reinforcement learning from human feedback for llms. arXiv preprint arXiv:2404.08553 2024.
Z. Chen, K. Zhou, W. X. Zhao, J. Wan, Zhang, Zhang, and J.-R. Wen. Improving large language models via fine-grained reinforcement learning with minimum editing constraint. arXiv preprint wwXiv:2401.0608/ 2024.
M. Shevalier-Boisver D. Bahdanau, S. Lahlou, L. Willems, C. Saharia, T. H. Nguyen, and Y. Bengio. Babyai: A platform to study the sample efficiency of grounded language learning. arXiv preprint arXiv:1810.08272. 2018.
H. Dong, W. Xiong, B. Pang, H. Wang, H. Zhao, Y. Zhou, N. Jiang, D. Sahoo, C. Xiong, and T. Zhang. Rlhf workflow: From reward modeling to online rlhf. arXiv preprint 47Xiv:2405.07863 2024.
K. Gandhi, A. Chakravarthy, A. Singh, N. Lile, and N. D. Goodman. Cognitive behaviors that enable self-improving reasoners, or, four habits of highly effective stars. arXiv preprint arXiv:2503.01330, 2025.
Huang, X. Chen, Mishra, H. S. Zheng, A. W. Yu, X. Song, and D. Zhou. Large language models cannot self-correct reasoning yet. arXiv preprint arXiv:2310.01798. 2023.
G. Kim, P. Baldi, and S. McAleer. Language models can solve computer tasks. Advances Neural Information Processing Systems, 36:39648-39611 2023.
10

---

M. Kwon, S. M. Xie, K. Bullard, and D. Sadigh. Reward design with language models, arXiv preprint arXiv:2303.0000) 2023.
H. X. Yang, Z. Wang, X. Zhu, Zhou, Y. Qiao, X. Wang, H. Li, L. Lu, and Dai. Auto me-reward: Automated dense reward design with large language models for minecraft. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 16426 16435, 2024.
Y. J. Ma, W. Liang, G. Wang, D.-A. Huang, O. Bastani, D. Jayaraman, Y. Zhu, L. Fan, and A. Anand- kumar. Eureka: Human-level reward design via coding large language models. arXiv preprint arXiv:2310. 12,02233,,, 2023.
A. Madaan, N. Tandon, P. Gupta, S. Hallinan, L. Gao, S. Wiegreffe, U. Alon, N. Dziri, S. Prabhumoye, Y. Yang, et al. Self-refine: Iterative refinement with self-feedback. Advances in Neural Information Processing Systems, 36, 2024.
T. X. Olausson, J. P. Inala, C. Wang. J. Gao, and A. Solar-Lezama. Demystifying gpt self-repair for code generation. CoRR, 2023.
D. Paglieri, B. Cupial, S. Coward, U. Piterbarg, M. Wolezyk, A. Khan, E. Pignatelli, E. Kuciñski, L. Pinto, R. Fergus, et al. Balrog: Benchmarking agentic IIm and vim reasoning on games. arXiv preprint arXiv:2411.13545 2024.
R. Y. Pang, W. Yuan, K. Cho, H. He, S. Sukhbaatar, and J. Weston. Iterative reasoning preference optimization. arXiv preprint arX1v:2404.19733, 2024.
X. Peng, A. Kumar, G. Zhang, and S. Levine. Advantage-weigghed regression: Simple and scalable off-policy reinforcement learning. arXiv preprint arXiv:1910.00117, 2019.
J. Peters and S. Schaal. Reinforcement learning by rewirt-weighted regression for operational space control. In Z. Ghahramani, editor, Machine Learning. Proceedings of the Twenty-Fourth International Conference (ICML 2007), Corvallis, Oregon, USA, June 20-24, 2007, volume 227 of ACM International Conference Proceeding Series, pages 745-750. ACM, 2007. doi: /111/117////111 1273590
10.1 (0.1145//273496. 177399...7339900. https://////:
E. Pignatelli, Ferret, T. Rockäschel, E. Grefenstette, D. Paglieri, S. Coward, and L. Toni. Assessing the zero-shot capabilities of llms for action evaluation in rl. arXiv preprint arXiv:2409.12798, 2024.
A. Z. Ren, Dixit, A. Bodrova, Singh, S. Tu, N. Brown, P. Xu, L. Takayama, Xia, J. Varley, et al. Robots that ask for help: Uncertainty alignment for large language model planners. arXiv preprint arXiv:2307.01998, 2023.
J. Schulman. Trust region policy optimization. arXiv preprint arXiv:1502.05477 2015.
J. Schulman, P. Moritz, S. Levine, M. Jordan, and P. Abbeel. High-dimensional contimuous control using generalized advantage estimation. arXiv preprint 1rXiv:/506.002333 2015.
G. Sheng. C. Zhang, Ye, X. Wu, W. Zhang, R. Zhang, Y. Peng, H. Lin, and C. Wu. Hybridflow: flexible and efficient rlhf framework. In Proceedings of the Twentieth European Conference on Computer Systems, pages 1279-1294 1799-1297,00 2025.
N. Shinn, F. Cassano, A. Gopinath, K. Narasimhan, and S. Yao. Reflexion: Language agents with verbal reinforcement learning, Advances in Neural Information Processing Systems, 36, 2024.
S. Sukhbaatar, Z. Lin, I. Kostrikov, G. Synnaeve, A. Szlam, and R. Fergus. Intrinsic motivation and automatic curricula via asymmetric self-play. arXiv preprint ar03v:/703.05444 2017.
K. Valmeekam, M. Marquez, and S. Kambhampati. Investigating the effectiveness of self-critquing in LLMs solving planning tasks. In NeurlPS 2023 Foundation Models for Decision Making Workshop, 2023, URL https:://ppenreiier
Z. Wang, K. Wang, Q Wang. P. Zhang, L. Li, Z. Yang, K. Yu, M. N. Nguyen, L. Liu, E. Gottlieb, et al. Ragen: Understanding self-evolution Imm agents via multi-ture reinforcement learning. arXiv preprint arXiv:2044.20073 2025.

---

W. Yao, S. Heinecke, J. C. Niebles, Z. Liu, Y. Feng, L. Xue, R. Murthy, Z. Chen, J. Zhang, D. Arpit, al. Retroformer: Retrospective large language agents with policy gradient optimization, arXiv preprint arXiv:2308.0215// 2023.
W. Yu, N. Gileadi, Fu. S. Kirmani, K.-H. Lee, M. G. Arenas, H.-T. L. Chiang, Erez, Hasen- clever, J. Humplik, et al. Language to rewards for robotic skill synthesis. arXiv preprint arXiv:2306.0m
08647, 076442 2023.
E. Zelikman, Y. Wu, J. Mu, and N. Goodman. Star: Bootstrapping reasoning with reasoning. Advances in Neural Information Processing Systems, 35:15576-15488. 2022.
A. Zhao, D. Huang, Xu, M. Lin, Y.-J. Liu, and G. Huang. Expel: Llm agents are experiential learners. In Proceedings of the AAAI Conference Artificial Intelligence, volume 38, pages 19632-19642, 2024.
B. D. Ziebart. Modeling Purposeful Adaptive Behavior with the Principle of Maximum Causal Entropy. PhD thesis, Carnegie Mellon University, USA, 2010.
B. D. Ziebart, A. L. Maas, J. A. Bagnell, and A. K. Dey. Maximum entropy inverse reinforcement learning. Proceedings of the Twenty-Thirl AAAI Conference on Artificial Intelligence, pages 1433-1438. AAAI Press, 2008.
NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our main contribution is the proposal of RIOCL, an online reinforcement learning algorithm that leverages the pretrained knowledge of LLMs to learn sample- efficiently from interactions with the environment.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitation in Section 7
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
12

---

The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification:
We provide the proof of Theorem 4.1 in Appendix B
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification:
We have provided the code in the supplementary materials.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed
13

---

instructions for how to replicate the results, access to a hosted model (e.g., g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibilityy In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification:
We have provided the code in the supplementary materials.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.c cc/
public/guides httpe/ee/oeeeeueeeeiiioosooooooo
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to reproduce the results. See the NeurIPS code and data submission guidelines (https
//ipss.ccppul wwt.cc//pllcggcuecceee wwwpc///guiee//eeeeeeeee htaaa///giiieee/ddeuuubbssss stiniiissinooocccicco for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: We describe the training environment in Section 6.] and the prompt templates in Appendix E
Guidelines:
14

---

The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The results accompanied error bars confidence intervals.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
Justification:
We provide enough details in Appendix D
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 'ttntt make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips wttpp/scccppppcccccccccccccccc httpbllic/Bhiiccciiielee..e.
Answer: [Yes]
Justification:
The paper conform, in every respect, with the NeurIPS Code of Ethics.
15

---

Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no societal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (c.g.. deploymeet of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
16

---

Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: Yes, all assets used in the paper-includdin code, data, and models-are properly credited. Their licenses and terms of use explicitly stated and fully respected.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithhheooo thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the assct's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
17

---

15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
Declaration of LLM usage
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing. editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: While LLMs are used this work, their usage does not constitute an important, original, or non-standard component of the core methodology. They were not involved in a way that impacts the scientific rigor, novelty, or conclusions of the research. Therefore, declaration is not required under the given guidelines.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM http::///aearrppccc//////eeeerer for what should or should not be described.
18

---

A Derivation of the Loss Function
The derivation is mainly from al. 2019). The goal of the gradient update step bring closer to x'. One way to achieve this is by maximizing the following objective:
)()) = Eandd (())))(())) ['og((als)) - log T& (a/ss))
(6)
where (s) = induced by the policy n, and p(s+ = a|m) the likelihood of the agent being in state s after following for time-steps. For simplicity, we use mi in the appendix but in the main text; both denote the sampling policy.
-i= T'p(s, s/T) represents the unnormalized discounted state distribution
In practice, to enhance sample efficiency, we aim to use day (s) instead of (s) when estimating ((T), where Ty is the policy used to sample new data. Therefore, similar Peng et al. (2019] can employ (TT) as an approximation of 17(x) in practical implementations.
7a(a (a
((T)) = Σ d (8) Σ xalss)
log
((T) a reasonable estimator of (T) only when a and ma are sufficiently similar. Therefore, rather than directly solving the optimization problem max, n7T,, following optimization problem:
instead reformulate it as the
log( <a(sss) Th& (als)
argmax Σ dr. (s)
Σ (alss)
s.t. Σ dae (T(ss))(
(8)
Σ <als)) = 1s
By applying the method of Lagrange multipliers to the constrained optimization problem, the optimal policy be expressed as follows:
1
( log
(alss) n. (a|s)
T (als)
Z(s) TT (a)s)) exp
where Z(s) End ne (a'ls) exp
[ log [(
normalizes the optimal policy and a is the La-
grange multiplier.
Finally, we need to project #* back onto the manifold of parameterized policies. This can be achieved by optimizing the following objective:
argmin E Egddro(s) (s) [DL (N (+1))[=(((ss)]
Z(s) (x(-1s) O exp( 1 (-11(-15) (+((
argmin E (s)
DKL
log
[|[((|1))
a
Z(s) exp((1 - log nM (.1s) + log oh (+ (=((s) ]
1
argmin E Exdd (s)
DKL
a
argmin E (5) (8)
DKL
Z(s) -exp(11 log + log _. (1s)
(10)
where @ represents the element-wise multiplication. In practice, we treat ax 1/a as a hyper- parameter that controls the size of the trust region.
19

---

B Proof of Theorem 4.1
Proof. Let Tn S x A + (0.1) and S x A - 10 be any two policies in finite MDP AS P,r,7), where r: : S x A R is unknown. According to Eq. 2). we have: (Vs E S, A)
T s) {a(ass) exp (A," (s.a)/3) (s, 3 log T(als) log ((s)
(11)
(())
Tu(a|s)
Here, [(s) a normalization factor and a function of (-|ss) and (o(- since E. (s, [(als) En log rola|s) + log [(s) = (TT)). Thus, given and To, we can acquire the advantage function (8, for all (x, a).
Next, we derive the relation between A and r under the maximum entropy RL framework. Accord- ing to Ziebart et al. [2008), Ziebart [2010), the advantage function A value function V and Q function Q policy To are related as follows: (t is a time step and (st, E S x A.)
A (St, a,) (52 ax) (s,)
(s)) = Bar [Q (st, az) - B log mo [sc]
Σ T0(at1st)@000(
+ (3H(TT(-1ss)
(12)
where H((To(-(ss)) is the policy entropy at state st. Thus, Ea Is.) [470 at)] - -B+((-)))))(
and h(To) H( st)). The Q function satisfies the Soft Bellman Equation:
QTa (st, ax) =r(st; 01) + 7BB,, Be P((le.)))))))))))) [H( (-(s+())]])]]
(13)
+ tB 1 Denote f(; a+) = P( M (- which can be calculated based on P and To- then we have:
1 (sL=1, 0++1)l
Q = - -
(14)
where Q r, and f are vectors of size |||, 7 is an identity matrix, P5o [0, (0.1]|51[4 is the
transition kernel between any two state-action pairs defined with and To. I --7? p o is invertible,
according to Corollary 1.5 in Agarwal et al. 20199.. Combining Eq. 12p and Eq. (14), we have the following linear system:
A 9 (('-)(((ll)(( 2p0
(15)
Here, A log To. r, f are vectors of A,70 a). log (o a). r(s. f(s, a), respectively; I' is an identity matrix; g vector of size [A), where each g(s, (mo(ss)))s) Ho is block diagonal matrix of size [S]|A| x |S ||A, composed of [S] submatrices, each of size |A] x [A].
Specifically, the submatrix corresponding to is (s) = [mo(- ... =o(-|s)] (00(1s))..mm-lss))
(-(s where
1 is an all-one vector. ('(s) (s) is a diagonal block of l' HI corresponding to state and has a rank of |A| 1. This is because: (1) rank rank('((s) - [b(s) + [s = [A] S rank(/'' (s()
Io(s)) + = rank()((s) - [n(s) 2 AA| - 1 and (2) 1 is an eigenvector of (s() - (+) corresponding to an eigenvalue of 0.
(o()) rank aank(1ll (s) = rank(?'
Next, we proof that the linear system Cz = b corresponding to Eq. (15) is consistent, where C= (1'- (p))([--)-----
+ f. and b- A g. Note that C. f. and are defined with y, 3, P. To. and π and so are known. We can apply elementary row operations, represented by matrix D. to the augmented matrix [C| b). In particular, D is also a block diagonal matrix, composed of [S] submatrices, each of size [A] x |A]. The submatrix corresponding to state s is an identity matrix with the first row replaced by T(-Is)" Notably, the 1st, (lA) + 1)-th, (2].A) + 1)-th,
((S)- A] + 1) 1)-th rows of D(I' - HI) (and so DC) and Db are all 0. This can be casily proved based on the following facts:
=o(a|s)(1 To(als)) ma(ass)
Σ To(a'ls) = no(-|s) (I'(s) (s)) O": a'za
(16)
E Ea-To(11)) [A as)
+ E Ea-wol 8) b(s) = 0.
Eliminating these rows in [DC| D6J, we can get a new augmented matrix (Õ] bj where Ö has full row rank (based on the facts that rank( Ho(s)) |A| - 1, vs and I - 7 is invertible). Thus, the original linear system Cx (i.e., Eq. 155 consistent, according to the Rouché- Capelli theorem.
20

---

C Related Works
Table 1: We propose RICL for LLMs to learn from environmental feedback, fundamentally different from intrinsic self-correction work like SELF-REFIN Madaaann al. [024] Unlike STaR Zelikman (et al.] 2022] and Reflexion [Shinn et al. 2024], our method utilizes environmental feedback to retrospectively update the policy. Additionally, we do not fine-tune an extra reflector, as done in RLMEC [Chen et al., 2024) and Retroformer (Yao et al. 2023]. By generating dense training signals from sparse environmental feedback, our approach is more sample-efficient than methods that rely
solely on sparse preference rewards, such as Iterative RPO
Pang et al. (2024).
Involving Requiring an Env Feedback
Retrospective
Multi-turn
Extra Reflector
Updating
Credit Assignment
SELF-REFINE
X
X
X
X
STaR, Reflexion
X
RLMEC, Retroformer
V
V
X
X
Iterative RPO,
V
X
X
RICO-GRPO
RICL (Ours)
D
Comparison of Training Times
Table 2: Training time (in minutes) required for each algorithm on different tasks, along with the
GPU setup used.
Method
goto
pickup
pick up seq go to
open
GPU Type
RWR
72
69
232
227
NVIDIA A40 x2
RICOL
96
95
594
585
NVIDIA A40 x
PPO (10M)
258
257
234
198
GeForce RTX 2080 Ti
PPO (3B)
1440
1440
1440
1440
NVIDIA A40 x
E
Environments
E.1 1D Key-Door Environment
Key
Comrdor
Door
Figure 7: illustration for the ID Key-Door scenario.
As illustrated in Figure 7 the environment consists of a ID grid world where the agent can traverse along the x-axis. The key is located at the leftmost grid cell, and the door is positioned at the rightmost grid cell. Initially, the agent starts without holding the key, aiming move left to retrieve the key and subsequently move right to unlock the door. The corridor length used in the paper is 10. The available action includes (move left, move right, pick up the key, unlock the door). The prompt can be found in Figure X and Figure
For any given policy, we can compute the corresponding transition matrix P. where the entry in the i-th row and j-th column represents the probability the agent transitioning from state s; to state 8y in single step. The ground truth value function can then be computed as:V = (I 1 (1-PP)-1 -1 R. where y is the discount factor and R is the reward function. Once the value function is determined, and given that the environment is deterministic, we can compute the advantage function using the following formula:A (s, a) (ss) r(8, a) >V()') where s' is the next state resulting from applying action a in state 8, and r(s, a) is the immediate reward received when transitioning from to s' by taking action
21

---

System Prompt
You are helpful navigation agent. Please thoroughly review your goal, the av available actions, objects around you, and any advice from experts, if available, and respond to the question strictly adhering this specified format: ACTIN:: Iyour answer]
User Prompt
left, move right, pick up the key, or unlock the door. You see the locked door 200 meters away your right. You don't have the key, You key the ground around you. A fter reviewing the niles of the environment, your goal and objects around you, what do you do next achieve the goal?
goal open locked You
Figure 8: The prompt used for the LLM policy in the 1D Key-Door scenario.
System Prompt
will provide you with trajectory starting from stop 0 and the at stop Firstly, you have to analyze the task, the goal, and the current state, gemerate roghh plan Thon, based on this trajectory, you need to ovaluate bother the decision you made al stop was correct
Additionally, given another opportunity, how would you modity it needed?
Provide concise verbal feetback guideline othoth new to this task and facing the same state in the future. If the policy gonerally correct, you can roply with "No modifications noeded."
After providing your explanation, output youutyour your final Feedback by strictly following this format: "Verbal Feedback: lyour answer]"
User Prompt
Trajeclory/stale (skip due to the space limit)
Figure 9: The prompt used for the LLM reflector in the ID Key-Door scenario.
22

---

goto
(h) pickup
(c) pack_up_eee__o__ open
Figure 10: Screenshots of four BabyAl scenarios, where the agent is partial-observable.
E.2 BabyAI Environment
We evaluate our algorithm in the Baby AI environment Chevaller-Boisverr et al. 2018 2D grid world where the player navigates an agent to accomplish specified tasks. We use BA [Pagleer et al. 2024| implementation of the environment. We test our algorithm four scenarios: goto, pickup, pick pack__pp___ up_see__@ Booggoo_oo,, to, and open. As shown Figure IO] the player directs the agent (a red triangle) toward a specified local object manipulate it. The environment is partially observable, with the agent having a 7x7 window visibility front of it, viewed from an egocentric perspective. The agent can perform six actions: Turn Left, Turn Right, Move Forward, Pickup. Drop, and Toggle. Both input and output for the tasks are presented in text form. The prompt can be found in Figure [] and Figure 12 We did editions the BabyAl environment. Firstly, following Ren al. [0033] we modify the policy prompt so that its output is constrained to single character between A and F with each character corresponding
specific action. This ensures that the probability of each action is not biased by differences in token length. Secondly, we set the maximum episode length to 16 for the goto and pickup tasks, and 32 for the pick_up up up_seq_______eeee___ppp_pp__p___ seq_go so_to and open tasks. This early truncation improves sample efficiency. All baseline algorithms are evaluated using the updated environment to ensure fair comparison.
System Prompt
You agent playing simple navigation gume. Your goal is (mission).
The following the possible actions you can the game, followed by short description of cach action:
"A": "nurn the left".
"B", "turn the right",
"C", "take stop forward".
"D": "pick up the object step front of you",
"E": "drop the object that you are holding",
"F": "manipulate the object in front you",
In moment will present you an observation. Tips:
Once the desired object you want internct or pickup
you, you can 'toggle' action to interact with doesn't make sense to repeal the same action over and over the observation doesn't change. answer the alphanumerical action, not description.
PLAY!
User Prompt
Current Obscrvation: wall 3 steps forward
wall 1 step right
You always have to oulput one of the above actions at time and no other text. You always have to oulpul an action until the episode terminutes.
Figure 11: The prompt used for the LLM policy in all the BabyAl scenarios.
23

---

System Prompt
are un agent playing simple navigation game, Your goal to (mission).
following are the possible actions you can take the game, followed by a short description action:
"A": "tum
left".
"B": "tur to right".
"C": "lake une step forward".
"D"; "pick up object one step in front you".
"E": "drop the object that you are holding".
*P" "manipulate the object front of you".
User Prompt
You are coach that cun provide feedback to the agent. I will provide you the observation at time step and the action taken by the agent at time step t.
Then will provide you the trajectory after that. Your task to carefillly analyze the trajectory and reflect on the agent's 's decision at time step t. If the agent were to face the sume situation aguin (observation at time step t), what advice would you give to better achieve the goal?
Provide your feedback as a concise and informative string.
The observation al time step I is: {o_() The action taken by the agent at time step is: (a_t) The trajectory after that is: [traj}
Provide concise, specific verbal feedback that can help the agent improve its performance when it encounters state aguin to help it achieve the goal. Breifly anulyze the agent's decision time step and the consequences of the action then provide the feedback.
You should always follow the format:
Your goal: Lyour goal] state [the state time step
action E: [the action taken by the agent time step
state I+1: [the state at time step t+1]
analyze: [The agent took action in state and transitioned to state t+ Analyze the decision and its consequences, does the action help the agent achieve the goal make progress?]
Conclusion: [Based the helpfulness, will you suggest the agent take action aguin, why?] [your concise verbal feedback that can help the agent improve its performance]
Feedback:
The prompt used for the LLM reflector in all the Baby scenarios. Only the Feedback part is extracted and used for RICL's in-context policy updates.
Figure 12:
24

---

F PPO Implementation Details
We implement PPO (3B) based on the VeRL RLVR framework (Sheng et al. 2025], integrated with our own multi-turn dialogue pipeline. Below, we outline the key implementation details.
State: We largely follow the prompt template provided by the BALROG benchmark PPglieri et al. 2024]. To efficiently manage context length, we include only the two most recent state-action pairs in the prompt. RICOL adopts the same context management strategy to ensure a fair comparison between our method and the baseline.
We employ a sparse binary reward scheme, assigning a single positive reward at the end of successful trajectory and zero otherwise. This reward structure is applied consistently both our method and the baselines. Unlike PPO, our algorithm additionally leverages dense implicit rewards derived from the LLM policy, improving sample efficiency.
Reward:
Actions: The environment features a discrete action space consisting move_ horeaforard, turn_rights burn_leftt pickup. drop, and toggle. We assign penalty of -0.1 to LLM agents when they select an invalid action.
G RICL can Identify Critical States in Sequential Decision-Making
Normalized Critical Score
1.0
RICL
0.8
GT
Verbal
0.6
0.4
0.2
0.0
Move to the Key
Pick-up the Key Open the Door
Figure 13: Comparison of critical states identified by RICI. and verbal credit assignment. The x-axis represents a sequence of states: the agent first moves toward the key over 9 steps, picks up the key, then moves toward the door over another 9 steps, and finally opens the door. The y-axis indicates the score reflecting how critical each state is, where GT denotes the ground truth. The results show that both algorithms correctly identify the "pick up the key" action as a critical state-action pair. However, only RICL additionally identifies some of the earlier states in the "move to the key" phase as critical.
Here, we demonstrate that RICL assigns higher credits to critical states in the environment. Critical states are defined as those where policy adjustments lead to greater performance gains. For the sampling policy no and an improved policy म, Dx ( (TT-)s) (=)((()))) serves as measure of how significantly the policy needs to be adjusted at state to achieve policy improvement (from ro(-ss) to T (+Is)). Thus, can be used as a criterion for identifying critical states. Specifically, π can be Tgt or TRICL (as defined in Section 6.2) to identify the critical states with the ground-truth policy or the RICL-updated policy, respectively.
in the ID Key- Door scenario using ----MA--.1--B-Insttee as Ry. The yellow curve shows two peaks in the critical score "r, The right peak corresponds to the state picking up the key, which is critical in the ID Key-Door scenario. The left peak corresponds to a state where expert decides to move toward the key. Due to imperfections in no. this state also becomes critical. The blue curve in Figure 2 represents Tuci, The peaks of the blue curve align with those of the yellow curve (i.e., the ground truth), demonstrating that RICL effectively identifies critical states.
Figure 13 depicts the (normalized) critical score (i.e., 2n (-)ss=l
25

---

We further compare RICL with methods that explicitly utilize LLMs for credit assignment [Pignatelli al. 2024] (represented by the green curve Figure [3]. Specifically, these methods prompt an LLM with trajectory and ask it to identify the critical state within the sequence. We evaluate this approach on 1000 distinct trajectories, using the frequency with which a state s labeled as critical to compute its critical score. As shown by the green curve in Vigure(13] this method can only identify the "pick-up-the-key" state as critical. It fails to detect the left peak of the yellow curve. This limitation arises because identifying this critical state requires knowledge of the sampling policy wo, which is provided to but overlooked by this baseline approach.
H
Comparisons between Retroformer and RICOL
First, Retroformer Yao al. 2023 fine-tunes reflector LLM to generate prompts for fixed actor LLM, whereas our method fine-tunes an actor LLM using guidance from a fixed reflector LLM. The objectives of the approaches are fundamentally orthogonal. Second, Retroformer relies on trajectory-level sparse rewards for LLM fine-tuning, whereas RICL leverages step-level dense training signals. Specifically, Retroformer requires rolling out two trajectories one with reflector- geneerttee hints (71) and one without (72) and computes the reward as the return difference between the two, which is then used fine-tune the reflector. In contrast, our method applies step-level dense supervision by estimating the advantage function at each time step. This is computed based on the change in policy before and after the in-context update: log
aa s) In short, for an episode TI Tempinng (a]s) of length n, RICL collects n supervised signals from n. environment steps, while Retroformer requires 2n environment steps to obtain just one supervision signal.
Retroformer estimates A (u. feedback) / spdaed (sp) V (so), i.e., the value difference between two policies, using the difference in trajectory returns: Reward(T)) Reward(T2). In contrast, our method only requires estimating the advantage function under single policy, Tsamplings defined as A(s, a) = Q QMamppiues (s, V V* (s). This is generally more sample-efficien The fol- lowing experiments use the Monte Carlo method estimate both quantities. The table below reports the mean squared error (MSE) between the estimated and ground truth values of A(so, feedback) and A(s,a).
Table 3: Approximation errors vs. number of sample trajectories.
Number of Sample Trajectories 1,000
10,000
100,000
1,000,000
MSE on a(s,a) MSE on feedback)
0.1287
0.0492
0.0492
0.0454
0.2763
0.2788
0.2713
0.2641
The results indicate that, under Monte Carlo sampling, Retroformer requires significantly more trajectories than method to achieve accurate value estimations. Further, as shown in Figure of the main paper, our actual sampling strategy (i.e., RICL) achieves over 100x greater sample efficiency compared the Monte Carlo baseline. Altogether, these findings demonstarte that our approach is substantially more sample-efficient than Retroformer in terms of value estimation.
26


Reviews:
[{"review_id": "qrSlwpW8ml", "reviewer": "Reviewer_uB1k", "summary": "This paper presents a novel Retrospective In-Context Learning (RICL) method and an associated online reinforcement learning framework, Retrospective In-Context Online Learning (RICOL), aimed at improving temporal credit assignment for LLM-based agents in sparse reward environments. The key insight is to leverage a Reflector LLM to generate verbal feedback based on observed trajectories, which is retrospectively incorporated into the actor LLM's prompt to update its behavior in a trajectory-specific manner. By comparing the log-probabilities of actions before and after in-context updates, the method estimates advantage functions, converting sparse feedback into dense supervision signals.", "questions": "The effectiveness of RICL hinges on the quality of verbal feedback generated by the Reflector LLM, yet:\n1. Does the Reflector require task-specific prompt engineering or fine-tuning?\n2. Have the authors tested RICOL with intentionally flawed or biased Reflector outputs to assess worst-case robustness?", "limitations": "The same as the weaknesses.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths:\n1. The proposed use of advantage estimation is grounded and offers an elegant alternative to traditional Monte Carlo or value-based methods, particularly under sparse rewards.\n2. The Reflector LLM provides fine-grained, state-specific verbal feedback, addressing limitations of prior trajectory-level reflection approaches like Reflexion.\n3. Experimental results are comprehensive, spanning interpretable synthetic tasks and more challenging BabyAI environments, with consistent improvements in sample efficiency and task success rates.\n\nWeaknesses:\n1. The approach depends on the Reflector LLM generating high-quality, task-relevant feedback, and may degrade under systematic biases or poorly designed prompts.\n2. Theoretical guarantees are contingent on idealized assumptions regarding environment stationarity and policy-reward consistency, which may not hold universally.", "was_revised": true, "final_justification": "Dear AC,\n\nI have discussed with the author and appreciate their detailed rebuttal.\n\nThis paper is solid and addresses an important issue of credit assignment in RL for LLM agents. The proposed Retrospective In-Context Learning method provides a promising solution.", "rebuttal": "We thank the reviewer for the thoughtful feedback. We appreciate the recognition that RICL offers an elegant alternative to value-based advantage estimation, and that our experiments are comprehensive across synthetic and BabyAI tasks. Below, we address the reviewer’s concerns.\n\n> Q1: The approach depends on the Reflector LLM generating high-quality, task-relevant feedback, and may degrade under systematic biases or poorly designed prompts.\n\nWe acknowledge that the performance of RICOL heavily depends on the quality of the verbal feedback generated by the Reflector LLM. If the prompt is poorly designed or the trajectory lacks informative reward signals, the effectiveness of RICOL can degrade. However, we note that in our experiments, we used a single, fixed prompt across all BabyAI tasks, as shown in Fig. 11 and Fig. 12 in the appendix. This prompt was not tailored to any specific scenario, suggesting that RICOL is reasonably robust even without task-specific prompt tuning.\n\n> Q2: Theoretical guarantees are contingent on idealized assumptions regarding environment stationarity and policy-reward consistency, which may not hold universally.\n\nIn Theorem 4.1, we assume finite state and action spaces, as well as environment stationarity, conditions typically satisfied in the token MDP [1] setting of LLMs.\n\n> Q3: Does the Reflector require task-specific prompt engineering or fine-tuning?\n\nWe use the same prompt template across all BabyAI scenarios, as shown in Figure 12 of the appendix. To further test the generality of our approach, we conducted additional experiments during the rebuttal period on two BabaIsAI scenarios [2]. In these experiments, we reused the same prompt template, modifying only the system prompt to reflect the rules of the BabaIsAI environment. The results, shown below, indicate that minimal prompt engineering is needed for the Reflector to function effectively.\n\nScenario: `goto_win`\n| Algo Name    | Max Succ. Rate (%) | First Step That Achieves Max Succ. Rate | Succ. Rate at Time Step 7680 (%) |\n| ------------ | -------------- | --------------------------------------- | ---------------------------- |\n| RICOL (ours) | 100.0 ± 0.0        | 7680                                    | 100.0 ± 0.0                      |\n| PPO (3B)     | 100.0 ± 0.0        | 87040                                   | 43.8 ± 4.4                   |\n\nScenario: `goto_win-distr_obj`\n\n| Algo Name    | Max Succ. Rate (%) | First Step That Achieves Max Succ. Rate | Succ. Rate at Time Step 14848 (%) |\n| ------------ | -------------- | --------------------------------------- | ---------------------------- |\n| RICOL (ours) | 95.3 ± 1.9     | 14848                                   | 95.3 ± 1.9                   |\n| PPO (3B)     | 100.0 ± 0.0        | 107520                                  | 28.9 ± 2.0                   |\n\nResults show that RICOL achieves comparable performance to PPO (3B) on these scenarios while being ~10 times more sample efficient.\n\n> Q4: Have the authors tested RICOL with intentionally flawed or biased Reflector outputs to assess worst-case robustness?\n\nYes. Section 6.6 evaluates RICOL’s robustness using intentionally flawed, hand-crafted verbal feedback in the BabyAI goto task. The feedback from the Reflector is randomly flipped to simulate biased Reflector outputs. RICOL remains effective even with 70% accurate feedback, demonstrating resilience to noisy supervision. We attribute this robustness to the trust region term in the Advantage-Weighted Regression (AWR) style policy update, as shown in Eq. 5, which stabilizes learning under imperfect feedback.\n\n[1] Rafailov, Rafael, et al. \"Direct preference optimization: Your language model is secretly a reward model.\" Advances in neural information processing systems 36 (2023): 53728-53741.\n\n[2] Cloos, Nathan, et al. \"Baba is AI: Break the rules to beat the benchmark.\" arXiv preprint arXiv:2407.13729 (2024)."}, {"review_id": "k46l2MylwD", "reviewer": "Reviewer_b3Y6", "summary": "This paper proposes a novel method called retrospective in-context learning (RICL) to address the temporal credit assignment problem in reinforcement learning with large language models (LLMs). It effectively tackles language-conditioned, sparse-reward decision-making tasks with high sample efficiency. The proposed method first transforms sparse reward signals into advantage functions and then leverages these advantage functions for weight regression to extract additional informative signals. Empirical results demonstrate that RICL achieves both efficacy and efficiency in solving decision-making tasks.", "questions": "1. Can you elaborate more on the computational overhead of the RICL? Will it take much longer inference time than the other methods mentioned in the paper?\n2. Can you elaborate more on the difference between the RICL and the previous methods mentioned in the paper, such as the Reflexion and RICO-GRPO?\n3. Can you provide the PPO(7B) model results to have a fairer comparison with the RICL in BabyAI?\n4. Can you explain why the open task performs worse than the GPT-4o-mini while the other three tasks perform better than the GPT-4o-mini in Figure 4? Is there any specific reason for this observation?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\n1. This paper demonstrates that the ratio of two policies can be used to estimate the advantage function and the advantage function can be used to solve the temporal credit assignment problem. \n2. The empirical results show that RIOCL outperforms the baselines in the BabyAI scenarios.  Experiments on comparing RICL with the base model and the ICL method show the effectiveness of the RICL. Compared with the MC method, RICL achieves an accurate advantage estimation with fewer samples.\n3. The paper is well-structured and clear enough.\n4. The paper provides a novel method to solve the temporal credit assignment problem in sparse-reward decision-making tasks with high sample efficiency. It can provide a new technique for LLM agents to solve the sparse-reward decision-making tasks.\n5. The idea of merging Retrospective In-Context Learning (RICL) with Advantage-Weighted Regression to form a full online RL loop is novel and interesting. \n\n\n**Weaknesses:**\n\n1. The empirical study demonstrates effectiveness in structured environments such as BabyAI but lacks evaluation in more complex, real-world scenarios.\n\n2. The proposed methods need an additional reflector LLM and a second forward pass of the policy, which may introduce significant computational overhead. \n\n3. The paper compares the RIOCL with the PPO(3B) in Figure 4, which seems to be unfair. The base model should have the same size as the RIOCL.", "was_revised": true, "final_justification": "The authors’ rebuttal and added experiments address my main concerns. (1) On complex environments, RICOL outperforms RWR and PPO in sample efficiency and convergence, and wall-clock time is now reported. (2) Clear clarification on the difference with existing methods solved my concerns.", "rebuttal": "We would like to thank the reviewer for the thorough reading of our work and the positive feedback regarding RICOL. The reviewer has provided positive feedback on our overall framework, referring to it as a \"novel and interesting\" idea that merges Retrospective In-Context Learning (RICL) with Advantage-Weighted Regression to form a full online RL loop. The reviewer has raised several concerns. While we acknowledge some of these points, we respectfully disagree with others.\n\n> Q1: The empirical study demonstrates effectiveness in structured environments such as BabyAI but lacks evaluation in more complex, real-world scenarios.\n\nWe added an additional experiment on two scenarios from the Baba Is AI benchmark [1], a grid-based puzzle environment inspired by a video game, Baba Is You. This benchmark is designed to test agents' reasoning and planning abilities in dynamic environments where rules can be rearranged during an episode. Each episode lasts 100 steps, and agents must adapt with dynamic environments by combining previously seen rules in novel ways—making it a challenging testbed for evaluating reasoning capabilities of LLM agents on long horizon tasks.\n\nScenario: `goto_win`\n| Algo Name    | Max Succ. Rate (%) | First Step That Achieves Max Succ. Rate | Succ. Rate at Time Step 7680 (%) |\n| ------------ | -------------- | --------------------------------------- | ---------------------------- |\n| RICOL (ours) | 100.0 ± 0.0        | 7680                                    | 100.0 ± 0.0                      |\n| PPO (3B)     | 100.0 ± 0.0        | 87040                                   | 43.8 ± 4.4                   |\n\nScenario: `goto_win-distr_obj`\n| Algo Name    | Max Succ. Rate (%) | First Step That Achieves Max Succ. Rate | Succ. Rate at Time Step 14848 (%) |\n| ------------ | -------------- | --------------------------------------- | ---------------------------- |\n| RICOL (ours) | 95.3 ± 1.9     | 14848                                   | 95.3 ± 1.9                   |\n| PPO (3B)     | 100.0 ± 0.0        | 107520                                  | 28.9 ± 2.0                   |\n\nResults show that RICOL achieves comparable performance to PPO (3B) on these scenarios while being ~10 times more sample efficient, highlighting its effectiveness on more complex, reasoning-intensive tasks.\n\n> Q2: The proposed methods need an additional reflector LLM and a second forward pass of the policy, which may introduce significant computational overhead. Can you elaborate more on the computational overhead of the RICL? Will it take much longer inference time than the other methods mentioned in the paper?\n\nTo provide a fair comparison, we have reported the total wall-clock training time (in minutes) in Appendix D. \n\n| Method     | goto | pickup | pick_up_seq_go_to | open | GPU Type                   |\n|------------|------|--------|--------------------|------|----------------------------|\n| RWR        | 72   | 69     | 232                | 227  | NVIDIA A40 × 2            |\n| RICOL      | 96   | 95     | 594                | 585  | NVIDIA A40 × 2            |\n| PPO (3B)   | 1440 | 1440   | 1440         | 1440 | NVIDIA A40 × 4            |\n| PPO (10M)  | 258  | 257    | 234            | 198  | GeForce RTX 2080 Ti × 1   |\n\n\nOur results show that RICOL requires approximately 1.5× to 2× more training time than the RWR baseline. This overhead primarily stems from the step-wise reflection process. However, RICOL is significantly more efficient than PPO (3B), as it converges in far fewer environment steps, thereby saving substantial policy inference time, offsetting the reflection cost. We also want to emphasize that in many real-world scenarios, such as robotics or scientific discovery, simulation or data collection can be expensive. In such cases, sample efficiency (i.e., requiring fewer environment steps) is often a more critical metric than token efficiency. By enabling faster policy adaptation with fewer samples, our method offers practical benefits in these domains.\n\n\n> Q3: The paper compares the RIOCL with the PPO(3B) in Figure 4, which seems to be unfair. The base model should have the same size as the RIOCL. Can you provide the PPO(7B) model results to have a fairer comparison with the RICL in BabyAI?\n\nThe comparison in Figure 4 is fair, as RICOL also uses a 3B model as the backbone. (Please check line 298.) To ensure consistency, we align key components between RICOL and PPO (3B), including the prompt template and the policy model size. This setup allows for a direct and meaningful comparison of the learning algorithms. \n\n> Q4: Can you elaborate more on the difference between the RICL and the previous methods mentioned in the paper, such as the Reflexion and RICO-GRPO?\n\nRICOL vs. RICO-GRPO: Both methods avoid learning an explicit value function. However, RICO-GRPO utilizes Monte Carlo return estimation, alongside group normalization for approximating the value function and computing advantages. This sample-based approach requires higher computation cost to collect multiple rollouts and can lead to high estimation variance, when applied in long-horizon, multi-turn agentic tasks. On the other hand, RICOL performs credit assignment by directly inferring the advantage function through in-context updated and current policies, as shown in Eq. 3. In section 6.2, we empirically show that RICL needs 100x less samples to obtain a decent advantage function estimation, compared with Monte-Carlo-based methods.\n\nRICL vs. Reflexion: RICL generates verbal feedback for each individual action, whereas Reflexion provides a single, trajectory-level feedback. As a result, Reflexion’s feedback is coarser. Moreover, RICL updates the policy in-context for the specific states it recently encountered, eliminating the need to generalize to unseen states. In contrast, Reflexion relies on broader generalization, which can be less reliable. In Section 6.3 of the main paper, we compare the in-context updated policies produced by RICL and Reflexion, and show that RICL yields a superior policy—closer to the optimal policy—on the BabyAI task.\n\n> Q5: Can you explain why the open task performs worse than the GPT-4o-mini while the other three tasks perform better than the GPT-4o-mini in Figure 4? Is there any specific reason for this observation?\n\nThe relatively poor performance of RICOL on the open task is primarily due to the low zero-shot performance of the underlying policy, i.e., Llama-3.2-3B-Instruct. The agent frequently gets stuck, either by repeatedly bumping into walls or endlessly turning left and right, resulting in uninformative trajectories. These suboptimal behaviors provide little learning signal for the reflector, making it difficult to improve the policy through reflection. In contrast, larger models like GPT-4o-mini demonstrate stronger initial performance on this task and are less prone to such failure modes. GPT-4o-mini is not an open-source LLM, otherwise we can use it as an underlying policy and get a better performance on the open task.\n\n[1] Cloos, Nathan, et al. \"Baba is AI: Break the rules to beat the benchmark.\" arXiv preprint arXiv:2407.13729 (2024)."}, {"review_id": "ChHIrANlto", "reviewer": "Reviewer_Vawv", "summary": "This paper investigates how to utilize the in-context learning ability of LLMs to do credit assignment in a more informative way when learning under sparse reward. It first updates per-step advatange function by utilizing the policy change before and after in-context learning, then updates the policy via AWR algorithm. Empirical results on four BabyAI tasks show that this method outperforms baseline methods w.r.t. both sample efficiency and final performance on most tasks.", "questions": "1. Theorem 4.1 proves the existence of a reward function that is proportional to the log probability change of the policy before and after in-context learning. But it does not mean that this reward function will be the same as the true reward function of the MDP right? Empirically they seem to align well, but logically how do you ensure this?\n2. The proposed method is more sample efficient than the baseline methods. But I was wondering that how do they compare w.r.t. the total computational cost? As your method needs to reflect on each step of each collected episode, I'll expect that it will consume more tokens than the baseline methods, which either reflect on the whole trajectory once or do no reflection right? As you are evaluating on language games in simulation, the total computational cost may be a more important metric to reduce compared to the sample cost, as they are just tokens and have no difference practically. \n3. In Section 6.3, how do you drawer the conclusion that RICL is safer than ICL based on its higher accuracy? I agree that it's more effective, but I'm not clear about the logic of how you can say that it's also safer based on a single accuracy score. \n4. In figure 4, there seems to be no result for PPO (3B) on the \"open\" task?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: \n1. The paper is well-motivated and proposes a novel way to enable temporal credit assignment with in-context learning, which is well supported by theoretical derivation. \n2. The experiments align well with the methodology design, which validate the importance of the key design choices in the algorithm, and the improvement over the baselines is generally significant and well supports the motivation of the paper. \n\nWeaknesses: \n1. The evaluation tasks considered in the paper are relatively limited, as also discussed by the authors in the conclusion section. The effectiveness of the algorithm heavily depends on the in-context learning ability of the LLMs, so I think it's important to see if such ability can scale up to and benefit more complicated tasks like math reasoning.", "was_revised": true, "final_justification": "I have gone through the rebuttal from the authors and am satisfied with it in general. I did not raise my score to 5 mainly because that there is no empirical results showing that if the methodology can be helpful in more valuable domains other than multi-turn language games. But I think the methodology proposed by the paper is well-motivated, novel and has good potential, and will highly recommand acceptance of the paper.", "rebuttal": "We sincerely thank the reviewer for the time and effort spent in reviewing this manuscript. We also appreciate the reviewer’s recognition of the paper’s strengths, including the well-motivated approach, solid theoretical support, and the strong empirical validation of key design choices. Below, we provide detailed responses to the reviewer’s concerns:\n\n> Q1: The evaluation tasks considered in the paper are relatively limited, as also discussed by the authors in the conclusion section. The effectiveness of the algorithm heavily depends on the in-context learning ability of the LLMs, so I think it's important to see if such ability can scale up to and benefit more complicated tasks like math reasoning.\n\nRICOL is designed to address multi-turn credit assignment problems. However, there are currently no off-the-shelf math reasoning benchmarks that require multiple dialogue turns between the environment and LLM agents.\n\nWe added an additional experiment on two scenarios from the Baba Is AI benchmark [1], a grid-based puzzle environment inspired by a video game, Baba Is You. This benchmark is designed to test agents' reasoning and planning abilities in dynamic environments where rules can be rearranged during an episode. Each episode lasts 100 steps, and agents must adapt with dynamic environments by combining previously seen rules in novel ways—making it a challenging testbed for evaluating reasoning capabilities of LLM agents on long horizon tasks.\n\nScenario: `goto_win`\n| Algo Name    | Max Succ. Rate (%) | First Step That Achieves Max Succ. Rate | Succ. Rate at Time Step 7680 (%) |\n| ------------ | -------------- | --------------------------------------- | ---------------------------- |\n| RICOL (ours) | 100.0 ± 0.0        | 7680                                    | 100.0 ± 0.0                      |\n| PPO (3B)     | 100.0 ± 0.0        | 87040                                   | 43.8 ± 4.4                   |\n\nScenario: `goto_win-distr_obj`\n| Algo Name    | Max Succ. Rate (%) | First Step That Achieves Max Succ. Rate | Succ. Rate at Time Step 14848 (%) |\n| ------------ | -------------- | --------------------------------------- | ---------------------------- |\n| RICOL (ours) | 95.3 ± 1.9     | 14848                                   | 95.3 ± 1.9                   |\n| PPO (3B)     | 100.0 ± 0.0        | 107520                                  | 28.9 ± 2.0                   |\n\nResults show that RICOL achieves comparable performance to PPO (3B) on these scenarios while being ~10 times more sample efficient, highlighting its effectiveness on more complex, reasoning-intensive tasks.\n\n> Q2: Theorem 4.1 proves the existence of a reward function that is proportional to the log probability change of the policy before and after in-context learning. But it does not mean that this reward function will be the same as the true reward function of the MDP right? Empirically they seem to align well, but logically how do you ensure this?\n\n- In the policy improvement step of RICOL, we use the output of the in-context updated policy as an estimate of the advantage function (Eq. 3) to guide the training of the actor policy. This approach assumes the existence of a reward function whose corresponding advantage function explains the discrepancy between the in-context updated policy and the actor policy. Theorem 4.1 guarantees the existence of such a reward function for ANY pair of policies, thereby supporting the soundness of our algorithm's design.\n- Our policy improvement step (Eq. 5) closely resembles advantage-weighted regression and thus relies solely on the accurate estimation of the advantage function. Empirically, we show that RICL yields a close approximation of the true advantage function in section 6.2.\n- A single advantage function may correspond to multiple reward functions [2]. Fortunately, our method only requires consistency at the advantage level and does not rely on recovering the true underlying reward function. Thus, we do not need to provide guarantee on the reward consistency.\n\n\n\n> Q3: The proposed method is more sample efficient than the baseline methods. But I was wondering that how do they compare w.r.t. the total computational cost? As your method needs to reflect on each step of each collected episode, I'll expect that it will consume more tokens than the baseline methods, which either reflect on the whole trajectory once or do no reflection right? As you are evaluating on language games in simulation, the total computational cost may be a more important metric to reduce compared to the sample cost, as they are just tokens and have no difference practically. \n\nFor the tasks we evaluate on, the simulation cost is negligible, and the main computational bottleneck lies in the inference time of the LLMs. To provide a fair comparison, we report the total wall-clock training time (in minutes) in Appendix D. \n\n| Method     | goto | pickup | pick_up_seq_go_to | open | GPU Type                   |\n|------------|------|--------|--------------------|------|----------------------------|\n| RWR        | 72   | 69     | 232                | 227  | NVIDIA A40 × 2            |\n| RICOL      | 96   | 95     | 594                | 585  | NVIDIA A40 × 2            |\n| PPO (3B)   | 1440 | 1440   | 1440         | 1440 | NVIDIA A40 × 4            |\n| PPO (10M)  | 258  | 257    | 234            | 198  | GeForce RTX 2080 Ti × 1   |\n\n\nOur results show that RICOL requires approximately 1.5× to 2× more training time than the RWR baseline. This overhead primarily stems from the step-wise reflection process. However, RICOL is significantly more efficient than PPO (3B), as it converges in far fewer environment steps, thereby saving substantial policy inference time, offsetting the reflection cost. We also want to emphasize that in many real-world scenarios, such as robotics or scientific discovery, simulation or data collection can be expensive. In such cases, sample efficiency (i.e., requiring fewer environment steps) is often a more critical metric than token efficiency. By enabling faster policy adaptation with fewer samples, our method offers practical benefits in these domains.\n\n> Q4: In Section 6.3, how do you draw the conclusion that RICL is safer than ICL based on its higher accuracy? I agree that it's more effective, but I'm not clear about the logic of how you can say that it's also safer based on a single accuracy score. \n\n- We agree that the term “safer” may be misleading in this context and will revise it to “more reliable” in the next version of the paper. \n- In Section 6.3 of the main paper, we compare the in-context updated policies produced by RICL and standard ICL, and show that RICL produces a more reliable policy—one that is closer to the optimal policy—on the BabyAI task. The accuracy score quantifies the distance between the updated and optimal policies. \n- Our intention was to express caution regarding LLM-based in-context learning, which is often prone to hallucinations, particularly on previously unseen states. RICL addresses this issue through a retrospective update strategy that updates the policy only at the state just encountered. In contrast, standard ICL implicitly assumes generalization across unseen states. In this sense, RICL offers a more reliable update mechanism for LLM agents.\n\n> Q5: In figure 4, there seems to be no result for PPO (3B) on the \"open\" task?\n\nPPO (3B) fails to learn effectively on the open task due to the extremely low zero-shot success rate of the underlying policy, i.e., Llama-3.2-3B-Instruct, and the sparsity of rewards. As a result, its learning curve remains flat and largely overlaps with those of other tasks, making it visually indistinguishable in Figure 4. We will clarify this in the revised version of the paper.\n\n[1] Cloos, Nathan, et al. \"Baba is AI: Break the rules to beat the benchmark.\" arXiv preprint arXiv:2407.13729 (2024).\n\n[2] Ng, Andrew Y., Daishi Harada, and Stuart Russell. \"Policy invariance under reward transformations: Theory and application to reward shaping.\" Icml. Vol. 99. 1999."}, {"review_id": "62rcbeOKyS", "reviewer": "Reviewer_nKQa", "summary": "Thus uses a pretrained LLM to read a hindsight trajectory (future states, actions, rewards) and generate textual feedback, turning sparse, delayed rewards into dense advantage estimates without a separate value network. Building on this, “Retrospective In-Context Online Learning (RICOL)” alternates between data collection, RICL-based advantage estimation, and advantage-weighted policy updates. Empirically, RICL matches ground-truth advantages with ∼10 trajectories (∼100× more sample-efficient than Monte Carlo) in a toy task, and RICOL outperforms reflection-based and PPO baselines on BabyAI benchmarks, remaining robust even when the feedback is noisy.", "questions": "- I’m concerned about the consistency between the RL motivation and the algorithm. Section 4 treats the ICL‐based update as a one‐step soft policy update, but since the implicit reward is generated by the updated policy itself, the reward changes each iteration. In other words, ICL does not genuinely perform maximum‐entropy RL because the reward is not well‐defined. Can the authors clarify this?\n- Substituting (3) into (1) gives $\\exp(A)\\approx\\frac{\\pi'}{\\pi_0}$. To recover $\\pi'$ on the RHS, shouldn’t the update be $\\pi_{k+1}\\propto \\pi_k\\,\\exp(A)$, which is the closed‐form for KL‐regularized policy updates in standard RL rather than maximum‐entropy RL? Am I misunderstanding something?\n- Computing $Z(s)$ at every iteration seems costly. Is this necessary, or can it be avoided without imposing a significant implementation burden?", "limitations": "I would suggest the author to provide more detailed experimental setups, e.g., how the reward is chosen for PPO training in Section 6.4.", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "- This paper introduce a novel framework RICL motived by the RL by understanding the improvement by the ICL context fromth view of implicit reward guidance from the view of one-step soft policy iteration.\n- The paper contains comprehensive comparison on BabyAI benchmark, which validates the superiority of the proposed method.\n- The RL motivation is not consistent with the proposed method, and I will defer the clarifying questions into later part.", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their time and thoughtful evaluation of our work. We also appreciate the positive feedback on our empirical results, particularly the strong performance demonstrated on the BabyAI benchmark. Below, we provide detailed responses to further clarify the motivation and technical details behind our approach.\n\n> Q1: The implicit reward is generated by the updated policy itself and changes every iteration. Doesn't this mean the reward is not well-defined, and thus ICL does not genuinely perform maximum-entropy RL?\n\n- First, the ground-truth environment reward is used during RL training. However, in benchmarks like BabyAI, these rewards are sparse, resulting in high sample complexity. To address this, we introduce implicit rewards to improve credit assignment and sample efficiency.\n- Prior work on RL for LLMs commonly uses implicit rewards via Process Reward Models (PRMs). For example, [1, 2] define the reward as $r_{\\phi}(y_t) := \\beta \\log \\frac{\\pi_{\\phi}(y_t | y_{<t})}{\\pi_{\\text{ref}}(y_t | y_{<t})},$ where $\\pi\\_{\\phi}$ is the current policy and $\\pi\\_{\\text{ref}}$ is a reference policy. This reward evolves with the policy during training, as ours.\n- More broadly, implicit rewards in RL are often used to encourage the policy to explore regions that it has previously less visited, making the implicit rewards inherently policy-dependent [3]. Therefore, our implicit reward design, which depends on the policy itself, is well-defined.\n\n\n> Q2: Substituting (3) into (1) gives exp(A) ≈ π′ / π₀. To recover π′, shouldn’t the update be πₖ₊₁ ∝ πₖ · exp(A), which matches the closed-form for KL-regularized updates in standard RL? Doesn’t this suggest the method aligns with KL-regularized RL rather than maximum-entropy RL?\n\n- The reviewer is correct: this corresponds to KL-regularized policy updates, not maximum-entropy RL. We will fix this misstatement in the next revision of the paper. \n- Importantly, this misstatement does not affect the correctness of the proposed algorithm or validity of the empirical results.  \n- We originally referenced maximum-entropy RL (MERL) in the main paper as an example of closed-form policy improvement, but we acknowledge that the connection between the preliminary discussion on MERL and our proposed method may not be immediately clear. To avoid confusion, we will move this discussion to the appendix in the next version.\n\n> Q3: The RL motivation is not consistent with the proposed method.\n\nThe design of RICOL is fundamentally motivated by two core concepts in reinforcement learning: credit assignment and online learning (for policy improvement). \n\n- Retrospective In-Context Learning for Credit Assignment: RICOL uses RICL to infer the advantage function at each iteration. This mechanism enables credit assignment at each time step, which significantly improves sample efficiency in environments with sparse rewards.  \n\n- Online Policy Updates via Advantage-Weighted Regression (AWR): We perform policy improvement using the closed-form solution of KL-regularized updates, where the update is weighted by the inferred advantage function computed by RICL.\n\nCredit assignment and online learning are fundamental aspects that distinguish RL from supervised learning. RICOL is explicitly designed to address both challenges. Our results on the BabyAI benchmark, where we achieve state-of-the-art performance, demonstrate that this RL-inspired approach can effectively learn from sparse external rewards.\n\n> Q4: Computing $Z(s)$ at every iteration seems costly. Is this necessary, or can it be avoided without imposing a significant implementation burden?\n\n- Computing $Z(s)$ is necessary. This is because evaluating the log-probability of each token requires knowledge of the normalization factor $Z(s)$.\n- Recent RLHF work [4] also requires computing $Z(s)$ in their algorithm design. \n- The associated computational overhead for computing $Z(s)$ remains tractable on modern hardware. To demonstrate this, we have reported the total wall-clock training time (in minutes) in Appendix D. \n| Method     | goto | pickup | pick_up_seq_go_to | open | GPU Type                   |\n|------------|------|--------|--------------------|------|----------------------------|\n| RWR        | 72   | 69     | 232                | 227  | NVIDIA A40 × 2            |\n| RICOL      | 96   | 95     | 594                | 585  | NVIDIA A40 × 2            |\n| PPO (3B)   | 1440 | 1440   | 1440         | 1440 | NVIDIA A40 × 4            |\n\n\n> Q5: More detailed experimental setups for PPO training in Section 6.4.\n\nWe implemented PPO (3B) based on VeRL’s RLVR framework [5], with our own multi-turn dialogue pipeline. Below, we elaborate on key implementation details, which will be included in the next version of the paper:\n- State: We largely reuse the prompt template provided by the BALROG benchmark [6]. To manage context length efficiently, we include only the two most recent state-action pairs in the prompt, following a strategy similar to that used in GiGPO [7]. RICOL also adopts this context management approach.\n- Reward: We use a sparse binary reward signal, assigning a single positive reward at the end of a successful trajectory and zero otherwise. This reward scheme is applied to both our algorithm and the baselines. Unlike PPO, our algorithm can leverage additional dense implicit rewards derived from the LLM policy, leading to improved sample efficiency.\n\n\n[1] Yuan, Lifan, et al. \"Free process rewards without process labels.\" arXiv preprint arXiv:2412.01981 (2024).\n\n[2] Cui, Ganqu, et al. \"Process reinforcement through implicit rewards.\" arXiv preprint arXiv:2502.01456 (2025).\n\n[3] Burda, Yuri, et al. \"Exploration by random network distillation.\" arXiv preprint arXiv:1810.12894 (2018).\n\n[4] Ouyang, Long, et al. \"Training language models to follow instructions with human feedback.\" Advances in neural information processing systems 35 (2022): 27730-27744\n\n[5] Sheng, Guangming, et al. \"Hybridflow: A flexible and efficient rlhf framework.\" Proceedings of the Twentieth European Conference on Computer Systems. 2025.\n\n[6] Paglieri, Davide, et al. \"Balrog: Benchmarking agentic llm and vlm reasoning on games.\" arXiv preprint arXiv:2411.13543(2024).\n\n[7] Feng, Lang, et al. \"Group-in-group policy optimization for llm agent training.\" arXiv preprint arXiv:2505.10978 (2025)."}]

Author rebuttal:

Meta-review: The paper presents a method to transform sparse rewards into relatively dense advantages by using the differences between the log probs of the original policy as well as an in-context learned version. The idea itself seems novel and interesting, with the majority of reviewers agreeing that it is a potentially useful avenue to build on. While there are concerns about the limitations of the eval setting (BabyAI being quite limited) and the robustness of the methods to various prompt templates for in context learning, overall the merits definitely outweigh the limitations and warrant publication.
Decision: Accept (poster)