acceptodds
Under review as a conference paper at ICLR 2027

Beyond First Success: Expanding Achievement Rewards in Open-World Survival Games

Abstract

Long-horizon tasks often require repeatedly performing intermediate behaviors that have already succeeded. Rewards for first success alone do not directly reflect subsequent progress through repetition, while continually rewarding repeated behavior can favor easily triggered events. We introduce Structured Ordinal Reward (SOR), which expands achievement feedback along two dimensions: event identity and recurrence level. Using first-success labels and structured reference trajectories, SOR learns event rules, identifies a finite set of observationally supported recurrence levels, and allocates a total auxiliary reward budget according to event recurrence support. The constructed reward program remains fixed during downstream training. Given reference data and approximately one million downstream training steps, SOR improves PPO's cumulative training achievement score in Crafter by 19.5% and its independent native evaluation score in Craftax-full by 37.2%. We further conduct payment-timing controls and budget-permutation experiments within SOR to study how feedback along recurrence and reward allocation across events affect learning. Experiments combining SOR with Achievement Distillation demonstrate compatibility with achievement representation learning, supporting its use as an auxiliary reward module for existing learners. Code is available at https://anonymous.4open.science/r/structured-ordinal-reward-DE30/.

Primary area:
reinforcement learning
Keywords:
Reinforcement Learning, Reward Shaping, Automatic Reward Construction, Achievement-Based Rewards, Long-Horizon Tasks, Open-Ended Environments

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_ogCPOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The authors introduce a new way to automatically generate a reward program, SOR, with the goal of helping the policy repeat actions that should be repeated multiple times, like gathering wood. This method builds the reward program based on the achievements and actions the previous agent took. They test their procedure on Crafter and Craftax, showing an improvement over the PPO baseline.

Critical strengths

How to design a better reward function when the reward for actions that are stepping stones for later problems is a real problem. A model might only perform an action a couple of times, and if it doesn’t get any additional reward signal, it might stop, although it would be useful to repeat the action for other rewards. The idea of giving an agent an additional reward for steps that should be repeated multiple times is interesting.

Critical weaknesses

The method increases computational cost. So it could be that PPO, which spends the number of seen environment steps on training instead of training the policy that then redefines the reward, performs better.

While there is some degree of automation, the method still relies on human information. Between the similar games Crafter and Craftax, part of the method had to be adjusted. This reduces the benefit of automation. Additionally, the method can only adjust relative to what the previous policy found, bounding its progress by that of the policy used to make the reward program.

Questions for authors

Did you compare against PPO in a step-matched setting? Producing the setup for the environment seems to involve similar work effort to hand-drafting a reward without performing better. What advantage do we get from automation when considerable human effort has to be spent setting up the reward program without outperforming the hand-drafted baseline?

5 comments
AuthorsOpenReview ↗

Response to Reviewer ogCP (1/2)

Dear Reviewer ogCP,

Thank you for recognizing the motivation for recurrence feedback. According to your comments, we have added experiments and clarifications addressing total interaction costs, automation, and reference coverage.


Regarding weakness 1 and question 1: matching total environment interactions

The original experiments primarily fixed downstream training budgets and did not sufficiently examine the total cost of generating references. We have now added comparisons that account for reference-policy training, trajectory collection, and downstream training; full results are in Appendices K.3 and K.5. At the same total budget of approximately 5M Crafter interactions, SOR uses 21.4% fewer downstream training steps than PPO (3.932M versus 5.001M), while achieving a slightly higher mean native return: 13.07 ± 0.42 versus 12.88 ± 0.32 (five runs, mean ± SD; native return averages the latest 50 completed episodes).

The reference stage produces a reusable, frozen reward program. The downstream policy learns from scratch without inheriting the reference policy's parameters. We therefore evaluate both the program's benefit to downstream learning and the total cost of constructing and using it from scratch. T-REX, Section 5.2 and VIPER, Sections 4.1–4.2 also distinguish reference-data generation, reward construction, and downstream training. In SOR, the constructed program can be reused: our AD experiments use the program built from PPO references without training new reference policies for AD.

We also added reference-cost experiments, reducing two references to one and reference training to 500k steps. With 1M downstream steps, the 500k reference yields Score/native return of 19.32/11.48, close to 19.59/11.60 with a single 1M reference. Compared with the original two-reference configuration, reference training and collection decrease by approximately 73%, and total interactions including downstream training decrease by 50%. These experiments show that reference count and training budget can be adjusted to reduce preparation costs while retaining useful feedback (Section 4.3, Figure 4; Appendices K.1 and K.3).

AuthorsOpenReview ↗

Response to Reviewer ogCP (2/2)

Regarding weakness 2 and question 1: human input, automation, and reference-policy limitations

SOR automates the construction of the concrete reward program. Appendix C specifies the division between human configuration and automatic processing:

StageHuman specification or verificationAutomatic processing and output
Data interfaceState fields, action encoding, native first-unlock labels, episode boundariesCollect trajectories and generate fitting labels from native logs
Event detectionAction/difference grammar and fitting/acceptance criteriaSearch candidates, select by BIC, perform five-fold validation, output detectors
Recurrence structureCounting, partitioning, support, and level-retention conventionsReplay trajectories, count recurrences, select groups and levels
Reward configurationReference budget, global reward parameters, verification and freezingCompute support, group budgets, and per-level payments; export the program

The human settings specify what to observe, how to count, which criteria to apply, and the total reward budget. They apply across candidates. Which events survive, how many recurrence levels receive rewards, and how much budget each group receives are determined by the data and construction rules. Interfaces and counting conventions connect rewards to actual environment operations; acceptance criteria control detector reliability; global parameters control reward scale and reference cost.

For the final programs in the main experiments, the procedure generates all 12/12 detectors, 114/114 recurrence levels, and 12/12 group budgets in Crafter, and all 7/7 detectors, 86/86 levels, and 7/7 group budgets in Craftax. Thus, 0% of these individual program entries are hand-specified; human work concerns the interfaces, global design, parameter selection, and correctness checks above. The new single-reference programs are reconstructed through the same procedure (Appendix K.1).

The manual programs in the paper are strong references developed by the authors using task knowledge and multiple experimental iterations (Section 2, Appendix E). SOR replaces item-by-item reward design with a procedure that can be rerun on new reference trajectories. In the added reference-quality experiments, changing the reference budget while keeping the construction procedure fixed generates new rules, levels, and budgets. The 500k reference produces results close to the 1M reference without manually rewriting individual rewards (Section 4.3, Figure 4; Appendix K.3).

Reference coverage determines which events the auxiliary program can reward, while the downstream policy continues learning from the complete native reward (Section 3.1). For example, the Craftax auxiliary program does not directly reward crafting stone pickaxes or stone swords, yet their success rates increase from 2.0% to 44.4% and from 2.5% to 49.6%, respectively (Section 4.4, Figure 5). Intermediate capabilities reinforced by the auxiliary program can therefore support progress beyond its own event list.


We sincerely hope that our response could address your concerns. Thank you once again for your valuable efforts and continued support!

Best regards,

All authors

Thank you for running the additional experiments. I agree that the amortisation of costs is a potential argument for SOR. Are there any possibilities to show that this method amortises costs better than, say, using the PPO policy? For example, a PPO policy run for the same number of steps as the first phase of SOR could be used to distill an AD policy. Without amortisation, native return doesn’t seem to be better than plain PPO on Crafter (slightly better at 5M steps and slightly worse at the other 3 checkpoints, all within noise) and slightly worse on Craftax. I understand that there isn’t much time for an additional experiment, so if an additional run showing the advantage on amortisation isn’t possible, it would be good to note the missing comparisons in the limitations.

Reviewer_6HCKOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
3
Soundness
1
Read review
Paper summary

This paper proposes Structured Ordinal Reward (SOR), an auxiliary reward construction method for tasks that require repeated execution of previously achieved behaviors. Using first-unlock labels and structured reference trajectories, SOR learns event detectors, constructs finite recurrence milestones, and allocates a bounded reward budget based on empirical event support. The resulting reward program is frozen during downstream training. Experiments on Crafter and Craftax-full show improvements over PPO, with additional analyses of payment timing, budget allocation, and integration with Achievement Distillation. However, the method relies on environment-specific achievement labels and structured state information, and its generalizability beyond closely related survival games remains insufficiently demonstrated by the experiments.

Critical strengths
  • The paper identifies a useful feedback gap: first-success rewards do not directly reinforce subsequent repetitions of intermediate behaviors needed for longer-horizon progress. SOR addresses this gap through a bounded auxiliary reward module without changing the policy architecture.
  • The main PPO comparisons use ten training runs per environment and show consistent improvements in native-task metrics. The payment-timing and allocation controls provide useful evidence about which reward construction choices contribute to these gains.
Critical weaknesses
  • The breadth of validation is limited. Crafter and Craftax-full are closely related survival environments, and SOR relies on first-unlock labels, structured transition information, and reference trajectories with sufficient recurrence coverage. Separate reward programs are constructed for each environment. These experiments therefore provide limited evidence that the construction procedure applies beyond this task family.
  • The matched comparisons primarily establish improvements over PPO and examine variants of SOR. They do not establish its advantage over established exploration bonuses or closely related progress-based reward methods under comparable information and training budgets. This makes it difficult to assess the incremental benefit of the proposed construction relative to existing approaches.
Questions for authors
  • When applying SOR to a new task, which components require manual redesign, particularly the event-rule grammar, structured inputs, and counting conventions? How much of the construction procedure was reused unchanged between Crafter and Craftax-full?
  • Can the authors provide a matched comparison with an established exploration bonus or progress-based reward method, while accounting for the additional information and reference-data costs used by SOR? Such a comparison would materially affect my assessment of the method’s incremental contribution.
4 comments
AuthorsOpenReview ↗

Response to Reviewer 6HCK (1/2)

Dear Reviewer 6HCK,

Thank you for recognizing the feedback gap and the empirical gains. We have clarified the motivation for our environment choices and which components transfer, then present the new exploration-baseline and reference-cost experiments.


Regarding weakness 1 and question 1: transferable components and task-specific adaptation

Our starting point is a feedback gap in long-horizon tasks: intermediate capabilities must be used repeatedly, whereas first-success rewards mark their initial achievement without directly rewarding subsequent recurrence. Crafter and Craftax naturally expose this problem. Resources are consumed, and crafting and continued survival require repeated gathering and replenishment, while achievement rewards are paid only on first completion. Their procedurally generated scenarios, interdependent tasks, and per-achievement evaluation allow us to examine whether recurrence feedback improves native-task progress. These properties also underlie the exploration, skill-reuse, and long-term reasoning challenges emphasized by the Crafter and Craftax benchmarks.

We therefore chose these environments to study the same feedback problem under different implementations and task mechanics. The reusable component is the procedure that constructs rewards from event supervision and reference experience; a new task supplies its own event semantics and data.

Both environments reuse the action-equality/integer-state-difference grammar, BIC selection, five-fold validation, reference replay, finite-level construction, budget normalization, and frozen execution framework. Adaptation concerns the structured fields, first-event labels, acceptance thresholds, support statistics, counting conventions, and global reward parameters. The final detection rules, event groups, levels, and group budgets are generated from data. For example, Crafter excludes the first detector hit at runtime, whereas Craftax gates recurrence counts using the native first unlock. Appendix C specifies these differences.

As a concrete extension, we envisage an Overcooked integration: use ingredient-placement, dish-pickup, soup-pickup, and delivery logs to generate first-event labels; encode held objects and pot contents as structured fields; and fix the partner while counting only the controlled player's events. Rule fitting, reference replay, recurrence-level selection, and budget construction could then provide feedback for the intermediate actions repeated across multiple orders. Evaluation would retain the native delivery reward.

AuthorsOpenReview ↗

Response to Reviewer 6HCK (2/2)

Regarding weakness 2 and question 2: an established baseline and its costs

We added RND experiments in both environments using the same visual PPO backbone, 1M downstream steps, and native evaluation protocol. Its reward coefficient was selected from three candidates per environment and then fixed for five matched runs (Appendix K.2, Tables 30–31; RND is also added to Tables 1–2).

The costs differ in their source. RND uses visual inputs and needs no reference data, but trains a predictor online and evaluates a frozen target network. In the audited RGB configuration, it adds approximately 1.13M trainable parameters and 0.60M frozen parameters. SOR uses first-success labels, structured state changes, and reference trajectories, incurring reference training, collection, and offline construction costs. Once frozen, its program executes rules and counters without an additional trainable network. The structured inputs are used by the reward module; the policy retains its original visual observations.

We also added experiments reducing SOR's reference-policy count and training budget. The table below compares these new configurations with PPO, RND, and the original two-reference program. Values are means over five matched Crafter runs. Every downstream run uses 1.004M steps; total interactions include reference training, collection, and downstream training.

MethodReference training + collection (M steps)Total interactions (M steps)ScoreNative return
PPO01.00415.9710.60
PPO + RND01.00415.0310.11
SOR: original two references2.1383.14219.1911.47
SOR: single 1M reference1.0692.07319.5911.60
SOR: single 500k reference0.5691.57319.3211.48
SOR: single 100k reference0.1681.17114.4010.26

Reference-count comparisons are in Appendix K.1, Table 29; reference-budget experiments are in Section 4.3, Figure 4, and Appendix K.3, Tables 32–33. Development searches and evaluation costs are reported separately from these per-run interaction costs.

The original two-reference setup is not required to retain the gains. A single reference works, and reducing its training budget to 500k preserves mean Score and return close to those of the 1M reference. Relative to the original configuration, this reduces reference interactions by approximately 73% and total interactions by 50%; reducing the reference budget further to 100k loses the gains. Reference count and training budget are therefore adjustable construction costs, allowing a lower-cost choice that retains useful feedback.

In the five matched Craftax evaluations, SOR achieves 5.54%, RND 4.11%, and PPO 3.90% (Appendix K.2, Table 30). SOR uses one 1M reference, giving 2.073M total interactions.


We sincerely hope that our response could address your concerns. Thank you once again for your valuable efforts and continued support!

Best regards,

All authors

AuthorsOpenReview ↗

Additional Response to Reviewer 6HCK

Dear Reviewer 6HCK,

In response to your concern about additional costs, we have added an experiment to test whether we can directly retain the reference policy’s training progress and use SOR to improve subsequent learning.

Starting from the same PPO checkpoint trained for approximately 500k steps, both arms restore the model parameters and optimizer state and continue training for approximately another 500k steps; one arm additionally uses SOR. At approximately 1M cumulative policy-training steps, the results across five paired continuations are as follows (mean ± standard deviation):

MetricPPO continuationPPO + SOR continuation
Cumulative achievement score14.912 ± 1.64316.662 ± 0.800
Native return10.472 ± 0.88211.056 ± 0.276

SOR improves mean score and native return by 11.7% and 5.6%, respectively. Native return averages the latest 50 completed episodes, while cumulative score includes the shared initial 500k-step training history.

This deployment incorporates reference-policy training directly into training the final policy. PPO uses 1,003,520 total environment interactions. SOR additionally uses 65,536 reference-collection steps, bringing its total to 1,069,056 interactions—approximately 6.5% more than PPO, alongside offline reward-construction computation. The initial 500k training steps are counted only once.

This experiment complements our earlier reference-budget results: besides reducing the reference-training budget, we can retain the reference policy and continue learning, allowing its training to contribute to both policy optimization and reward construction. The complete setup, learning curves, and cost accounting have been added to Appendix K.6 of the revised manuscript.

Best regards,

All authors

AuthorsOpenReview ↗

A Gentle Reminder: Discussion Period Nearing Closure

Dear Reviewer 6HCK,

We deeply appreciate the time and effort you have invested in reviewing our manuscript. We have meticulously revised the paper based on your insightful comments and believe that the quality of the work has been significantly improved as a result.

With the discussion period drawing to a close on November 18th, we respectfully remind you to update your score should you find our responses satisfactory. Your positive consideration would be highly appreciated.

Thank you for your patience and valuable guidance throughout this process.

Best regards,

All authors

Reviewer_4Zt5OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes structured ordinal reward (SOR), which leverages the recurring events' information to complement the reward design for the open-world survival scenarios. SOR learns event detectors from the first achievements and uses reference trajectories to select the recurrence levels, allocating the reward budget. In PPO experiments, the SOR design allows training score improvements in Crafter and Craftax-full.

Critical strengths

The motivation for proposing SOR as a more fine-grained reward design for open-world survival tasks is clear: useful intermediate behaviors often need to be repeated even after their first achievement has already been rewarded. Ten-run PPO comparisons support the practical value of this approach, with improvements of 19.5% in Crafter’s cumulative training score and 37.2% in Craftax-full’s native-only checkpoint evaluation score. The per-achievement results further show gains in resource acquisition and tool crafting, providing concrete evidence that the aggregate improvements reflect stronger intermediate capabilities relevant to subsequent task progression.

Critical weaknesses
  1. Limited comparisons with relevant reward-construction baselines: While the main experimental results in Tables 1 and 2 demonstrate gains from SOR, the paper lacks sufficient empirical comparisons with relevant reward-construction baselines, particularly alternative ways of using the same first-unlock labels and reference trajectories to construct auxiliary rewards. The internal controls examine SOR’s design choices, but the related methods discussed in Appendix I are not evaluated under comparable conditions. Comparisons with representative alternatives, with supervision and construction costs matched or explicitly accounted for, would help establish the value of SOR beyond its improvement over native-reward PPO.

  2. Unclear connection between rewarding recurrence and improving native-task performance: Figures 3 and 4 show that aggregate scores increase alongside per-achievement success rates, but they do not establish which rewarded recurrences contribute to progress toward subsequent achievements. In particular, SOR allocates larger budgets to events with greater recurrence support in the reference data, although frequent occurrence does not necessarily indicate usefulness for the native task, as acknowledged in Appendix J. While the allocation controls provide evidence for the tested configurations, controlled comparisons across event groups or changes in their task relevance would help determine whether the construction reliably rewards useful repetition rather than favoring common, easily repeated behaviors.

Questions for authors
  1. How would relevant baselines (e.g., in Appendix J) perform on the same settings on two games?
3 comments
AuthorsOpenReview ↗

Response to Reviewer 4Zt5

Dear Reviewer 4Zt5,

Thank you for recognizing the motivation and the improvements in intermediate capabilities. We have added an exploration baseline and analyses connecting reference experience, reward construction, and subsequent task progress.


Regarding weakness 1 and question 1: reward-construction comparisons

To our knowledge, no prior method combines native first-unlock supervision for learning recurring-event detectors with reference-based construction of finite recurrence levels and support-based allocation of a fixed auxiliary budget. This specific construction, which turns first-success supervision into bounded recurrence rewards, is the methodological contribution of SOR.

The methods in Appendix I are related at different levels. AD and world-model methods provide performance references on the same environments; the main tables include our AD reproduction and published world-model results. VICE learns event rewards from success examples, while reward-machine learning constructs temporal reward structures from high-level event traces. ProgressCounts and Strategist use LLM-generated progress or strategy information.

A further relevant method is From Laws to Motivation, which uses ten successful and ten failed human interaction records per achievement and DeepSeek-V2 to generate action preconditions and reward rules. Its PPO agent achieves a Crafter Score of 12.3 ± 0.8 after 4M steps, versus 9.7 ± 0.7 without the invalid-action penalty (Table 2 of that paper); it reports experiments on Crafter. These published results use human examples, LLM inputs, and a different training budget from our experiments. SOR uses native first-unlock labels and policy-generated reference trajectories to construct bounded feedback for recurrence beyond first success.

For alternative constructions using the same reference information, K10-Uniform and K10-Support share the detectors, recurrence caps, and total reward budget, changing only the allocation across event groups. Their Scores are 16.78 and 19.60, respectively (Section 4.6, Figure 6d). We also added RND in both environments, using the same visual PPO backbone, 1M downstream steps, and native evaluation protocol. Across five matched runs, single-reference SOR versus RND achieves Crafter Scores of 19.59 versus 15.03 and native returns of 11.60 versus 10.11; Craftax evaluation scores are 5.54% versus 4.11%. The new RND results appear in Tables 1–2, with the matched comparisons in Appendix K.2, Table 30. RND requires no reference trajectories; SOR's additional structured inputs and reference-training and collection costs are documented in Appendices K.2–K.3.


Regarding weakness 2: recurrence rewards and subsequent task progress

To address whether highly supported events are associated with subsequent progress, we added a temporal analysis using separately collected trajectories that were not used to fit detectors. After the first recurrence of each event, we measure the fraction of previously locked achievements subsequently unlocked. Across the 12 event groups, its Spearman correlation with reference support is 0.59 (Appendix K.4, Table 34). The two existing budget-permutation controls preserve the set of group budgets and their total while changing which event receives each budget; both reduce mean performance (Section 4.6, Figure 6c). Together, these analyses connect recurrence support to subsequent unlocks and support the value of assigning budgets to particular events.

The deeper question is why reference support should help construct useful rewards. Our premise is that the task information carried by support depends on what the reference policy has learned. A weak policy can frequently repeat easy behaviors; further native-task training can produce reference experience containing more useful intermediate capabilities. We therefore collected 65,536 transitions from each of the 100k and 500k checkpoints of a PPO reference run, keeping the construction procedure, total auxiliary budget, and downstream training settings fixed.

The program constructed from the 100k reference did not improve mean performance over native PPO. The 500k program improved both Score and native return over PPO in all five matched runs. Mean Scores were 14.40 versus 19.32, and native returns were 10.26 versus 11.48, for the 100k and 500k programs, respectively (Section 4.3, Figure 4; Appendix K.3, Table 32). Thus, the same construction procedure produces useful feedback from more developed task experience. These results support SOR's design: the reference policy supplies task experience, and SOR converts its event coverage, recurrence depth, and support statistics into a reusable reward program.


We sincerely hope that our response could address your concerns. Thank you once again for your valuable efforts and continued support!

Best regards,

All authors

AuthorsOpenReview ↗

Additional Response to Reviewer 4Zt5

Dear Reviewer 4Zt5,

Thank you for your suggestions regarding baseline comparability and reward-construction costs. We have added a paired continuation experiment starting from the same PPO checkpoint trained for approximately 500k steps. Both arms restore the model parameters and optimizer state and train for approximately another 500k steps; one arm additionally uses SOR. The baseline therefore also retains the reference policy’s training progress, allowing us to examine SOR’s additional value on top of policy reuse.

Across five paired continuations, SOR improves mean cumulative score and native return by 11.7% and 5.6%, respectively. Because the reference policy directly becomes the final policy, the initial 500k training steps are counted only once. SOR additionally requires 65,536 collection steps, bringing its total to 1,069,056 environment interactions—approximately 6.5% more than PPO’s 1,003,520 interactions, alongside offline reward-construction computation.

This experiment complements our existing reward-construction controls and RND comparison: when both arms retain the existing policy’s capabilities, SOR still improves subsequent learning with a relatively small additional interaction cost. The experimental setup, learning curves, and full cost accounting have been added to Appendix K.6 of the revised manuscript.

Best regards,

All authors

AuthorsOpenReview ↗

A Gentle Reminder: Discussion Period Nearing Closure

Dear Reviewer 4Zt5,

We deeply appreciate the time and effort you have invested in reviewing our manuscript. We have meticulously revised the paper based on your insightful comments and believe that the quality of the work has been significantly improved as a result.

With the discussion period closing on November 18th, we respectfully remind you to update your score should you find our responses satisfactory. We would greatly appreciate your positive consideration.

Thank you for your patience and valuable guidance throughout this process.

Best regards,

All authors

Comments on the paper

1 comment
Area_Chair_Cg7nOpenReview ↗

Do the rebuttals address your concerns?

Hi Reviewers,

If you haven't done already, please read the author rebuttals and to let them know if it addresses the concerns raised in the original reviews.

Thanks!

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.