PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Control Strategies in Delayed Sharing Information Structures

Ashutosh Nayyar, Aditya Mahajan, Demosthenis Teneketzis

arXiv:1002.4172v1cs.OH

TL;DR

Decentralized control with delayed sharing faces growing data and lacks the separation available in centralized control. The paper derives two structural results for optimal strategies, including delayed separation, and reports agreement with Witsenhausen’s conjecture when n = 1.

  • Problem

    Growing decentralized data expands control-law domains and complicates both searching for and implementing strategies, while analogous separation results are not known for general decentralized systems.

    Source: §1.1 · pp. 1–2

  • Method

    The paper derives two structural results for delayed-sharing control by formulating an alternative problem from a coordinator’s perspective.

    Source: §1.4 · p. 4, §6 · p. 17

  • Results

    The two results characterize optimal control laws with time-invariant domains, and the second separates the information state from laws before t−n+1; for n = 1, the result coincides with Witsenhausen’s conjecture.

    Source: §1.4 · p. 5, Delay n = 1 · p. 15, §6 · p. 17

  • Takeaways & Limitations

    The authors believe the coordinator-based alternative-problem approach is also useful for general decentralized control problems.

    Source: §6 · p. 17

    The authors believe Kurtaran’s proof is incomplete and report that they have neither corrected it nor found a counterexample to his result.

    Source: §1.4 · p. 5, §5 · p. 17

Abstract

from arXiv · show

The $n$-step delayed sharing information structure is investigated. This information structure comprises of $K$ controllers that share their information with a delay of $n$ time steps. This information structure is a link between the classical information structure, where information is shared perfectly between the controllers, and a non-classical information structure, where there is no "lateral" sharing of information among the controllers. Structural results for optimal control strategies for systems with such information structures are presented. A sequential methodology for finding the optimal strategies is also derived. The solution approach provides an insight for identifying structural results and sequential decomposition for general decentralized stochastic control problems.

1. Introduction

The introduction motivates structural compression for decentralized control with delayed sharing, then presents two optimal-strategy structural results and a partial separation property. It also positions these results against earlier proposals and describes the model and notation.

1.1. Motivation

  • Growing data makes decentralized control-law domains expand over time, increasing the strategy search space and complicating implementation; general decentralized structural-result methods are not known.Centralized control can instead use an information state in a time-invariant space, but analogous separation results are not known for general decentralized systems.Source: §1.1 · pp. 1–2

1.3. Model

  • With n-step delayed sharing, each station knows other stations’ observations and actions from n steps earlier, alongside its own available information.Stations have perfect recall.Source: §1.1 · p. 2, §1.3 · p. 3

1.4. The structural results

  • The results agree with Witsenhausen’s conjecture for n = 1, differ from Kurtaran’s proposal for n > 1, and the authors believe Kurtaran’s proof is incomplete.The authors report that they have neither completed that proof nor found a counterexample.Source: §1.1 · p. 2, §1.4 · pp. 4–5

1.2. Notation

  • The notation uses uppercase random-variable names, lowercase realizations, and X_a:b for a vector of consecutive variables; the exposition assumes finite sets.Probability and expectation may depend on the chosen collection of functions.Source: §1.2 · p. 2

1.4. The structural results

  • Both structural results restrict optimal strategies to time-invariant domains, and the second separates information states from control-law choices before t−n+1.The paper calls this delayed separation.Source: §1.4 · pp. 4–5
  • The first result depends on prior control laws, whereas the second represents common information using a belief and partial functions of recent control laws.The second result’s partial functions do not depend on laws used before t−n+1.Source: §1.4 · pp. 4–5

2. Proof of the first structural result

The proof replaces the decentralized problem with an equivalent coordinator problem, then uses that formulation to derive structural results. The two-controller proof proceeds through coordinator formulation, equivalence, state identification, and an MDP.

2.1. Two Controller system (K = 2)

  • The proof proceeds by formulating a coordinator problem, showing equivalence to the original problem, identifying a sufficient state, and converting the problem to an MDP.The stages are given for two controllers, with extension to general K noted as the purpose of the section.Source: §2.1 · p. 5

Stage 1

  • The coordinator observes shared information and selects partial functions mapping each controller’s private information to its action.It informs the controllers of those functions, which they evaluate to generate their actions.Source: Stage 1 · p. 6

Stage 2

  • The coordinator problem and the original problem are equivalent: either strategy can be implemented in the other with the same expected cost.Under the corresponding designs, the system states, observations, and control actions are identical.Source: Stage 2 · p. 7

Stage 3

The coordinator’s problem is represented using a state sufficient for its input-output mapping and then an information state. This yields a controlled Markov formulation and an optimal coordination strategy depending only on that information state.

Proposition 1

  • Proposition 1 establishes S_t as sufficient for the coordinator’s input-output mapping, with next state, output, and instantaneous cost expressible through current state and inputs.The three properties respectively concern next state, current output, and instantaneous cost.Source: Stage 4 · p. 8, Proposition 1 · p. 8, Stage 3 · p. 8

Stage 4

  • The information-state process Π_t is a controlled Markov chain with the coordinator’s partial functions as control actions.Its evolution is described by strategy-independent functions, and the initial information state is fixed by the primitive-variable distribution.Source: Stage 4 · p. 9
  • Without loss of optimality, the coordinator’s strategy can be restricted to a function of the current information state Π_t.The result follows by treating the coordinator’s problem as a Markov decision problem.Source: Stage 4 · p. 9
  • For two controllers, the structural result is implemented in the original problem by having both controllers use the shared Π_t to select their partial functions.At the next time step, the controllers share the new common observations and can update Π.Source: Stage 4 · p. 10

2.2. Extension to General K

The structural result extends to general K, and the coordinator’s problem admits a dynamic program for finding optimal strategies. The paper also relates its one-step-delay result to Witsenhausen’s structural result.

2.2. Extension to General K

  • The two-controller structural result extends to general K using partial functions for each controller and analogous state and Markov-chain results.The coordinator’s sufficient state includes the plant state and the controllers’ private information.Source: §2.2 · p. 10

2.3. Sequential Decomposition

  • The optimal coordination strategy can be found by dynamic programming, and the corresponding strategy is optimal for the original problem.The dynamic program also extends to general K.Source: §2.3 · p. 11

2.4. Computational Aspects

  • The coordinator’s problem can be viewed as a POMDP, with S_t as the partially observed state and Π_t as its belief information state.Its value functions are piecewise linear and concave in Π_t, a characterization the paper notes can support computationally efficient POMDP algorithms.Source: §2.4 · p. 11

2.5. One-step Delay

  • For n = 1, the paper’s structural result is equivalent to Witsenhausen’s result because Π_t corresponds one-to-one with the belief P(X_{t−1} | Δ_t).That belief is a marginal of Π_t, and Π_t can also be recovered from it.Source: §2.5 · p. 12

3. Proof of the second structural result

The second structural result uses an information state that combines a belief with partial functions representing earlier control laws. It yields a coordinator MDP and distinguishes the result from Witsenhausen’s conjecture for delays greater than one.

3.1. Two controller system (K = 2)

  • For two controllers, the coordinator’s information state is a function of Θ_t and the partial functions r^1_t and r^2_t, yielding an MDP formulation and an optimal coordination strategy.The corresponding strategy can be found by dynamic programming and implemented optimally in the original problem.Source: §3.1 · pp. 13–14
  • The second structural result extends to K controllers by using (Θ_t, r^{1:K}_t) as the coordinator’s information state.The paper identifies Θ_t as strategy-independent and updated using common observations.Source: §3.1 · pp. 13–14

3.2. Comparison to Witsenhausen’s Result

  • For n > 1, unlike Witsenhausen’s conjecture, optimal control laws use partial functions of earlier control laws to predict other controllers’ actions; for n = 1, the results coincide.The partial functions depend on the previous n−1 control laws, so the information state is separated from control laws before time t−n+1.Source: Delay n > 1 · p. 15, Delay n = 1 · p. 15

4. A Special Case of Delayed Sharing Information Structure

The section specializes delayed sharing to coupled subsystems with local state observations and describes an optimal coordination strategy for that setting. It also relates the structural result and sequential decomposition to prior work.

4. A Special Case of Delayed Sharing Information Structure

  • With n-step delayed exchange of observations and actions, coupled subsystems whose controllers observe their own states form a special case of delayed sharing.The section refers to further model assumptions, but their full statements are not given in these passages.Source: §4 · p. 15
  • For the model considered in, the first structural result and sequential decomposition apply, while the second structural result simplifies because the belief is concentrated on the true X_t−n.The belief assigns probability 1 to the true realization of X_t−n and 0 otherwise.Source: §4 · pp. 15–16
  • Corollary 2 states that, under Assumptions 1 and 2, an optimal coordination strategy has the specified form.The displayed strategy is not described in the supplied prose.Source: §4 · p. 16
  • The section says the optimal coordination strategy can be found by a dynamic program, and compares its structural result and sequential decomposition to Theorem 1 of.The passages introduce the program and identify it as analogous to Theorem 1 of, without supplying its full recurrence.Source: §4 · p. 16

5. Kurtaran’s Separation Result

For two controllers with a two-step delay, the paper challenges Kurtaran’s separation argument: the proposed information-state update retains dependence on common information, undermining the cited dynamic-programming proof. The authors leave Kurtaran’s result unresolved.

5. Kurtaran’s Separation Result

  • The analysis restricts to two controllers and delay n = 2 to examine Kurtaran’s proposed structural result.Kurtaran’s result proves the terminal-time case and invokes a dynamic-programming argument for earlier times, which the authors dispute.Source: §5 · p. 16
  • The proposed update cannot be established by the authors’ argument because the first two terms retain dependence on δ_t, so ϕ_t+1 still depends on δ_t.The authors state this dependence is not an artifact of the chain-rule ordering.Source: §5 · p. 17
  • Consequently, the dynamic-programming argument in does not establish Kurtaran’s result, and the authors report no corrected proof or counterexample.They therefore characterize the proof as incomplete without resolving whether the result itself is correct.Source: §5 · p. 17

6. Conclusion

The paper establishes two structural results for n-step delayed sharing, including a partial separation result, using a coordinator formulation. The results agree with Witsenhausen’s conjecture for n = 1.

6. Conclusion

  • Both structural results characterize optimal control laws with time-invariant domains.Source: §6 · p. 17
  • The second result gives partial separation: the information state at time t is separated from choices of control laws before time t − n + 1.Source: §6 · p. 17
  • For n = 1, both structural results agree with Witsenhausen’s conjecture.Source: §6 · p. 17
  • The derivation formulates an alternative problem from a coordinator’s point of view, and the authors suggest this approach may also be useful for general decentralized control problems, as illustrated by and.Source: §6 · p. 17

A. Proof of Proposition 2

The proof develops the coordinator’s information-state update by fixing its strategy and a realization of common information, then using the system’s sequential generation of variables.

A. Proof of Proposition 2

  • The proof fixes a coordinator strategy and a realization of common information, then identifies the corresponding choices of partial functions through time t.Source: A. Proof of Proposition 2 · p. 18
  • It expresses the next information state using Proposition 1 and the decomposition δ_t+1 = (δ_t, z_t+1).Source: A. Proof of Proposition 2 · p. 18
  • The sequential order in which system variables are generated yields an update involving F_t+1, defined by equations (62)–(65).Source: A. Proof of Proposition 2 · p. 18

B. Proof of Proposition 3

The proof fixes a coordinator strategy and a realization of common information, then develops the argument through probability expressions and cited propositions.

B. Proof of Proposition 3

C. Piecewise linearity and concavity of value function

The section establishes piecewise linearity and concavity at the terminal time, then proves concavity of the value function inductively.

C. Piecewise linearity and concavity of value function

D. Proof of Proposition 4

The proof characterizes the coordinator's belief through the current belief state and private information, and establishes a recursive update for the belief state.

D. Proof of Proposition 4

Loading 1002.4172v1…