We thank the reviewer for their feedback and positive review.

Q1: In Algorithm 1, the pseudocode said that there is an input $B$ …

We thank the reviewer for catching this typo. $B$ in the pseudocode has the same purpose as $C$, in the sense that we collect $C$ trajectories in parallel for each of the $T$ tasks (selected by the algorithm). The collection of the $C$ trajectories is parallelized across multiple GPUs. We will edit our paper to reflect this more clearly.

One can in-practice also parallelize the data collection across multiple tasks (beyond trajectories for a single task as we do) with more computational resources. In this case, a batched variant of UCB [1, 6] can be used to update the arm parameters, which we leave for future work.

Q2: In Section3.3, the SFT objective and RPO objective…

We apologize for the confusion. In section 3.3, we define loss functions over any dataset $D$, and do not differentiate between the dataset used for SFT vs RPO stages. We will update the paper to clarify our notation.

However, we also want to provide some clarifications here: for the SFT phase, we collect all successful trajectories for each training task $\tau$. During the RPO stage, for each training task $\tau$, we pick the best trajectory and one of worse-scoring trajectories randomly to form exactly one preference pair. We sample 20 trajectories per task, a large number of which can be successful and included in the SFT phase, but we construct at most 1 preference pair per task. The reason we only form one preference pair per task is because we observed that using more than one per task can cause unintentional unalignment [2, 3], and lead to performance degradation.

Q1: In Section 4.1 Finetuning on regular multiturn data does not help…

Fine-tuning on the full WildChat-1M dataset takes close to 10 days with our computational resources and we could not run that. Moreover, certain trajectories in WildChat have very long context length (> 100,000) and we do not have the resources to train on such long trajectories. Also note that we only ~20K trajectories for Paprika, showing that targeted synthetic trajectory generation is much more sample efficient for the tasks we care about in this work.

Q2: …but there is only one test case in your Bandit best arm selection…

Apologies for the confusion. Even though we have only one test case (e.g., picking colors), we test our models on 100 iterations of the test case, each time randomly sampling the bandit arm probabilities. For each specific bandit arm probabilities, we run 4 iterations of the game, and report the average pass@4 success rate to be 100%. We would edit the paper to make this point clearer.

To follow the reviewer’s suggestion, we generate 20 more bandit tasks (so, 20 problem description + different arm names) using gpt-4o-mini and test Paprika on them, with pass@4 success rate reducing slightly to 98%, still outperforming the regular instruct model (See this Figure, first row, first column)

Weeknesses: Scalability Concerns…

Sampling trajectory is indeed the main time bottleneck. However, we believe this is not too different from other RL tasks. Sampling is the only way we can get experience from the model, and it is still considerably cheaper than collecting human demonstrations. Recent works have found similar approaches to be very effective for other domains like math or coding [4, 5]. Collecting expert data and doing domain specific pre-training or mid-training can improve sample efficiency during the RL phase [7]. Another scalability concern is designing particular tasks for training, and a potential solution is to train another LLM to generate these tasks and then use our curriculum algorithm to select which ones to train on at every step.

Additional Experiments

We have also run additional experiments as per the other reviewers’ suggestions:

1. Paprika with Gemma-3-12B-IT: Our experiments show that Paprika works with Gemma-3-12B-IT as the base model. We also see the Paprika fine-tuned model being comparable or better than GPT-4o-mini in 7/10 task groups. See full results here.

2. More tests for generalization: We extend Figure 4 by running leave-one-out experiments on 5 more task groups, and Paprika (LOO) improves over the instruct model in 9/10 task groups, showing strong generalization: Figure

References

[1] Multi-Armed Bandit Problem and Batch UCB Rule

[2] Unintentional Unalignment: Likelihood Displacement in Direct Preference Optimization

[3] Preference Fine-Tuning of LLMs Should Leverage Suboptimal, On-Policy Data

[4] DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning

[5] OpenAI o1 System Card

[6] Perchet, Vianney, et al. "Batched bandit problems." (2016): 660-681

[7] Cognitive behaviors that enable self-improving reasoners, or, four habits of highly effective stars

We thank the reviewer for the support and thoughtful review. We want to address their feebacks below.

There is not really an ablation (on the different parts of the method)...

We have conducted additional experiments on different parts of Paprika, we list them below:

1. Ablation on training data generation: Since our training data is generated using high temperature (1.5) and min-p sampling with parameter 0.3, we have run an ablation to show the importance of both. On twenty questions, we see that either using a lower temperature or lower min-p sampling parameter leads to lower coverage on the training set, see this Figure for varying Min-p at a fixed temperature of 1.5, and this Figure for varying temperature at a fixed Min-p parameter of 0.3. The training data also affects downstream performance on held-out tasks, see this Figure.

2. Ablation on fine-tuning stages: We ran an ablation on the two different parts of our fine-tuning: namely the SFT and the RPO stage, please see this Figure.

If the reviewer has any other ablation in mind, we are happy to add it to the paper.

For example, is there a way to measure how ‘correct’...

We thank the reviewer for this great question. In general, we found that it is hard to intuitively understand the curriculum or argue whether it’s “correct”. However, we note the following:

1. Performance of the final fine-tuned model: This is the final metric we care about. We have run our curriculum algorithm for 3 seeds and 3 rounds (with 250 tasks sampled at each round) and have an updated version of Figure 4 here, it shows that the model trained on tasks selected by our curriculum outperforms that trained on uniformly selected tasks by 1.4% and 3.3% at average and pass@4 success rate respectively, demonstrating its efficacy in selecting training tasks.
2. Distribution of selected tasks: This is the other metric that is easy to understand. First, see that our defined metric for learning potential (with Llama-3.1-8B-Instruct as the policy) has an intuitive distribution over the gpt-4o-mini defined easy, medium and hard categories — easy tasks have a higher learning potential compared to medium and hard ones. | Category | Average Learning Potential Metric | |-|-| |Easy|0.22 | |Medium| 0.16| |Hard| 0.09|

Next, notice the distribution of easy, medium and hard tasks within 20 questions: we have 477 easy, 727 medium and 296 hard questions. Uniform sampling respects this distribution, and samples more medium tasks as opposed to easy tasks. However, our curriculum algorithm follows the learning potential metric, and samples more easy, then medium and finally the least number of hard tasks in a sampled batch. In a batch of 250 questions, we observe the following distribution:

This shows that our curriculum has an intuitively reasonable behavior. If the reviewer has any other questions/thoughts, we would be happy to address them.

This is noted by the authors and above but the main weakness…

We agree with the reviewer’s comment. To extend Paprika, one would ideally use another LLM to keep generating diverse tasks that require strategic exploration, and use the curriculum algorithm to adoptively choose which tasks to train on. We believe that this is an exciting future direction.

It could be helpful to have a short discussion on the limits of generalizability of the tasks.

We thank the reviewer for this suggestion. We would edit the paper to discuss this limitation more clearly. We will emphasize the suite of tasks is diverse but it remains to be seen whether the resulting model will generalize to more temporally extended and real-world tasks.

How were the particular tasks chosen and which tasks were rejected?

Some of the task groups we work with have been studied before, such as bandits [1, 2], 20 questions [3], guess my city [3] and wordle [3]. We expand upon these prior works and generate more training and test examples by prompting gpt-4o-mini with techniques from GenQA [4]. For the other tasks, we looked for tasks similar to the ones before, and GPT-4o-mini suggested battleship, minesweeper and mastermind. We came up with the cellular automata task as a toy example for iterative coding tasks with an interpreter. Finally, customer service and murder mystery are the open-ended tasks we could think of that have partial observability and fits nicely with other tasks. We wanted as many tasks as possible, so we did not reject any tasks.

References

[1] Can large language models explore in-context?

[2] EVOLvE: Evaluating and Optimizing LLMs For Exploration

[3] LMRL Gym: Benchmarks for Multi-Turn Reinforcement Learning with Language Models

[4] GenQA: Generating Millions of Instructions from a Handful of Prompts

We thank the reviewer for their constructive feedback, and hope to address their concerns below:

One thing probably need to analyze more is…

We note that all our evaluations are conducted on held-out tasks within each group. These tasks require strategic exploration, as they are partially observable (POMDPs) and require agents to interact with the environment to gather necessary information before solving them. For instance, in Mastermind, memorizing training trajectories isn't enough --- agents must learn to make informed guesses based on prior observations. Therefore, success on held-out tasks reflects genuine improvement, not noise. Since there is no direct mapping $x \rightarrow y$ without environment interactions, higher success rates (Figure 2) and fewer turns taken (Figure 6) indicate the model is learning to explore effectively and solve tasks more strategically.

PAPRIKA can teach LLMs generalizable strategies…

In our work, we use 10 different task groups (for example, 20 questions, mastermind etc.). Each task group consists of different tasks (for example, guessing ‘Apple’ and ‘Mango’ in 20 questions). Each task group also employs 2 distinct training and test subsets. For all evaluations, we use the test split, and in that sense, these tasks are unseen.

Moreover, for the LOO experiments, we test on completely unseen task groups. In this way, Paprika itself tests for generalization within the same task group, and Paprika (LOO) tests for generalization to tasks that are from a different domain.

Of course, the tasks have to share some “similarity” for there to be any transfer at all but we don’t think such abstract similarity makes the tasks the same domain.

In these environments, are them mostly about the action…

This is an excellent question. The action and observation spaces of our task groups are often very different from one another. For example, in mastermind, the agent needs to guess a 4 digit code, whereas in 20 questions it needs to ask a yes/no question about the secret topic. We discussed this in Appendix A, here we include a summary.

There is no obvious way to measure the difficulty of a task beyond reporting the model’s performance on each of them before fine-tuning, see Figures 2 and 5 (although this would be a great research question). Similarly, it is hard to say definitively whether one task is semantically similar to another.

I noticed Fig 3 only shows 5 domains…

We have performed LOO experiments in all 10 domains. Paprika (LOO) outperforms the instruct model in 9/10 domains, showing remarkable generalization.

1. This Figure shows the performance of Paprika (LOO) with pass@4 success rate (with additional changes made to Bandits according to reviewer WvQu’s suggestion)

2. This Figure shows the average success rate.

The metric used in the paper is mostly "best-of-4", why we need to report this best of n performance?

We used best-of-4 to account for stochasticity in environment dynamics. However, we agree that one-shot performance is also important. We have collected the following:

1. Average success rate

2. Pass@k for k = 1, 2, 3, 4, at temperature 0.7

The whole paper is only experimenting on the same model…

This is a good point. We have evaluated two different base models with comparable parameter count and see that they perform worse compared to Llama-3.1-8B-Instruct: Figure.

Additionally, we have run Paprika fine-tuning on the recent Gemma-3-12B-IT, which is larger with 12B parameters. Paprika generally improves performance, and the improvement is often larger compared to that on Llama-3.1-8B-Instruct. Additionally, Paprika fine-tuned Gemma-3-12B-IT reaches comparable or better performance to GPT-4o-mini on 7 out of 10 task groups. Below are the most notable results (pass@4 success rate, temp 0.7, min-p 0.3):

Full results: Average, Pass@4

More detailed analysis on the interaction trajectories...

We show comparison between Llama-3.1-8B-Instruct and Paprika on 3 examples:

1. 20 questions, with the secret topic being ‘prime numbers’: Figure

2. 20 questions, with the secret topic being ‘Orca’: Figure

3. Wordle, with the secret word being ‘toast’: Figure

Paprika performs better information gathering and higher quality actions compared to the instruct model. We will add these and more example trajectories in the next revision of the paper.

This would be relevant as well...

Thank you for the reference! We will cite and discuss this.

We thank the reviewer for their thoughtful review and suggestions. They will greatly improve our paper!

But I suggest the authors to derive...

Indeed, mastermind is the hardest task, as demonstrated by the untrained model only achieving ~4% pass@4 success rate on it, the lowest among all 10 task groups (Figure 2).

It is conceptually unclear if the learning potential and LOO generalization should be related, since generalization depends on how transferable the decision making ability from training task groups is to the test task group, rather than the learning potential of the training or test task groups (which is only important for choosing which tasks to train on next). Even a highly learnable test task may not see much generalization if the training tasks do not teach any strategies that transfer to it. We are happy to incorporate any analysis if the reviewer has any suggestions.

In Section 2, the authors stated "for most tasks...

This is a good point and we thank the reviewer for the references which we will discuss in the final version of the paper. What we meant is that we don’t always know how to generate near optimal solutions. In fact, the methods the reviewer mentions are also ways to overcome the fact that we do not know how to solve most tasks like we know how to solve bandits.

We believe what sets paprika apart is that existing works focus on training to solve specific domains like web navigation whereas we are interested in whether the agents can generalize to a wide range of tasks. The motivation is that training for specific domains will not scale to all possible tasks in the world. What we actually want is an agent that is capable of general decision making so it can solve new tasks efficiently.

As the reviewer pointed out, these two perspectives are complementary. These methods could be used as subroutines in Paprika to help gather good experience, and Paprika could make task-specific training more sample efficient because the models are more capable of general decision making.

The term "Curious"...

We thank the reviewer for their suggestion. We would update the paper in the next iteration to clarify the terminology clearly in our introduction.

We want to also briefly discuss it here: the concept of curiosity has been used in many different machine learning contexts. A popular notion is intrinsic motivation, where the agent is driven by an exploration bonus that is not necessarily related to the task to be achieved [1, 2]. Many works build on this notion to handle problems with sparse reward or no reward at all [3, 4]. The curiosity in this work differs from intrinsic motivation in that we focus on gathering only the information required to solve a given task rather than all the knowable information. This is closer in spirit to the original exploration-exploitation trade-off in reinforcement learning [5]. The goal is to explore to the extent that the problem can be solved but not over-explore at the cost of efficiency, by training on a wide range of problems. This can be thought of as a form of amortized exploration.

In the Line 6 of Algorithm 1, $\tau$ tasks and $C$ samples...

Sampling trajectory can be expensive but not avoidable. It is the same as gathering experience in other RL algorithms. Since the sampling is expensive, we have only tried one configuration, the largest one our hardware can support. Namely, we sample task $\tau$ uniformly at random from task group $k^*$, and fix $C = 20$.

We fully agree that different configurations can affect the estimated difficulty of a task, since the empirical estimate of the learning potential (Appendix E) might become worse if $C$ is significantly reduced, and therefore affect the final agent’s performance.

In Section 3.2, the authors mentioned that the top-p sampling...

To clarify, we use min-p sampling instead of top-p, since it is known to work better at higher sampling temperatures [6]. We have run an ablation to show the importance of min-p sampling. On twenty questions, we see that either using a lower temperature or lower min-p parameter leads to lower coverage on the training set, as measured by pass@20 success rate, please see this Figure for varying Min-p at a fixed temperature of 1.5, and this Figure for varying temperature at a fixed Min-p parameter of 0.3.

The training data generated by different min-p parameters and temperatures also affects downstream performance of the fine-tuned model on held-out tasks, see this Figure.

References

[1] Curious model-building control systems.

[2] Godel machines: Fully self-referential optimal universal self-improvers.

[3] Curiosity-driven exploration by self-supervised prediction.

[4] Exploration by random network distillation.

[5] Reinforcement learning: An introduction

[6] Turning up the heat: Min-p sampling for creative and coherent llm outputs