💬 NLP

PolicyBank: Evolving Policy Understanding for LLM Agents

The paper introduces PolicyBank, a memory mechanism that enables LLM agents to autonomously refine their understanding of ambiguous organizational policies through iterative interaction and corrective feedback, significantly closing the gap between agent behavior and true requirements where existing methods fail.

Original authors: Jihye Choi, Jinsung Yoon, Long T. Le, Somesh Jha, Tomas Pfister

Published 2026-04-20

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jihye Choi, Jinsung Yoon, Long T. Le, Somesh Jha, Tomas Pfister

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you hire a very smart, highly trained personal assistant (an LLM Agent) to run your company's customer service. You give them a thick, written rulebook (the Policy) written in plain English.

The problem? The rulebook isn't perfect. It has typos, vague phrasing, and missing details. For example, the rulebook might say: "If a customer complains about a delay, give them a $50 gift card only if they also want to change their flight."

In reality, your company actually wants to give the gift card to anyone who had a bad delay, even if they just want to keep their flight. But because the assistant is so obedient, they follow the rulebook literally. They deny the gift card to the loyal customer who just wants to keep their seat. The assistant is doing exactly what they were told, but they are failing the company's actual goal.

This is the core problem the paper PolicyBank solves.

The Old Way: "The Stuck Record"

Currently, most AI assistants treat the rulebook as immutable truth. If the rulebook says "No," the AI says "No," even if the rulebook is wrong.

Think of it like a GPS that is stuck on an old map. If the road is closed, the GPS keeps telling you to drive into a wall because the map says the road is open. Even if you tell the GPS, "Hey, there's a wall here!" the GPS just ignores you and tries to drive through again, because it trusts the map more than your eyes.

Existing AI memory systems are like this. They remember how to do tasks (e.g., "how to book a flight"), but they don't remember why a rule might be wrong. They just reinforce the mistake.

The New Way: PolicyBank (The "Living Rulebook")

The authors propose PolicyBank, a system that lets the AI evolve its understanding of the rules.

Imagine instead of a static rulebook, the AI has a living, breathing notebook that it updates in real-time.

The Test Drive (Pre-deployment): Before the AI goes live, a human tester (the "QA Engineer") runs through scenarios.
- Scenario: A Gold member complains about a delay but doesn't want to change flights.
- AI Action: Denies the gift card (following the flawed rulebook).
- Human Feedback: "Stop! That's wrong. Gold members get the gift card even if they don't change flights. The rulebook is misleading."
The Update (PolicyBank in Action):
- Instead of just saying "Okay, I'll try again," the AI's PolicyBank takes this feedback and rewrites its internal logic.
- It creates a new, precise note: "For Gold members, the 'change flight' rule is a red herring. Ignore it. Just check if they are Gold and if the flight was delayed."
- This note is stored in a structured "bank" of insights, ready to be pulled up instantly next time.
The Result:
- The next time a Gold member complains, the AI doesn't just "guess" better. It actively retrieves the specific insight from its PolicyBank: "Ah, I remember this! The 'change flight' condition doesn't apply here."
- It gives the gift card correctly.

The Three Types of "Rulebook Glitches"

The paper identifies three common ways rulebooks fail, which PolicyBank fixes:

The "Too Narrow" Trap (Ambiguous Scope): The rulebook says, "We refund for health or weather reasons." But in reality, we should refund for any valid reason if you have insurance. The AI learns to ignore the narrow list and look at the bigger picture.
The "Missing Exception" Trap (Under-Specified): The rulebook says, "You can't change your destination." But it forgets to mention that changing from one NYC airport (JFK) to another (LGA) is fine. PolicyBank learns this exception.
The "False Link" Trap (Logical Contradiction): The rulebook says, "If you want a refund, you must also want to cancel." But sometimes you want a refund without canceling. PolicyBank learns to break the link between these two unrelated ideas.

Why This Matters

In the real world, policies are messy. They are written by humans, for humans, and they often contain gaps.

Without PolicyBank: The AI is a rigid robot that follows bad instructions, frustrating customers and damaging the brand. It fails repeatedly because it's trying to solve a puzzle with a broken piece.
With PolicyBank: The AI is a smart apprentice. It makes a mistake, gets corrected, updates its internal "cheat sheet," and immediately gets it right the next time. It doesn't just learn how to do the job; it learns what the job actually is.

The Bottom Line

PolicyBank is like giving your AI agent a self-updating GPS. When the map is wrong, the agent doesn't crash; it listens to the passenger, updates the map, and finds the right route. It turns a "compliant but wrong" robot into a truly helpful, adaptable assistant.

1. Problem Statement: The Specification–Requirement Gap

The paper addresses a critical failure mode in Large Language Model (LLM) agents operating within organizational constraints. While existing research focuses on ensuring agents follow written policies, it often assumes the policy text ( $\pi_{spec}$ ) is a complete and unambiguous proxy for true requirements ( $\pi_{req}$ ).

In reality, Natural Language (NL) policy specifications are prone to:

Ambiguities: Imprecise quantifiers or lists.
Under-specification: Missing valid exceptions or edge cases.
Logical Contradictions: False dependencies between unrelated variables.

This leads to Type II Failures (Alignment Failures): The agent faithfully executes the written policy but fails the true requirement because the policy itself is flawed. Existing memory mechanisms (e.g., Synapse, AWM, ReasoningBank) treat the policy as immutable ground truth. They reinforce "compliant but wrong" behaviors by learning from successful trajectories that strictly follow the flawed policy, rather than correcting the policy interpretation itself.

Core Question: Can an agent autonomously refine its interpretation of imperfect policy specifications through interaction and corrective feedback to close the gap between $\pi_{spec}$ and $\pi_{req}$ ?

2. Methodology: PolicyBank

The authors propose PolicyBank, a memory mechanism designed to automate policy updates by maintaining structured, tool-level insights rather than raw task trajectories.

A. Core Architecture

PolicyBank operates in a pre-deployment or streaming workflow where a "Policy Agent" (an offline LLM) iteratively refines a memory bank ( $M$ ) based on task trajectories ( $\tau$ ) and developer feedback ( $\Phi$ ).

Structured Memory Schema:
Unlike previous methods that store raw text or trajectories, PolicyBank stores entries at the tool-capability level. Each entry is a tuple containing:
- ID & Tool/Capability: Specific tool and function (e.g., send_certificate).
- Spec_NL: A semi-structured natural language field decomposing the policy into:
  - TRIGGER: When the capability applies.
  - PRECONDITIONS: Verification steps.
  - ELIGIBILITY: Conditions for permission (using logical operators like ANY/ALL).
  - ACTION: The procedure to follow.
  - KEY INSIGHT: The learned delta resolving the gap between the written policy and true requirements.
Agent-Triggered Retrieval:
Instead of injecting the entire policy into the context window (which causes context bloat), the agent uses a retrieve_policy() tool. It dynamically queries the memory bank for relevant rules based on the current conversation state, ensuring scalability and precision.
The Feedback Loop (Policy Agent):
After a task, a dedicated Policy Agent analyzes the trajectory and developer feedback (binary pass/fail + NL explanation). It performs one of three operations:
- Add: Create a new entry for uncovered capabilities.
- Revise: Update an existing entry to correct misaligned logic (e.g., removing a false dependency).
- Omit: No change if the existing logic is sufficient.
- Crucially, the Policy Agent is prompted to distinguish between Type I (execution/reasoning errors) and Type II (specification gaps), focusing its updates on the latter.

3. Evaluation Framework: $\tau$ -Bench Extension

To rigorously test policy evolution, the authors extended the popular $\tau$ -Bench (Airline and Retail domains) by introducing Policy Gaps.

Gap Identification: They analyzed tasks where frontier LLMs failed due to specification gaps, categorizing them into three structural classes:
1. Ambiguous Scope: Treating illustrative lists as exhaustive.
2. Under-Specified Exceptions: Missing valid edge cases (e.g., same-item replacement for defective goods).
3. Logical Contradiction: False dependencies (e.g., requiring flight cancellation to receive delay compensation).
Sister Tasks: For every "Parent" task containing a gap, they generated three "Sister" tasks to test generalization:
- Simplified: Isolates the gap.
- Different Instance: Tests transfer to new users/contexts.
- Complex Variant: Tests robustness under cognitive load/distractions.
Metric: $pass^k$ (probability of $k$ consecutive successful trials), emphasizing consistency over single-shot success.

4. Key Results

The experiments compared PolicyBank against baselines including "No Memory," Synapse, AWM, and ReasoningBank, using Gemini-3.0-Pro and Claude-4.5-Opus.

Failure of Existing Methods: Standard memory mechanisms achieved near-zero success ( $<0.02$ $pass^1$ ) on Sister Tasks (policy-gap scenarios). They reinforced the flawed policy logic, unable to distinguish between "doing the task right" and "following the wrong rule."
PolicyBank Performance:
- Gap Closure: PolicyBank closed up to 82% of the performance gap toward a human oracle (perfect policy understanding).
- Consistency: It significantly improved $pass^k$ metrics. For example, in the Retail domain with Claude-4.5-Opus, PolicyBank achieved a $pass^4$ of 0.67 on sister tasks, while the best baseline was 0.28.
- Generalization: The agent successfully applied refined insights to "Different Instance" and "Complex Variant" sister tasks immediately after the first correction (one-shot learning).
Feedback Granularity: The study found that binary rewards alone were insufficient for policy evolution. NL Explanations (e.g., "compensation should be offered regardless of modification intent") were critical for the Policy Agent to deduce the correct logical structure.

5. Significance and Contributions

New Problem Formulation: The paper formalizes Evolving Policy Understanding, distinguishing execution failures from alignment failures caused by specification gaps.
Novel Mechanism: PolicyBank is the first framework to treat policy interpretation as a learnable, evolving variable rather than a static constraint. It shifts the burden from manual rule rewriting to automated, structured insight refinement.
Benchmark Contribution: The extended $\tau$ -Bench provides a standardized testbed for evaluating agent adaptability to imperfect specifications, a critical real-world scenario often ignored in favor of "perfect" synthetic benchmarks.
Practical Impact: The approach offers a pathway for deploying LLM agents in high-stakes environments (finance, healthcare, customer service) where policies are complex, ambiguous, and subject to change, allowing agents to self-correct before full system redeployment.

In conclusion, PolicyBank demonstrates that LLM agents can autonomously evolve their understanding of organizational rules, transforming from rigid rule-followers into adaptive agents capable of resolving the inherent ambiguities of natural language policy specifications.