Personalized Path Recourse

Dat Hong, Tong WangarXiv 2023 · DOI · arXiv

In the rapidly evolving landscape of machine learning, "recourse" has traditionally focused on answering a simple question: "What should I have done differently to get a better outcome?" Most existing methods treat this as a static problem—for instance, suggesting a loan applicant increase their savings to flip a classification from "denied" to "approved." However, real-world decisions are rarely static; they are sequences of actions taken over time.

A recent study by researchers at Yale University introduces Personalized Path Recourse (PPR), a framework that moves beyond one-off feature changes to suggest entire alternative trajectories. Crucially, these paths are not just effective at reaching a goal; they are tailored to the individual's unique behavioral patterns and preferences.

The Challenge of Sequential Recourse

Most algorithmic recourse research focuses on supervised learning settings. In sequential environments like career planning, financial management, or robot navigation, simply changing a single feature is insufficient. If an individual seeks a higher income, a generic algorithm might suggest they become a professional athlete. While this path leads to the desired goal, it ignores the person's history, skills, and "intrinsic policy"—their natural way of interacting with the world.

Personalized recourse paths in a grid-world environment for different driver types.

The challenge is to provide recourse that satisfies two criteria:

  1. Path-level personalization: The suggested sequence should remain as similar as possible to the original choices to minimize the "cost" of change.
  2. Policy-level personalization: The new path must respect the user's inherent style (e.g., a risk-averse driver should not be told to take dangerous shortcuts).

Methodology: Reward Shaping for Personalization

The authors frame the problem using Markov Decision Processes (MDPs) and employ Deep Q-Networks (DQN) to train a recourse agent. The core innovation is a multi-objective reward function designed to balance three goals:

  • Goal Achievement ($R_{goal}$): Rewards the agent for reaching the desired terminal state.
  • Path Similarity ($R_{path}$): Uses the Levenshtein (edit) distance to reward paths that require minimal changes (insertions, deletions, or substitutions) relative to the original sequence.
  • Policy Alignment ($R_{policy}$): Ensures the recommended actions align with the user's original behavior. The authors developed a specific link function $h(p)$ to normalize action probabilities across different action space sizes, ensuring that "likely" actions are rewarded and "unlikely" ones are penalized relative to random chance.

To navigate the vast space of possible sequences, the training algorithm utilizes an Upper Confidence Bound (UCB) exploration strategy, ensuring an efficient search for optimal personalized paths.

Experimental Evaluation

The PPR method was tested across four distinct environments:

  1. Grid-world: A taxi simulation where agents have different driving styles (e.g., preferring highways over local roads).
  2. Super Mario Bros: Generating recourse for agents with different objectives, such as "coin seekers" versus "coin dodgers."
  3. Text Generation: Modifying the sentiment of sentences while preserving the specific writing style of different corpora (e.g., the Bible vs. Harry Potter).
  4. Climate Data: Adjusting temperature profiles of one city to match another while maintaining local seasonal patterns.

Results and Discussion

The results demonstrate that PPR effectively balances goal attainment with personalization. In the grid-world environment, PPR successfully suggested different routes for "experienced" versus "new" drivers, outperforming baselines that provided generic, one-size-fits-all solutions.

PPR generated paths for 'coin seeker' and 'coin dodger' agents in Super Mario Bros.

In the Mario environment, the distinction was even clearer. For a "coin seeker" who failed early, PPR suggested a path that both navigated obstacles and collected coins. Conversely, for a "coin dodger," the suggested recourse reached the goal while strictly avoiding coins, respecting the agent's intrinsic preference.

In text generation, the model flipped sentiments (e.g., from "sad" to "happy") while maintaining the linguistic "flavor" of the target style. In climate tasks, it intelligently modified only the necessary segments (e.g., summer months) to match a target profile, leaving similar segments (e.g., winters) untouched—a level of precision baselines failed to achieve.

Conclusion and Future Directions

Personalized Path Recourse represents a significant step toward more human-centric AI. By treating recourse as a trajectory rather than a point, and by explicitly modeling user "style," PPR provides recommendations that are both actionable and authentic.

While currently limited to discrete action spaces and requiring knowledge of the user's policy, future work aims to extend this to continuous environments and explore "diverse" recourse, offering users multiple personalized paths to their desired future. This research paves the way for AI systems that don't just tell us where to go, but help us get there in a way that feels like ourselves.

Summary updated

BibTeX
@misc{hong2023personalized,
  author = {Dat Hong and Tong Wang},
  title = {{Personalized Path Recourse}},
  year = {2023},
  eprint = {2312.08724},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2312.08724},
}
Figure