In partially observable environments, an agent cannot directly observe the true state of the world. Instead, it must maintain a belief state—a continuous probability distribution over all possible states. Planning in this continuous, infinite belief space sounds computationally intractable. However, standard single-agent Partially Observable Markov Decision Processes (POMDPs) remain solvable because their value functions possess a powerful geometric property: they are Piecewise Linear and Convex (PWLC).
A convex value function over the belief simplex means that extreme beliefs (being 100% certain you are in state A or state B) are inherently more valuable than uncertain, high-entropy beliefs (a 50/50 guess). Because the function is piecewise linear, the entire continuous belief space can be perfectly represented or closely approximated by a finite set of hyperplanes ($\alpha$-vectors). To find the optimal action at any given belief, an agent simply evaluates which hyperplane sits on top.
But what happens when we push past the boundaries of standard POMDPs? What if multiple agents are interacting, or what if the goal isn't just to reach a physical destination, but to actively gather information or hide our tracks? A major thread of research focuses on proving that these vital geometric structures—convexity and concavity—are preserved even under these complex extensions, unlocking efficient optimization algorithms for advanced planning problems.
Preserving Convexity in Multi-Agent Settings
In multi-agent environments, planning becomes a moving target. An agent's optimal action depends not only on the physical state, but also on what other agents believe and intend to do. This nested uncertainty threatens to destroy the clean geometric structure of the value function.
Prashant Doshi addressed this challenge within the Interactive POMDP (I-POMDP) framework in A Framework for Optimal Sequential Planning in Multiagent Settings. By modeling finite nested beliefs (e.g., what Agent A thinks Agent B thinks about Agent A), Prashant Doshi proved that the value function maintains its PWLC properties. This mathematical consistency means that multi-agent planning problems do not require entirely new optimization paradigms; instead, established single-agent value iteration techniques can be transferred directly to compute optimal multi-agent policies.
Standard POMDP (PWLC) ----> [Nested Beliefs / Fixed Policies] ----> Multi-Agent POMDP (Preserved PWLC)
└─ Enables Single-Agent Solvers
For Decentralized POMDPs (Dec-POMDPs), where agents must coordinate without central control, Ranjit Nair et al. demonstrated a similar structural preservation in Taming Decentralized POMDPs: Towards Efficient Policy Computation for Multiagent Settings. The authors showed that if the policies of all other agents are held constant, the value function for any individual agent remains PWLC. This insight forms the backbone of the Joint Equilibrium-based Search for Policies (JESP) framework, allowing point-based or exact single-agent solvers to iteratively find local Nash equilibria in decentralized systems over extended horizons.
Belief-Dependent Rewards and Active Sensing
In a standard POMDP, rewards are tied strictly to physical states and actions (e.g., reaching a goal coordinate). However, in "active sensing" or information-gathering tasks, the objective is to reduce uncertainty itself. Here, the reward must depend directly on the belief state (e.g., receiving a high reward for achieving a low-entropy belief).
Mauricio Araya et al. formalized this concept as $\rho$POMDPs in A POMDP Extension with Belief-dependent Rewards. The authors proved that as long as the immediate belief-dependent reward function is convex over the belief simplex, the Bellman backup operation preserves this convexity across the entire planning horizon. Consequently, active sensing problems can be solved using existing point-based optimization algorithms with minimal modification.
This principle was extended to decentralized multi-agent teams by Joni Pajarinen et al. in Information Gathering in Decentralized POMDPs by Policy Graph Improvement and Multi-agent active information gathering in discrete and continuous-state decentralized POMDPs by policy graph improvement.
The authors demonstrated that information-theoretic objectives, such as negative entropy, maintain convexity when mapped to finite-horizon joint value functions. This mathematical preservation allows agents to effectively coordinate without communication by prioritizing transitions toward joint states of higher certainty. By leveraging this underlying convexity, the authors derived computationally efficient lower bounds, making decentralized information gathering tractable in environments an order of magnitude larger than those manageable by previous exact solvers.
The Dual View: Concavity in Trajectory Estimation
While maximizing information gain yields convex value functions, tracking or estimating entire state trajectories often reveals a dual structural property: concavity.
Timothy L Molloy explored this in Active Trajectory Estimation for Partially Observed Markov Decision Processes via Conditional Entropy. Instead of estimating just the current state, the goal was to actively control the system to minimize uncertainty about its entire past path. By reformulating this path-estimation problem as a belief-state MDP, the author proved that the resulting value function is concave with respect to the belief state. This concavity is crucial because it allows practitioners to use standard piecewise-linear function approximations to make the history-dependent problem computationally tractable.
Convex Value Function (Information Gain) Concave Value Function (Trajectory Tracking)
Value Value
^ / ^ .---.
| / | / \
| \ / | / \
| \____/ | / \
+-------------------> +------------------->
Pure Uncertain Pure Uncertain
Belief Belief Belief Belief
In subsequent work, Timothy L Molloy extended this analysis to "smoother entropy" metrics in Smoother Entropy for Active State Trajectory Estimation and Obfuscation in POMDPs. Whether the objective is active estimation (minimizing entropy to track a path) or active obfuscation (maximizing entropy to hide a path from an observer), the derived belief-state expressions yield cost and value functions that maintain strict concavity or convexity. This structural guarantee prevents the optimization landscape from collapsing into non-concave chaos, enabling standard, efficient POMDP solvers to handle both tracking and privacy-preserving tasks.
Exploiting concavity is equally vital in network control and resource allocation. For instance, Fangwen Fu et al. demonstrated in Structure-Aware Stochastic Control for Transmission Scheduling that the post-decision state-value function for wireless transmission scheduling is concave. The authors exploited this structural property to develop low-complexity online learning algorithms, showing that concave functions can be effectively represented and learned, bypassing the curse of dimensionality in dynamic communication channels.
Summary
The core insight uniting these diverse papers is that the geometric structure of the belief-space value function is remarkably resilient. Whether dealing with the nested beliefs of multi-agent systems, the non-traditional rewards of active sensing, or the history-dependence of trajectory estimation, the value function consistently retains either convexity or concavity. Identifying and proving these structural properties is not just a theoretical exercise—it is the exact mechanism that allows researchers to repurpose powerful, scalable single-agent optimization algorithms for highly complex, non-standard control problems.
Key Foundational Work
Taming Decentralized POMDPs: Towards Efficient Policy Computation for Multiagent Settings (2003) — contributed 2 concept elements to this direction.
A Framework for Optimal Sequential Planning in Multiagent Settings (2004) — contributed 2 concept elements to this direction.