PaperlayerView exact revision on arXiv

Source-linked AI summary

Decentralized Stochastic Control with Partial History Sharing: A Common Information Approach

Ashutosh Nayyar, Aditya Mahajan, Demosthenis Teneketzis

arXiv:1209.1695v1eess.SYmath.OC

TL;DR

The paper presents a general decentralized stochastic-control model and reformulates the decentralized problem as an equivalent centralized problem for a coordinator. The resulting approach supports structural results for optimal strategies and POMDP-style value-function analysis, while relying on specific shared-memory assumptions.

  • Problem

    The paper investigates decentralized stochastic-control problems in which controllers have different information.

  • Method

    The paper introduces partial history sharing and reformulates the decentralized problem as an equivalent centralized problem from the perspective of a coordinator.

  • Results

    The two systems are equivalent, and the resulting value functions are piecewise linear and concave in the common-information belief.

  • Takeaways & Limitations

    The approach provides structural results for optimal strategies using Markov decision theory.

  • Takeaways & Limitations

    The analysis depends on a specific shared- and local-memory update model; increasing shared memory ensures perfect recall.

Abstract

from arXiv · show

A general model of decentralized stochastic control called partial history sharing information structure is presented. In this model, at each step the controllers share part of their observation and control history with each other. This general model subsumes several existing models of information sharing as special cases. Based on the information commonly known to all the controllers, the decentralized problem is reformulated as an equivalent centralized problem from the perspective of a coordinator. The coordinator knows the common information and select prescriptions that map each controller's local information to its control actions. The optimal control problem at the coordinator is shown to be a partially observable Markov decision process (POMDP) which is solved using techniques from Markov decision theory. This approach provides (a) structural results for optimal strategies, and (b) a dynamic program for obtaining optimal strategies for all controllers in the original decentralized problem. Thus, this approach unifies the various ad-hoc approaches taken in the literature. In addition, the structural results on optimal control strategies obtained by the proposed approach cannot be obtained by the existing generic approach (the person-by-person approach) for obtaining structural results in decentralized problems; and the dynamic program obtained by the proposed approach is simpler than that obtained by the existing generic approach (the designer's approach) for obtaining dynamic programs in decentralized problems.

I. INTRODUCTION

The paper introduces partial history sharing as a general decentralized stochastic-control model and uses common information to reformulate it through a coordinator. The resulting POMDP-based approach yields structural results and a dynamic program while differing from existing generic approaches.

  • Decentralized stochastic-control problems involve multiple decision makers with different information, so centralized stochastic-control techniques cannot be directly applied.
  • Existing person-by-person methods derive best-response structure and can identify globally optimal strategy structure, but iterative best-response procedures generally yield only person-by-person optimal strategies.
  • The designer’s approach models decentralized planning as open-loop stochastic control, with each dynamic-programming step becoming a functional optimization problem.
  • Partial history sharing lets controllers sequentially share part of their past observations and controls through shared memory while retaining perfect recall of common information.
  • The common-information approach reformulates the decentralized problem as an equivalent centralized coordinator problem, where prescriptions map local information to actions and the coordinator’s problem is a POMDP.
  • The approach provides structural results and a dynamic program for optimal controller strategies, unifying prior ad-hoc methods; its structural results and dynamic-programming decomposition improve on the generic approaches.

A. Common Information Approach for a Static Team Problem

The static-team example shows how common information reduces decentralized strategy search by replacing direct controller strategies with coordinator-selected prescriptions. The paper extends this idea to dynamical systems and develops a general common-information methodology.

  • A. Common Information Approach for a Static Team Problem: In the static team, controllers observe common information Y* alongside local observations and choose actions through their respective control strategies.
  • A. Common Information Approach for a Static Team Problem: A coordinator observes Y* and selects prescriptions Γi mapping each controller’s local observation Yi to its action Ui.
  • A. Common Information Approach for a Static Team Problem: Choosing original control strategies is equivalent to choosing a coordination strategy, making the optimization problem centralized with the coordinator as the sole decision maker.
  • B. Contributions of the Paper: The paper extends the coordinator idea to dynamical decentralized systems by converting them into centralized stochastic-control problems, particularly POMDPs, with dynamic-programming decompositions.
  • B. Contributions of the Paper: The general model covers several existing information-sharing models and establishes both a structural property of optimal strategies and a dynamic-programming decomposition.

D. Organization

The paper defines a discrete-time decentralized stochastic control system in which controllers use local observations, local memories, and shared memories. It formulates the objective as minimizing expected total cost over a finite horizon.

  • The Dynamic System: The system has n controllers, evolves in discrete time over horizon T, and includes a state, individual actions, and a joint action vector.The initial state is probabilistically specified and the system evolves with independent primitive random variables.
  • Information Structure: Each controller accesses a current local observation, a local memory containing selected past information, and a shared memory containing selected histories from all controllers.The shared memory is a subset of past local observations and control actions, while local memories are updated according to the model’s protocols.
  • Control Strategies: Controllers choose actions as functions of their available local information, and their control laws collectively define the system’s control strategy.The available information includes the controller’s local data and the shared memory.
  • Memory Updates: After acting, controllers send protocol-selected portions of local information to shared memory and update their local memories using a pre-specified protocol.The shared-memory contents are nested over time, and Figure 1 specifies the ordering of observations, actions, and memory updates.
  • Optimization Problem: The partial history sharing information structure is optimized by finding a control strategy that minimizes expected total cost over the horizon.The objective is the expected sum of instantaneous costs induced by the chosen controller strategies.

B. Special Cases: The Models

The partial history sharing model contains delayed, periodic, control-only, finite-memory, and asymmetric sharing structures as special cases. These cases arise from different pre-specified protocols for updating local and shared memories.

  • Delayed Sharing: Delayed sharing results when the shared memory contains observations and actions up to t−s, so information becomes available to every other controller after s steps.This protocol recovers the delayed sharing structure considered in prior work.
  • Delayed State Sharing: Delayed state sharing is obtained when the system state is an n-dimensional vector and each controller observes its corresponding state component.Under these assumptions, the complete state vector becomes available to all controllers after the sharing delay.
  • Periodic Sharing: Periodic sharing results when controllers update shared memory only at times separated by a fixed period s, sharing the intervening observation and action history.Between update times, the shared memory remains fixed and controllers send no new data.
  • Control Sharing: Control sharing is the special case in which shared memory contains past control actions, making each controller’s actions available to others after one time step.This protocol corresponds to the control sharing structure considered in prior work.
  • Other Special Cases: The model also includes systems with no shared data and asymmetric sharing protocols in which controllers can transmit different fixed-delay observation histories.Thus, identical sharing protocols across controllers are not required.

III. MAIN RESULTS

The paper converts the decentralized control problem into an equivalent centralized problem viewed through a coordinator that observes common information and selects local-action prescriptions. The coordinated problem is a POMDP, yielding structural results and a dynamic-programming decomposition that can be translated back to the original system.

  • Structural Results and Dynamic Programming: An optimal coordination strategy has a structure characterized through the POMDP formulation, and a dynamic program is provided to find it.The paper explicitly identifies these as the main results for the coordinated system.
  • Centralized Reformulation: The proposed approach addresses the decentralized stochastic control problem with partial information sharing by constructing an equivalent centralized stochastic control problem.The proof proceeds by solving the centralized formulation and translating its results back to the decentralized model.
  • Coordinator: The coordinator observes only shared memory and selects prescriptions that map each controller’s local information to its control action.Local memories and observations remain unavailable to the coordinator, while prescriptions are communicated to the controllers.
  • Equivalence: Strategies in the coordinated and original systems are mutually implementable with the same expected total cost, establishing equivalence between the two systems.The structural results and dynamic-programming decomposition can therefore be translated to the original decentralized problem.
  • POMDP Formulation: The coordinated system is shown to be a partially observable Markov decision process with state {Xt, Yt, Mt}, observation Ot := Zt−1, and action At := Γt.The lemma establishes the required state transition, observation, and cost structure for the POMDP representation.

Stage 3: Structural result and dynamic program for the coordinated system

The coordinated problem is formulated as a POMDP whose information state is the common-information belief, enabling structural optimality results and dynamic programming.

  • Structural result: The coordinated system is a POMDP, so its optimal coordination strategy can be characterized through partially observable control methods.The coordinator's information state is the conditional distribution Πt on (Xt, Yt, Mt) given Ct.
  • Structural result: There is no loss of optimality in restricting coordination strategies to the specified structural form.The restriction is formalized in Proposition 1 and underlies the subsequent dynamic program.
  • Dynamic program: The coordinator's dynamic program selects prescriptions by minimizing the current cost plus the expected continuation value under the belief update.At each information state π, the minimizing prescription supplies the coordinator's optimal action for the controllers.
  • Dynamic program: POMDP computational algorithms can be used to solve the coordinator's dynamic program.This follows from identifying the coordinated system as a POMDP.
  • Equivalence to the basic model: The coordinated system is equivalent to the basic decentralized model: every basic control strategy maps to a coordination strategy with the same cost, and conversely.Proposition 3 states both directions of the equivalence and preserves the objective value.
  • Dynamic program: Backward induction evaluates optimal partial control laws for every realization of the common information state.Theorem 3 defines the value functions and selects each controller's minimizing partial control law.

A. Comparison with Person by Person and Designer Approaches

The common-information approach yields a jointly valid structural result that generic person-by-person analysis cannot obtain, while producing a simpler dynamic program than the designer's approach.

  • Comparison with Person by Person: The structural result cannot be obtained by the person-by-person approach because arbitrary fixed strategies of other controllers can invalidate the proposed form for one controller.A controller may need the entire common information to predict another controller's actions under arbitrary strategies.
  • Comparison with Person by Person: The common-information approach proves that all controllers can jointly use the identified structural strategy form without loss of optimality.This joint result avoids the person-by-person failure described for arbitrary strategies.
  • Comparison with Designer: The resulting dynamic-programming decomposition is simpler than decompositions obtained through the designer's approach.The designer's approach treats the problem as open-loop centralized planning, whereas this approach uses closed-loop coordination.
  • Comparison with Designer: Partial control laws form a smaller space than full control laws, and the reduction is strict when common information is non-empty.This smaller decision space explains the simpler decomposition relative to the designer's approach.
  • Example: When all controllers receive a common observation, the common-information state reduces to P(Xt|Y com 1:t), matching centralized stochastic control.The corresponding designer information state is described as much more complicated.
  • Special cases: For delayed sharing, delayed state sharing, periodic sharing, and control sharing, the framework provides structural strategies and analogous dynamic programs.These information-sharing models are treated as special cases of the generalized framework.

3) Periodic Sharing Information Structure:

For periodic sharing, optimal strategies depend on recent unsynchronized histories and the common-information state, with a dynamic program selecting partial control laws at every step.

  • 3) Periodic Sharing Information Structure:: Periodic sharing admits optimal control strategies using each controller's recent local history together with the common information state Πt.For ks < t ≤ (k + 1)s, the strategy uses the local history from ks+1:t−1.
  • 3) Periodic Sharing Information Structure:: The periodic-sharing strategies can be obtained through a dynamic program analogous to the general decomposition.The framework therefore supplies both the structural form and a computational procedure.
  • 3) Periodic Sharing Information Structure:: Unlike an earlier decomposition performed only at information-sharing times, this dynamic program chooses partial control laws at every step.The finer decomposition operates between sharing instants rather than selecting all intervening laws at once.
  • Related special cases: The framework also yields analogous structural strategies and dynamic programs for control sharing and finite-memory information structures.For the finite-memory case, the common information state is an unconditional probability because common information is empty.
  • Related special cases: In the finite-memory special case, the structural result is redundant because all control laws already have the stated form, although the dynamic program still provides a procedure to find them.The redundancy concerns the structural restriction, not the availability of the computational procedure.
  • Alternative common-information state: An alternative common-information state can restate the structural and dynamic-programming results while removing Yt from the original state definition.The alternative formulation is conceptually equivalent to the original results and extends the corresponding corollaries.

B. Generalization of the Model

The partial-history-sharing methodology extends to settings with common observations and coupled subsystems, retaining structural results and dynamic-programming decompositions under the stated model assumptions.

  • B. Generalization of the Model: The methodology relies on shared memory being common to all controllers and can be modified when current observations are also commonly available.The paper states that such cases can be included by an easy modification of the general methodology.
  • B. Generalization of the Model: Under the generalized assumptions, the observation process analysis yields structural results and dynamic-programming decompositions analogous to Theorems 2 and 3.The common-information state is redefined for the generalized model.
  • Common-observation special case: When controllers have identical information consisting only of a common observation history, the resulting dynamic program coincides with centralized stochastic control.A single controller in the centralized formulation chooses all actions.
  • Coupled subsystems: The coupled-subsystems model uses a shared global component and local subsystem states, with control sharing and independent noise processes specified by the model.The system state is an (n+1)-dimensional vector, and local subsystem states evolve under their corresponding dynamics.
  • Coupled subsystems: For coupled subsystems with control sharing, restricting controllers to no local memory incurs no loss of optimality, and Theorems 1 and 2 apply.The restriction is Mt = ∅.
  • Coupled subsystems: In the coupled-subsystems setting, local states are conditionally independent given the shared global state and past controls, yielding a product of marginal distributions.This conditional factorization supports the specialized information-state representation.

3) Broadcast information structure:

The broadcast information structure is a special case in which common observations are shared, local observations remain distinct, and no additional data enters shared memory. The general results yield optimal time-invariant strategies for the infinite-horizon formulation under time-invariant spaces and time-homogeneous dynamics.

  • The system has a central node and peripheral nodes, with state Xt=(X1t,…,Xnt) and subsystem-specific local states.
  • At each time, all controllers observe X1t as common information, while controller i>2 observes its local component Xit.
  • No controller sends additional data, so shared memory contains only the history of common observations.
  • The peripheral state components are conditionally independent given the central state history, making their joint distribution a product of marginal distributions.
  • For infinite-horizon discounted cost, the coordinated system is equivalent to a POMDP, supporting known POMDP results and an optimal time-invariant control strategy.
  • The infinite-horizon extension requires time-invariant state, observation, and action spaces plus time-homogeneous dynamics and observation equations; control sharing is an exception when local-memory sets grow with time.

VI. DISCUSSION AND CONCLUSIONS

The discussion frames common information as a consistent basis for coordinating decentralized controllers and reformulates their problem through a coordinator as a POMDP. The approach yields structural and computational results, but depends on specific memory-update assumptions and leaves value-function simplification as future work.

  • Different controllers’ beliefs and predictions of future costs need not be consistent because they possess different information.
  • Shared data creates common knowledge, whose beliefs are consistent across controllers and can serve as a sufficient statistic.
  • A coordinator knows the common information and selects partial control laws, converting the problem into a POMDP with a state containing system state and local information.
  • The shared-memory model’s increasing-memory assumption provides perfect recall; losing past shared contents would invalidate the common-information-state update and Theorems 2 and 3.
  • The local-memory update must preserve St={Xt,Yt,Mt} as a coordinator state; otherwise Ct must be added, causing a state space that grows with time.
  • The dynamic program is essentially a POMDP dynamic program, with value functions that are piecewise linear and concave in πt.
  • Future work includes identifying special cases and value-function properties that simplify the structural result or reduce computational burden.

APPENDIX B

The appendix establishes equivalence between the paper’s decentralized formulation and a coordinated formulation, then relates the partial history sharing model to the common observation model. It also specifies system variables, memories, controls, and costs for these representations.

  • A decentralized control strategy can be converted into a coordination strategy that produces identical states, observations, controls, and memories.
  • Because the induced trajectories coincide, the expected costs satisfy J(g1:n)=Ĵ(d).
  • The paper calls its information structure partial history sharing (PHS) and compares it with the common observation (CO) model.
  • The PHS model is shown to be a special case of the CO model, while the CO model is represented as a PHS model by splitting time so only one controller acts at each time.
  • The appendix defines system state, common and private observations, local memories, controls, dynamics, observation equations, instantaneous costs, and total expected cost.
  • The time-splitting construction introduces variables over τ=1,…,nT, assigning the original common observation at τ=tn+1 and empty shared observations thereafter.
Loading 1209.1695v1…