Title: A Strong Duality Result for Cooperative Decentralized Constrained POMDPs
The work studies cooperative decentralized constrained POMDPs with asymmetric information. Using an extension of Sion's Minimax theorem for functions with positive infinity and results on weak-convergence of measures, strong duality and existence of a saddle point are established for the setting of infinite-horizon expected total discounted costs when the observations lie in a countable space, the actions are chosen from a finite space, the immediate constraint costs are bounded, and the immediate objective cost is bounded from below. more »« less
Huang, Xiaojun; Xiao, Ming
(, Journal für die reine und angewandte Mathematik (Crelles Journal))
null
(Ed.)
Abstract We give an affirmative solution to a conjecture of Cheng proposed in 1979which asserts that the Bergman metric of a smoothly bounded stronglypseudoconvex domain in {\mathbb{C}^{n},n\geq 2} , is Kähler–Einsteinif and only if the domain is biholomorphic to the ball. We establisha version of the classical Kerner theorem for Stein spaces withisolated singularities which has an immediate application toconstruct a hyperbolic metric over a Stein space with a sphericalboundary.
Cook, Joshua; Rothblum, Ron D.
(, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023))
Megow, Nicole; Smith, Adam
(Ed.)
The celebrated IP = PSPACE Theorem gives an efficient interactive proof for any bounded-space algorithm. In this work we study interactive proofs for non-deterministic bounded space computations. While Savitch’s Theorem shows that nondeterministic bounded-space algorithms can be simulated by deterministic bounded-space algorithms, this simulation has a quadratic overhead. We give interactive protocols for nondeterministic algorithms directly to get faster verifiers. More specifically, for any non-deterministic space S algorithm, we construct an interactive proof in which the verifier runs in time Õ(n+S²). This improves on the best previous bound of Õ(n+S³) and matches the result for deterministic space bounded algorithms, up to polylog(S) factors. We further generalize to alternating bounded space algorithms. For any language L decided by a time T, space S algorithm that uses d alternations, we construct an interactive proof in which the verifier runs in time Õ(n + S log(T) + S d) and the prover runs in time 2^O(S). For d = O(log(T)), this matches the best known interactive proofs for deterministic algorithms, up to polylog(S) factors, and improves on the previous best verifier time for nondeterministic algorithms by a factor of log(T). We also improve the best prior verifier time for unbounded alternations by a factor of S. Using known connections of bounded alternation algorithms to bounded depth circuits, we also obtain faster verifiers for bounded depth circuits with unbounded fan-in.
Doron, Dean; Pyne, Ted; Tell, Roei
(, 56th Annual ACM Symposium on Theory of Computing (STOC 2024))
We provide compelling evidence for the potential of hardness-vs.-randomness approaches to make progress on the long-standing problem of derandomizing space-bounded computation. Our first contribution is a derandomization of bounded-space machines from hardness assumptions for classes of uniform deterministic algorithms, for which strong (but non-matching) lower bounds can be unconditionally proved. We prove one such result for showing that BPL=L “on average”, and another similar result for showing that BPSPACE[O(n)]=DSPACE[O(n)]. Next, we significantly improve the main results of prior works on hardness-vs.-randomness for logspace. As one of our results, we relax the assumptions needed for derandomization with minimal memory footprint (i.e., showing BPSPACE[S]⊆ DSPACE[c · S] for a small constant c), by completely eliminating a cryptographic assumption that was needed in prior work. A key contribution underlying all of our results is non-black-box use of the descriptions of space-bounded Turing machines, when proving hardness-to-randomness results. That is, the crucial point allowing us to prove our results is that we use properties that are specific to space-bounded machines.
Williams, Ashley M.; Hogg, Jennifer A.; Diekfuss, Jed A.; Kendall, Samantha B.; Jenkins, Colton T.; Acocello, Shellie N.; Liang, Yu; Wu, Dalei; Myer, Gregory D.; Wilkerson, Gary B.
(, Journal of Sport Rehabilitation)
Context: An Optimizing Performance through Intrinsic Motivation and Attention for Learning theory-based motor learning intervention delivering autonomy support and enhanced expectancies (EE) shows promise for reducing cognitive-motor dual-task costs, or the relative difference in primary task performance when completed with and without a secondary cognitive task, that facilitate adaptive injury-resistant movement response. The current pilot study sought to determine the effectiveness of an autonomy support versus an EE-enhanced virtual reality motor learning intervention to reduce dual-task costs during single-leg balance. Design: Within-subjects 3 × 3 trial. Methods: Twenty-one male and 24 female participants, between the ages of 18 and 30 years, with no history of concussion, vertigo, lower-extremity surgery, or lower-extremity injuries the previous 6 months, were recruited for training sessions on consecutive days. Training consisted of 5 × 8 single-leg squats on each leg, during which all participants mimicked an avatar through virtual reality goggles. The autonomy support group chose an avatar color, and the EE group received positive kinematic biofeedback. Baseline, immediate, and delayed retention testing consisted of single-leg balancing under single- and dual-task conditions. Mixed-model analysis of variances compared dual-task costs for center of pressure velocity and SD between groups on each limb. Results: On the right side, dual-task costs for anterior–posterior center of pressure mean and SD were reduced in the EE group (mean Δ = −51.40, Cohen d = 0.80 and SD Δ = −66.00%, Cohen d = 0.88) compared with the control group (mean Δ = −22.09, Cohen d = 0.33 and SD Δ = −36.10%, Cohen d = 0.68) from baseline to immediate retention. Conclusions: These findings indicate that EE strategies that can be easily implemented in a clinic or sport setting may be superior to task-irrelevant AS approaches for influencing injury-resistant movement adaptations.
Skyler, S.; Atzmon, D.; Felner, A.; Salzman, O.; Zhang, H.; Koenig, S.; Yeoh, W.; Hernandez, C.
(, Proceedings of the Symposium on Combinatorial Search (SoCS))
There are many settings that extend the basic shortest-path search problem. In Bounded-Cost Search, we are given a constant bound, and the task is to find a solution within the bound. In Bi-Objective Search, each edge is associated with two costs (objectives), and the task is to minimize both objectives. In this paper, we combine both settings into a new setting of Bounded-Cost Bi-Objective Search. We are given two bounds, one for each objective, and the task is to find a solution within these bounds. We provide a scheme for normalizing the two objectives, introduce several algorithms for this new setting and compare them experimentally.
Nouman Khan and Vijay Subramanian. A Strong Duality Result for Cooperative Decentralized Constrained POMDPs. Retrieved from https://par.nsf.gov/biblio/10488315. Proceedings of the IEEE Conference on Decision Control .
Nouman Khan and Vijay Subramanian. A Strong Duality Result for Cooperative Decentralized Constrained POMDPs. Proceedings of the IEEE Conference on Decision Control, (). Retrieved from https://par.nsf.gov/biblio/10488315.
Nouman Khan and Vijay Subramanian.
"A Strong Duality Result for Cooperative Decentralized Constrained POMDPs". Proceedings of the IEEE Conference on Decision Control (). Country unknown/Code not available: IEEE. https://par.nsf.gov/biblio/10488315.
@article{osti_10488315,
place = {Country unknown/Code not available},
title = {A Strong Duality Result for Cooperative Decentralized Constrained POMDPs},
url = {https://par.nsf.gov/biblio/10488315},
abstractNote = {The work studies cooperative decentralized constrained POMDPs with asymmetric information. Using an extension of Sion's Minimax theorem for functions with positive infinity and results on weak-convergence of measures, strong duality and existence of a saddle point are established for the setting of infinite-horizon expected total discounted costs when the observations lie in a countable space, the actions are chosen from a finite space, the immediate constraint costs are bounded, and the immediate objective cost is bounded from below.},
journal = {Proceedings of the IEEE Conference on Decision Control},
publisher = {IEEE},
author = {Nouman Khan and Vijay Subramanian},
}
Warning: Leaving National Science Foundation Website
You are now leaving the National Science Foundation website to go to a non-government website.
Website:
NSF takes no responsibility for and exercises no control over the views expressed or the accuracy of
the information contained on this site. Also be aware that NSF's privacy policy does not apply to this site.
An official website of the United States government
