Reward Design as a Procedure: From Objectives to Causal Coverage to a Polytope of Weights

Paper: 2608.12302 Authors: Di Yang Shi, W. Bradley Knox Categories: cs.LG

The Gap

Reward design is the last unformalized step in reinforcement learning. Everything downstream of the reward function has decades of theory; the reward function itself is typically produced by someone staring at a task, guessing a weighted sum of things they can measure, watching the agent exploit it, and nudging coefficients. Knox’s own earlier work on autonomous-driving reward functions documented how bad this gets in practice: published AV reward functions routinely contain terms that are outright incentive-inverted, and nobody notices because there is no procedure to check against.

The existing alternatives each dodge a different piece of the problem rather than solving it:

• Reward shaping / manual tuning has no stopping rule and no notion of correctness. You iterate until the agent stops embarrassing you.
• IRL and RLHF learn a reward from data, but they collapse the human’s preferences into a point estimate through a noise model (usually Bradley–Terry) fit by maximum likelihood. Contradictory labels get absorbed silently into the likelihood; you never learn that your feature set cannot represent the preferences you claim to have. And they say nothing about *which features to use — the feature vector is an input, not an output.
• Active preference learning (max-volume-removal query selection and friends) does pick informative queries, but under a probabilistic model where “feasible” is soft. There is no guarantee that the returned reward function respects the answers actually given.
• LLM-written reward functions (Eureka-style) produce plausible code with no auditable link between the code and the stated objectives.
• Decision analysis (value-focused thinking, multi-attribute utility theory) has had the “fundamental vs. means objectives” machinery since Keeney & Raiffa, but it was never wired into RL reward construction as an executable pipeline.

So the gap is specific: nobody had an end-to-end process that takes a natural-language task description and returns a linear reward function while (a) justifying the choice of reward terms and (b) provably respecting a given preference ordering over trajectories.

PROBLEM: reward functions are hand-guessed
         no rule for choosing terms
         no rule for choosing weights
         no rule for stopping
              |
              v
ASSUMPTION: preferences over trajectories can be
            captured by a LINEAR score over
            measurable outcome variables
              |
      +-------+--------------+--------------+
      v                      v              v
[STEP 1]               [STEP 2]        [STEP 3]
guided workflow        term choice     weight fitting
task text >            min-cost        convex feasible
fundamental            partial cover   region cut by
objectives >           on causal DAG   preference
outcome vars           via max-flow    queries
      |                      |              |
      +-------+--------------+--------------+
              v
EVIDENCE: step 2 solved exactly in polynomial time
          step 3 reaches tolerance in O(n log k) queries
          feasible region provably never empties
          (formal guarantees rather than benchmark curves)
              |
              v
CONCLUSION: reward design becomes a checkable
            procedure a non-expert can run
            and an auditor can inspect

The Increment

One sentence: Before this paper, “how did you pick those reward terms and weights” had no answer better than *judgment; after it, term selection is an exactly-solvable graph problem and weight fitting is a convex region you shrink with a logarithmic number of questions, with the guarantee that the region never becomes empty by accident.

Core Mechanism

Step 1 (informal, human-in-the-loop). Start from the task in natural language. Repeatedly ask “why do I care about this?” until you hit things you want for their own sake — the *fundamental objectives — and discard the means objectives that were only instrumentally valuable. Then, for each fundamental objective, write down measurable outcome variables: quantities computable from a trajectory that move when the objective is served. Output: a candidate pool of outcome variables, each tagged with the objective it speaks to and a cost (measurement difficulty, sensor availability, annotation burden).

Step 2 (formalized). The candidate variables are not independent — they sit in a causal DAG. If smooth acceleration causes passenger comfort which causes good ratings, you do not need all three as reward terms; rewarding the right node handles the others. The paper turns “pick a causally representative subset” into minimum-cost partial cover on the DAG: choose the cheapest set of nodes such that every fundamental objective is covered through the causal structure, possibly up to a partial-coverage requirement. Generic min-cost partial cover is NP-hard; the DAG’s ancestor/descendant structure is what buys tractability, and the problem is solved exactly in polynomial time by a max-flow / min-cut formulation — the same closure-selection trick that makes project selection and image segmentation tractable. Output: the reward terms phi_1 ... phi_n.

Step 3 (formalized). The reward is r(t) = w . phi(t). Every preference answer “trajectory A is better than B” is a linear inequality w . (phi(A) - phi(B)) > 0 — a halfspace. The set of weight vectors consistent with all answers so far is therefore a convex cone, and reward design becomes convex feasibility: find any point in it, and shrink it until every point in it is within tolerance of every other. Each query is chosen as a cutting plane through the current region — crucially, a query is only asked if both possible answers leave a nonempty region, which is what makes the process *deterministically conflict-free: the feasible set can never be emptied by a contradiction between answers. Off-the-shelf separation-oracle methods then give the bound: O(n log k) queries for n reward terms and precision ratio k. That is a high-dimensional binary search over reward functions.

natural language task description
        |
        v
+---------------------------------------------+
| STEP 1  objectives workflow (guided/manual) |
|   task text                                 |
|     > why do I care  >  fundamental objs    |
|     > measurable outcome variables + cost   |
+---------------------------------------------+
        | V = candidate outcome variables
        v
+---------------------------------------------+
| STEP 2  reward term selection (exact)       |
|   causal DAG over V                         |
|                                             |
|     smooth_accel --> comfort --> rating      |
|          |                         ^        |
|          +------> spill_risk ------+        |
|                                             |
|   pick cheapest S in V that covers every    |
|   fundamental objective through the DAG     |
|   = min-cost partial cover                  |
|   = max-flow / min-cut   (poly time)        |
+---------------------------------------------+
        | phi = (phi_1 ... phi_n)
        v
+---------------------------------------------+
| STEP 3  weight fitting (convex feasibility) |
|   r(t) = w . phi(t)                         |
|                                             |
|   W_0 = initial weight region               |
|   loop:                                     |
|     oracle proposes cut  h  through W_i      |
|     ask human:  A better than B             |
|     answer gives  w . (phi(A)-phi(B)) > 0   |
|     W_i+1 = W_i  intersect  halfspace       |
|     both sides nonempty by construction     |
|   until diameter(W) < tolerance             |
|                                             |
|   query count:  O(n log k)                  |
+---------------------------------------------+
        |
        v
r = w . phi     w drawn from a nonempty region
                that satisfies every answer given

The structural metaphor: commissioning a factory’s health dashboard.

You have been hired to build a single “plant health score” for a factory, and the plant manager is a non-expert who knows what good and bad days feel like but cannot write the formula.

Step 1 is the interview. The manager says “I want the conveyor at 4 m/s.” You ask why. Because throughput. Why? Because delivery deadlines. Deadlines are what he actually cares about; conveyor speed was just a means. You keep pushing until you have the short list of things wanted for their own sake, then list every gauge reading that could reflect them.

Step 2 is sensor placement. The factory is a network of pipes: pressure upstream causes flow downstream causes tank level. Sensors cost money, and a sensor at the right junction tells you about everything downstream of it — so you do not instrument every pipe, you instrument the cheapest set of junctions that still lets you observe every outcome you care about. That is exactly min-cost partial cover on the causal DAG, and max-flow is the routing computation that finds the optimal placement rather than a greedy guess.

Step 3 is calibrating the dials. Each gauge feeds a dial that sets its contribution to the single score, and you do not know the dial settings. So you show the manager pairs of days: “was Tuesday better than Wednesday?” Every answer is a fence post — it rules out all dial settings that would have scored Wednesday higher. The remaining legal settings form a fenced plot of land, and each new question is a fence line drawn through the middle of the remaining plot, so the land halves each time. Two rules matter. First, you never ask a question whose answer would fence off everything — so the plot is never empty, and there is always a valid dashboard you can ship. Second, you stop when the plot is small enough that any point in it gives practically the same score. That stopping rule is the thing hand-tuning never had.

If the plot ever would be emptied, that is not a failure of the method — it is the method telling you that no linear score over your chosen gauges can reproduce the manager’s preferences, and you must go back to step 1 or 2. The fence is also a falsification test.

Key Concepts

• Fundamental vs. means objectives: Ask a driver what a good trip is and you get “stay in the lane, keep 2 seconds of following distance, don’t brake hard.” None of those are things anyone wants for their own sake — they are all instruments for *arrive safely and comfortably on time. That distinction matters enormously for reward design, because if you reward means objectives directly you have hard-coded one particular strategy into the reward and the agent will optimize the proxy past the point where it still serves the real goal (hard braking is bad — until it prevents a collision, at which point your reward punishes the correct action). The test is mechanical: ask “why do I care?” If there is an answer, it is a means objective; go one level up.

• Causal coverage of a reward term: Suppose you care about passenger comfort, and you can measure jerk (rate of change of acceleration), self-reported comfort ratings, and whether the coffee spilled. All three carry the same signal because jerk *causes the other two. Adding all three to the reward function does not triple your information — it triples your ability to double-count and to introduce contradictions between terms. “Causally representative” means: pick a set of nodes such that every fundamental objective is reachable through the causal structure from something you are rewarding. This is why reward-term selection is a covering problem and not a feature-importance problem, and why the answer depends on measurement cost: you would rather reward cheap upstream jerk than expensive downstream survey ratings if they cover the same objective.

• The feasible weight region (and why keeping it beats fitting it): In RLHF you take a pile of comparisons and fit one weight vector by maximum likelihood. Here you keep the *set of every weight vector consistent with the comparisons. Geometrically: each comparison is a plane through the origin, “better” picks one side, and the consistent weights are the wedge where all the chosen sides overlap. Three consequences fall out for free. (1) You can report uncertainty as a shape, not a variance estimate from an assumed noise model. (2) You know when to stop asking — when the wedge is thin enough that every reward function in it ranks things the same way. (3) An empty wedge is a proof that your terms cannot express the preferences, which an MLE fit would have hidden from you by returning its best compromise. The price is that a single mistaken human answer is not absorbed as noise — it is treated as truth and permanently cuts away part of the region.

Framework Shift

Before (mainstream approach)         After (this paper)

  task in someone head                task text
        |                                  |
        v                                  v
  guess feature list                  fundamental objectives
  (importance / intuition)            (why do I care ladder)
        |                                  |
        v                                  v
  guess weights                       causal DAG over
        |                              outcome variables
        v                                  |
  train agent                              v
        |                             min-cost cover
        v                             via max-flow
  watch reward hacking                     |
        |                                  v
        +----> tweak ----+            W = ALL weights
        ^                |            consistent with
        |                |            every answer
        +----------------+                 |
                                           v
  loop with no stopping rule          query > cut > query
  one weight vector                   halve W each time
  no idea if it is                         |
  even representable                       v
                                      stop at tolerance
                                      region provably nonempty
                                      or provably unrepresentable

From fit a point estimate to whatever data you happened to collect to maintain the set of all admissible reward functions and shrink it deliberately, the core shift is treating reward design as constraint satisfaction with a termination criterion rather than as regression.

Expert Assessment

Problem choice: Real gap, and well-positioned. This is the constructive sequel to the “reward misdesign” critique literature — having shown that practitioners get reward functions badly wrong, the natural next move is to hand them a process instead of a warning. The step-2 contribution in particular fills a hole nobody was even naming: the RLHF/IRL literature treats the feature map as given, and there was no principled story for where reward terms come from. The framing also usefully imports decision analysis into RL, which is overdue.

Method maturity: Steps 2 and 3 are genuine cleverness of the “notice that your problem is secretly a solved problem” variety, which is the good kind. The max-flow reduction is the more interesting of the two — min-cost partial cover is NP-hard in general, so the whole result lives inside the structural assumptions about the DAG and the coverage requirement, and that is the first thing I would read the paper for. If coverage is defined per-objective independently over ancestor sets, the closure/min-cut formulation is natural but also not deep; the value is in having stated the problem crisply, not in the algorithm. Step 3 is a straightforward application of existing cutting-plane machinery, and the abstract is appropriately honest about that (“solved by existing separation oracle methods”). The O(n log k) bound is the standard cost of high-dimensional bisection, and the practical caveat is that achieving it needs a good centering method — exact center of gravity is intractable, ellipsoid wastes a dimension factor, and sampling-based centers bring back the randomness that the “deterministic” framing is advertising against. Step 1 is not a method at all; it is a workflow, and calling it a “contribution” alongside two theorems is a stretch.

Experimental integrity: The abstract advertises no empirical results — no human-subject study, no RL training runs, no comparison against an RLHF or active-preference-learning baseline. That may be a deliberate positioning choice (this is a framework-and-theory paper), but it leaves the two load-bearing assumptions untested. The first is linearity: the guarantee is “conflict-free feasible region for a linear reward over the chosen terms,” and if human preferences are not linear in those terms, the honest outcome is an empty region, which the method converts into “go back to step 1” — an infinite regress with no evidence about how often it terminates. The second and larger one is the noiseless oracle. Deterministic conflict-freeness requires that the human never errs, never is inconsistent, and never changes their mind, which is precisely the opposite of what every preference-elicitation user study has found. RLHF’s probabilistic model is not there out of laziness; it is there because the data is noisy. A single erroneous answer here permanently amputates part of the region, possibly the part containing the true weights, and no amount of subsequent querying recovers it. I would want to see either a robust variant (soft cuts, region inflation, retractable queries) or an experiment showing how badly one bad answer hurts. Also unaddressed in the abstract: the causal DAG is an *input, elicited from the same non-expert who could not write a reward function. Garbage DAG, garbage cover.

Writing quality: The abstract is unusually clear about what is formalized versus what is a workflow, which I appreciate. The corner cut is step 1 — a “guided workflow” is the part a non-expert will actually spend their time in, and it is the part with no guarantees, no user study, and probably the least page count. Rewriting step 1 as a worked end-to-end case study, with the causal DAG explicitly elicited and the queries actually answered by a human, would elevate the whole paper from a framework proposal to something a practitioner could copy. Second priority: an explicit section on what happens when the region empties, since that failure mode is the method’s most interesting diagnostic and its most likely practical outcome.

Verdict: weak accept — two clean formalizations of steps everyone previously hand-waved, held back by a noiseless-human assumption and (as far as the abstract reveals) no empirical validation of the one step that humans actually perform.

Takeaways

Things worth stealing regardless of whether you ever build a reward function:

• The “why do I care?” ladder as a spec-review tool. Take any metric dashboard, OKR list, or loss function you own and climb it. Every term that has an answer to “why do I care about this” is a means objective, meaning you have hard-coded a strategy into your objective and your optimizer will eventually break it. This is a five-minute audit with a high hit rate.

• Feature selection as coverage over a causal graph, not importance ranking. When you have many correlated candidate signals, the right question is not “which one predicts best” but “which cheapest subset causally covers everything I care about.” Reward the mediator, not the symptoms. This reframing transfers directly to metric design, monitoring/alerting (the classic sensor-placement version), and A/B test guardrail selection.

• Represent your labeled preference data as a polytope and check whether it is empty. This is a free falsification test on your feature set, and it is something maximum likelihood structurally cannot give you: an MLE always returns an answer, so it never tells you that no member of your model class can honor your data. Even if you ultimately fit a probabilistic model, running the feasibility check first tells you whether your features are expressive enough or your labels are contradictory.

• Query selection by bisection with a nonemptiness precondition. Only ask questions where both answers leave a live hypothesis set, and prefer the question that halves the set. That gives you a labeling budget that scales as (dimension × log precision) instead of (however many labels you can afford), plus an actual stopping rule. Useful anywhere you are paying humans per label: annotation, config tuning, elicitation of preferences from stakeholders.

• The transferable meta-move: when a design step is currently “use judgment,” try to find the constraint set it implicitly defines, and ask whether that set is convex or graph-structured. If it is, you have a solvable problem and a termination criterion where you previously had an art.