Active Inference via Incentive Design: Eliciting Divergent Behaviors under Partial Observability

The gist: We present a method for active inference with partial observations in stochastic systems through incentive design, also known as the leader-follower game.

Problem Formulation

The core problem involves a leader agent aiming to infer a follower agent’s type given a finite set of possible types, where different types differ in their dynamical model, the reward function, or both<ref:2502.07065#pg2> The leader can partially observe a follower’s behavior in the stochastic system modeled as a Markov decision process, in which the follower takes an optimal policy to maximize a total reward<ref:2502.07065#pg5>. The leader's goal is to identify which follower is currently interacting with the system through imperfect and noisy observations<ref:2502.07065#pg2>. To improve inference accuracy within a finite time horizon, the leader strategically designs an incentive policy to offer side payments (additional rewards) within the environment, influencing the followers’ best responses<ref:2502.07065#pg2>. These incentives incur a direct cost to the leader’s own payoff<ref:2502.07065#pg2>.

Incentive Design and Objective

The problem is formulated as a special class of leader-follower games where the leader’s objective is to balance the information gain and cost of incentive design<ref:2502.07065#pg4>. The information gain is measured by the entropy of the estimated follower’s type given partial observations<ref:2502.07065#pg4>. The problem is framed as a bi-level optimization problem where the leader minimizes uncertainty while balancing against the cost of side payments<ref:2502.07065#pg5>. Specifically, Problem 2 states that the objective is to minimize H(T O0:T,M(π⋆ (x))) + h(x) subject to π⋆ i(x) ∈ argmax π∈Π Vi(µi, Ri(x), π), ∀i ∈ T<ref:2502.07065#pg5>.

Reduction to Single-Level Optimization

The bi-level optimization problem can be reduced to a single-level optimization problem by leveraging the entropy-regularized MDP solution<ref:2502.07065#pg4>. The optimal policy of the entropy-regularized MDP is uniquely defined by πQ⋆(R) where Q⋆(R) is viewed as a vector in RS×A and πQ⋆(Ri(x)) is the entropy-regularized optimal policy<ref:2502.07065#pg4>. This reduction allows the problem to be solved with gradient descent methods<ref:2502.07065#pg4>. The objective function is defined as J(x):= J1(Q⋆(R(x))) + h(x)<ref:2502.07065#pg5>.

Gradient Computation and Implementation

The gradient of the objective function with respect to the side payment x is given by DJ(x) = DJ1(Q⋆ (R(x)))·DQ⋆ (R(x))·DR(x)+Dh(x)<ref:2502.07065#pg5>. The computation of DQ⋆ (R(x)) is shown to be a block diagonal matrix, and the partial derivative can be computed using any method for solving the Bellman equation<ref:2502.07065#pg5>. Observable operators within the hidden Markov model (HMM) are utilized to compute the necessary gradients and demonstrate effectiveness through experiments in stochastic grid world environments<ref:2502.07065#pg5>.

Experimental Validation

Experiments validate the accuracy and effectiveness of the proposed methods through two case studies in a fire rescue task and a behavior comparison task<ref:2502.07065#pg5>. In Example 1, increasing the side payment to be higher than 0.291 will improve the inference accuracy, but at too much cost for the leader<ref:2502.07065#pg5>. The results show that as the side payment increases and converges to the optimal value of 0.5, the posterior Pˆθ(T = iY) decreases to about 0.15, while Pˆθ(T = 2Y) increases to about 0.85<ref:2502.07065#pg5>. These experimental results validate the accuracy and effectiveness of our proposed methods<ref:2502.07065#pg5>.

Conclusion

In this paper, we introduced a class of active inference problems through incentive design and developed a bi-level optimization method to solve a locally optimal solution for the leader’s incentive policy<ref:2502.07065#pg5>. Our approach uses conditional entropy to measure uncertainty about followers’ types from the leader’s partial observations and consider an incentive design with an objective to balance information gain and incentive cost<ref:2502.07065#pg5>. Future work could explore several directions: 1) Integrating active inference with adaptive incentive design for personalized systems; 2) Extending the proposed method from model-based to model-free setting, where the leader only has access to collected data from different followers in the past interactions<ref:2502.07065#pg5>.

--- Page 1 ---

Active Inference through Incentive Design in Markov Decision Processes

Xinyi Wei∗1, Chongyang Shi∗1, Shuo Han2, Ahmed H. Hemida3, Charles A. Kamhoua3, Jie Fu1

Abstract

We present a method for active inference with partial observations in stochastic systems through incentive design, also known as the leader-follower game<ref:2502.07065#pg2> Consider a leader agent who aims to infer a follower agent’s type given a finite set of possible types<ref:2502.07065#pg2>. Different types of followers differ in either the dynamical model, the reward function, or both<ref:2502.07065#pg2>. We assume the leader can partially observe a follower’s behavior in the stochastic system modeled as a Markov decision process, in which the follower takes an optimal policy to maximize a total reward<ref:2502.07065#pg2>. To improve inference accuracy and efficiency, the leader can offer side payments (incentives) to the followers such that different types of them, under the incentive design, can exhibit diverging behaviors that facilitate the leader’s inference task<ref:2502.07065#pg2>. We show the problem of active inference through incentive design can be formulated as a special class of leader-follower games, where the leader’s objective is to balance the information gain and cost of incentive design<ref:2502.07065#pg2>. The information gain is measured by the entropy of the estimated follower’s type given partial observations<ref:2502.07065#pg2>. Furthermore, we demonstrate that this problem can be solved by reducing a single-level optimization through softmax temporal consistency between followers’ policies and value functions<ref:2502.07065#pg2>. This reduction allows us to develop an efficient gradient-based algorithm<ref:2502.07065#pg2>. We utilize observable operators in the hidden Markov model (HMM) to compute the necessary gradients and demonstrate the effectiveness of our approach through experiments in stochastic grid world environments<ref:2502.07065#pg2>.

--- Page 2 ---

decision-making processes are categorized into Nash equilibrium strategies and myopic update rules<ref:2502.07065#pg2> They develop an algorithm that the principal can employ to learn the agents’ decision-making processes while simultaneously designing incentives to change their response to one that is more desirable<ref:2502.07065#pg2>. Adaptive incentive design in [Ma et al., 2024] introduces gradient-ascent algorithms to compute the leader’s optimal incentive strategy, despite the lack of knowledge about the follower’s reward function<ref:2502.07065#pg2>. While adaptive incentive design focuses on dynamically adapting the leader’s policy based on the follower’s response, our work examines a different problem: incentive design that supports inference tasks under partial observability<ref:2502.07065#pg2>. Specifically, we assume the leader has a prior distribution over potential follower types and aims to reduce uncertainty in the posterior distribution of these types based on limited observations<ref:2502.07065#pg2>. To achieve this, we propose an information-theoretic objective for the leader, rather than defining the leader’s value in terms of cumulative discounted rewards<ref:2502.07065#pg2>. Since information-theoretic measures cannot be directly expressed as cumulative rewards, we develop novel solutions for this class of incentive design problems<ref:2502.07065#pg2>.

--- Page 3 ---

Incentive design [Bolton and Dewatripont, 2005], is also referred to as the principal-agent or leader-follower game<ref:2502.07065#pg2>. Ho et al.

1. Adaptive Incentive Design for Personalized Systems: The system can dynamically adjust side payments to followers based on real-time leader observations to tailor their reward functions, such as surge pricing or completion bonuses, directly improving the accuracy and efficiency of inferring user preferences in ride-sharing platforms.

2. Intent Inference for AI Alignment: The improved AI system can infer human intentions or capabilities by strategically designing incentives that cause followers to exhibit diverging behaviors, ensuring the AI tailors decisions for specific user groups and avoids unintended or harmful behaviors.

3. Information-Theoretic Uncertainty Minimization: The system will minimize uncertainty about a follower's type by optimizing the conditional Shannon entropy, which is quantified as H(T Y,M(π⋆(x))) in the bi-level optimization problem, balancing information gain against the cost of side payments.

4. Gradient-Based Inference Optimization: The solution employs a single-level optimization approach derived from reducing the bi-level problem using entropy regularization, allowing for efficient gradient descent methods to find stationary points for the incentive policy parameter theta.

5. Efficient Gradient Computation via Observable Operators: The system computes necessary gradients using observable operators within Hidden Markov Models, such as Atheta o [i, j], enabling more accurate and computationally efficient gradient computation for the partially observable follower dynamics.