Pith. sign in

REVIEW 2 major objections 4 minor 95 references

Provable Partially Observable Reinforcement Learning with Privileged Information

T0 review · 2 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read On $\gamma$-observable partially observable Markov decision processes, training with access to the true underlying states reduces the sample complexity of learning a near-optimal policy from quasi-polynomial to polynomial, while…

desk verdict A substantial theory paper that gives the first polynomial-sample explanation for teacher-student and asymmetric actor-critic with privileged information, but the load-bearing filter-stability step in Theorem 5.3 deserves scrutiny before you rely on it. read the letter →

arxiv 2412.00985 v3 pith:3IIWRSHH submitted 2024-12-01 cs.LG

Yang Cai , Xiangyu Liu , Argyris Oikonomou , Kaiqing Zhang This is my paper · ORCID
classification cs.LG MSC 68Q3268T05
keywords partiallyobservableMarkovdecisionprocessprivilegedinformationexpertdistillationasymmetricactor-criticbeliefstatelearninggamma-observabilityfilterstabilitycentralizedtrainingwithdecentralizedexecution
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tries to establish that two paradigms practitioners actually use — expert distillation (teacher-student learning) and asymmetric actor-critic — can be provably sample- and computationally efficient for partially observable RL when training has privileged access to the true states. The first claim is a caution: distillation can lose a constant fraction of optimal value even on $\gamma$-observable POMDPs, but becomes both sample- and time-polynomial under a new 'deterministic filter condition' (the belief always collapses to a single state), a condition weaker than known tractable classes and covering decodable POMDPs with unknown decoding length. The second and main claim is positive for the harder $\gamma$-observable class: a belief-weighted asymmetric actor-critic with a new belief-learning oracle learns an $\epsilon$-optimal policy with polynomial episodes and quasi-polynomial time — improving the quasi-polynomial sample complexity of prior no-intractable-oracle algorithms to polynomial, and beating vanilla actor-critic, which the paper proves is sample-super-polynomial. If correct, these results say that simulator or sensor access to states during training is not just practically useful but provably converts some of the hardest learnable POMDPs into polynomial-sample problems, without oracle shortcuts.

What carries the argument

The argument runs on three objects. (1) $\gamma$-observability (Assumption 2.5): each emission matrix $O_h$ must separate any two belief distributions by at least $\gamma$ in $\ell^1$ norm; this is the condition under which $L$-step finite-memory policies approximate history-dependent policies, via the filter-stability bound $L\ge\widetilde{\Omega}(\gamma^{-4}\log(SH/\epsilon))$. (2) The deterministic filter condition (Definition 3.2): every Bayes belief update returns a one-hot state vector, so there is a function $\psi_h(s_{h-1},a_{h-1},o_h)$ that exactly recovers the current state; this turns distillation into learning a decoding function, a supervised classification task solvable with polynomial samples and time, and it strictly generalizes deterministic transitions, block MDPs, and $k$-step decodable POMDPs. (3) Model truncation for belief learning (Algorithm 4): the learner explores the state space explicitly with a reward-free MDP subroutine (possible only because states are visible in training), estimates transitions and emissions, then redirects probability mass from rarely visited to frequently visited states so the truncated emission stays $(\gamma/2)$-observable; finite-memory beliefs computed on the truncated model are provably within $\epsilon$ of true beliefs in $\ell^1$ under any policy. The belief-weighted policy update $\pi_t(\cdot|z)\propto\pi_{t-1}(\cdot|z)\exp(\eta\,\mathbb{E}_{s\sim b^{\mathrm{apx}}(z)}[Q_{t-1}(z,s,\cdot)])$, a multiplicative-weights step on each memory $z$ with the action-value averaged over the learned belief, is what decouples sample from computational complexity: synchronous updates over all memories cost quasi-polynomial computation per iteration but keep the number of episodes polynomial.

What would settle it

A concrete check: instantiate the $H=1$, $S=O=A=2$ instance from the paper's own Proposition 3.1 with small $\gamma$ (two states whose emission distributions differ by $\gamma$), run Algorithm 2 with $L=\widetilde{\Omega}(\gamma^{-4}\log(SH/\epsilon))$ and about $\mathrm{poly}(1/\epsilon,1/\gamma)$ episodes, and measure both the value gap to the optimal history-dependent policy and the $\ell^1$ error of the learned belief. The theorem predicts both shrink to $O(\epsilon)$; any instance where the gap or the belief error stalls as $1/\gamma$ grows would point at the filter-stability step. A second, sharper test targets the truncation lemma: search over $\gamma$-observable POMDP instances for one where redirection of probability mass from rarely visited to frequently visited states (Algorithm 4) makes the empirical emission matrix fail $\gamma/2$-observability — the proof of Theorem 5.2 depends on that separation being preserved.

Watch

Extended reading notes

Core claim

The central claim, Theorem 5.3, states that for a $\gamma$-observable POMDP $P$ — every emission matrix separates any two beliefs in $\ell^1$ distance by at least $\gamma$ — Algorithm 2 (belief-weighted optimistic asymmetric actor-critic with a truncated-model belief oracle) learns, with probability at least $1-\delta$, a finite-memory policy $\pi\in\Pi_L$ with $v_P(\pi)\ge \max_{\pi'\in\Pi} v_P(\pi')-\epsilon$, using $\mathrm{poly}(S,H,1/\epsilon,1/\gamma,\log(1/\delta),O,A)$ episodes and running in time $\mathrm{poly}(S,H,1/\epsilon,\log(1/\delta),O^L,A^L)$, where $L=\widetilde{\Omega}(\gamma^{-4}\log(SH/\epsilon))$. The sample complexity is polynomial where the best prior guarantees without intractable oracles were quasi-polynomial; the time remains quasi-polynomial, which the paper notes cannot be improved even for planning. A second theorem (4.6) claims that under the deterministic filter condition, expert distillation matches the value of any state-based expert policy with both sample and computational complexity polynomial, including for $k$-decodable POMDPs with unknown, arbitrary $k$, where learning without privileged information is exponential in $k$. The paper also claims (Proposition 3.7) that vanilla asymmetric actor-critic is inherently sample-super-polynomial, and extends both frameworks to partially observable Markov games under centralized-training-with-decentralized-execution information sharing, with polynomial sample and (quasi-)polynomial time guarantees for Nash, correlated, and coarse correlated equilibria.

Load-bearing premise

The load-bearing premise for the main result is $\gamma$-observability: every observation channel must separate any two belief distributions by at least a margin $\gamma$, together with the inherited filter-stability requirement that the memory length $L$ grow like $\gamma^{-4}\log(SH/\epsilon)$. If some channel fails to separate beliefs or $\gamma$ is tiny, finite-memory policies no longer approximate history-dependent policies, the learned belief can be far from the true one, and the polynomial-sample, quasi-polynomial-time guarantee collapses.

Editorial extensions

If this is right

  • For $\gamma$-observable POMDPs, privileged state information during training cuts sample complexity from quasi-polynomial to polynomial while keeping runtime quasi-polynomial, without any computationally intractable planning oracle.
  • Under the deterministic filter condition, expert distillation achieves both polynomial sample and polynomial time, matching a state-based expert's value even when the state-decoding length is unknown and arbitrary; without privileged information, $k$-decodable POMDPs need sample complexity exponential in $k$.
  • The belief-learning oracle is modular: any approximate belief with $\ell^1$ error $\epsilon_{\mathrm{belief}}$ yields a policy with value gap $O(\epsilon + H^2\epsilon_{\mathrm{belief}})$, giving a provable guarantee for the belief-state learning plus planning paradigm used by many empirical systems.
  • Vanilla asymmetric actor-critic cannot be fixed by tuning alone: with tabular parameterization it is provably sample-super-polynomial on $\gamma$-observable POMDPs under standard hardness assumptions.
  • In multi-agent settings with information sharing (centralized training, decentralized execution), the same two paradigms yield polynomial-sample, (quasi-)polynomial-time guarantees for Nash, correlated, and coarse correlated equilibria in the analogous model classes.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A general design principle implicit in the paper: privileged information converts exploration from a POMDP problem into a state-space MDP problem, leaving partial observability to be handled only inside a belief-estimation oracle; the analysis is all-or-nothing about state quality, so how guarantees degrade with noisy, biased, or delayed privileged states is an open extension.
  • The $\gamma^{-4}$ exponent in the required memory length $L$ is imported from filter stability and not shown tight; a sharper filter-stability bound would directly shrink the quasi-polynomial time exponent, since runtime is polynomial in $O^L$ and $A^L$.
  • The explicit counterexample behind Proposition 3.1 doubles as a cheap diagnostic: measuring whether empirical belief updates are near one-hot under random rollouts could tell a practitioner whether the cheap distillation pipeline is safe or whether belief-weighted actor-critic is needed.
  • The truncated-model belief oracle is a standalone reward-free primitive that any $\gamma$-observable POMDP algorithm needing an approximate belief could consume; the paper flags possible independent interest but does not explore such reuse.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. This paper studies partially observable RL in the setting where privileged state information is available during training, and it provides provable guarantees for two practically used paradigms. It first formalizes the expert-distillation (teacher-student) objective in Equation (3.1) and shows, in Proposition 3.1, that even for a gamma-observable POMDP and with infinite distillation data, the distilled policy can be strictly suboptimal. It then introduces the deterministic filter condition (Definition 3.2), which subsumes deterministic POMDPs, block MDPs, and k-step decodable POMDPs with unknown k, and proves that under this condition expert distillation achieves polynomial sample and computational complexity (Theorem 4.6). For the asymmetric actor-critic paradigm, the paper argues that the vanilla variant has super-polynomial sample complexity (Proposition 3.7) and develops a belief-weighted optimistic asymmetric actor-critic (Algorithm 2) together with a belief-learning oracle based on model truncation (Algorithms 3-4). The main guarantee, Theorem 5.3, states that for a gamma-observable POMDP, a policy pi in Π_L can be learned with v_P(pi) >= max_{pi'} v_P(pi') - epsilon using poly(S,H,1/epsilon,1/gamma,log(1/delta),O,A) episodes and quasi-polynomial time, provided L >= Omega-tilde(gamma^{-4} log(SH/epsilon)). The framework is extended to partially observable stochastic games under centralized-training-with-decentralized-execution in Theorems 7.4, 7.6, and 7.7.

Significance. The paper's central claim, that privileged state information reduces the sample complexity of observable POMDPs from quasi-polynomial to polynomial while avoiding computationally intractable planning oracles, is significant if it holds. The algorithmic framework is genuinely modular: the belief-learning oracle of Section 5.2, which truncates rarely visited states while preserving observability and filter stability, is a substantive technical contribution that may be of independent interest, and the deterministic filter condition correctly unifies several known tractable POMDP classes. The presentation is careful about what is imported and what is proved in the paper: the algorithms are explicit, the proofs are detailed and modular, the comparisons with prior work are fair, and the limitation of assuming exact state information is acknowledged in Section 8. The numerical study is honest and small-scale.

major comments (2)
  1. [Section 3.1, Proposition 3.1 (proof in Appendix C)] Proposition 3.1 is stated for any choice of D_f (any f-divergence) in Equation (3.1), but the proof establishes the claim only for strictly convex generators f. The step identifying the minimizer of E_{s~b1(o1)}[D_f(pi*(.|s)||q)] with Unif(A) uses a uniqueness assertion from Jensen's inequality that holds only when f is strictly convex, which the proof itself concedes in the parenthetical 'for the common choice of D_f ... where f is strictly convex.' For a non-strictly-convex generator such as f(t)=|t-1| (total variation), the objective (TV(delta_{a1},q)+TV(delta_{a2},q))/2 equals 1/2 for every q in Delta(A) in the constructed counterexample, so every q is a minimizer; choosing q = delta_{a1} yields a distilled policy whose value gap to the optimal policy is gamma*epsilon/(2-gamma), which is strictly smaller than the claimed (1-gamma)(1-epsilon)/4 for, e.g., gamma = epsilon = 0.1. The proposition should be restricted to strictly convex f (or to a fixed tie-breaking rule that the proof controls), and the statement should be corrected accordingly.
  2. [Appendix F, proof of Theorem F.6 (invoked by Theorem 5.3)] The load-bearing step of the proof of Theorem F.6 is the assertion that, for the truncated learned model bP_sub, E_{bP_sub,pi}||b_{b,sub,h}(tau_h) - b'_{b,sub,h}(z_h)||_1 <= epsilon follows from [22, Theorem 4.1] with L >= Omega-tilde(gamma^{-4} log(SH/epsilon)). Two hypotheses of that imported theorem are not verified for the constructed bP_sub. First, [22, Theorem 4.1] is stated for a POMDP with a fixed state space S, whereas bP_sub has state spaces S_high^h that vary with h; this is not a purely notational issue, because the gamma-observability assumption in the imported theorem is a global condition over all pairs of beliefs on a single state space, and the natural time-augmented model union_h {h} x S_high^h does not automatically inherit it from the slice-wise separation condition shown in the paper. Second, the finite-memory filter b'_{b,sub,h} is re-initialized with the uniform prior over S_high^{h-L} at the start of each length-L window, while the ground-truth belief b_{b,sub,h} is conditioned on the full history under the truncated initial distribution mu_trunc_1; the paper does not check that the imported theorem's constants accommodate this prior mismatch and the burn-in of the contraction. Since this filter-stability bound is essential for Theorem F.6, and hence for the polynomial sample complexity claimed in Theorem 5.3 (and in the multi-agent Theorem 7.7), the authors should provide a self-contained filter-stability lemma for the truncated, time-varying model bP_sub with all constants tracked, or verify the hypotheses of [22, Theorem 4.1] verbatim.
minor comments (4)
  1. [Section 2.2, Definitions 2.2 and 2.3] The displayed formulas for NE-gap and CCE-gap are identical; the distinction between Nash equilibrium and coarse correlated equilibrium (product policies versus potentially correlated joint policies, and the admissible deviation sets) should be made explicit in the displayed equations or by naming the policy classes over which the maxima are taken.
  2. [Appendix C, proof of Proposition 3.7] The argument that the vanilla asymmetric actor-critic has super-polynomial sample complexity is informal: it assumes that convergence of the tabular update to an epsilon-optimal policy would imply a polynomial-time planner whenever the sample complexity is polynomial, but no convergence guarantee for that update rule is stated, and the coupling between per-iteration computation and sample count is not formalized; the proposition should be stated as conditional on that convergence property or proved formally.
  3. [Appendix F, proof of Theorem F.6] The inequality P_{pi,P}(tau_h) <= P_{pi,P_trunc}(tau_h) for tau_h in T_high_h is asserted without justification; a one-line argument that truncation only transfers probability mass out of S_low into S_high, so the probability of every all-high trajectory weakly increases, would make the step transparent.
  4. [Appendix F, Theorem F.6 statement and proof] The statement of Theorem F.6 contains an unmatched parenthesis in L >= Omega-tilde(gamma^{-4} log(S/epsilon), and the accuracy parameter is denoted epsilon in the theorem statement but ϵ (same symbol as the model-error parameter) at several points in the proof; the two accuracies should be distinguished and the notation made consistent.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: the guarantees are built on external structural results and published prior work, with no fitted parameter renamed as a prediction.

full rationale

I walked the derivation chain. The main result (Theorem 5.3) factors into optimistic Q-estimation with concentration-based bonuses (Lemma F.3), a standard multiplicative-weights policy update, and approximate belief learning via model truncation (Theorems 5.2 and F.6). The belief-error bound invokes [22, Theorem 4.1] for the finite-memory filter of the truncated model P_sub; that is an external result, not a self-citation, and the paper states the gamma-observability and memory-length conditions it relies on. The finite-memory-to-full-history reduction invokes [38, Theorem 4.1], also external. The expert-distillation results (Theorems 4.5 and 4.6) are supervised-learning arguments under the deterministic-filter condition, where the decoder is trained on privileged state samples; the value bound is not defined in terms of the trained quantity. The MARL extension uses the authors' prior compressed-common-information framework [29] for the compression bound in Theorem 7.7; this citation is load-bearing, but it is a published result with its own proofs and assumptions, and it is not used to define the target conclusion into existence. The concerns raised by a skeptical reader about whether the time-varying state spaces and uniform-prior initialization of P_sub satisfy all hypotheses of [22, Theorem 4.1] are correctness risks about unverified application conditions, not circular reductions. No equation in the paper reduces to its own input, and no fitted constant is relabeled as a prediction.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

No data-fitted constants appear; the guarantees are parameterized by problem parameters epsilon, delta, and gamma. The main new postulates are structural conditions on the POMDP, plus one implicit strict-convexity assumption in Proposition 3.1 that is not stated in the proposition.

assumptions (6)
  • domain assumption gamma-observability (Assumption 2.5): each emission matrix O_h separates any two beliefs by ell-1 distance at least gamma.
    Load-bearing for all Section 5 and 7 results; enables filter stability and quasi-polynomial planning bounds imported from [38].
  • domain assumption Deterministic filter condition (Definition 3.2): the belief after a one-step update from a known state, action, and observation is one-hot.
    Central assumption for expert distillation guarantees in Section 4; encompasses block MDPs, deterministic transitions, and k-decodable POMDPs.
  • domain assumption Strategy independence of beliefs (Assumption 2.6) and common/private information evolution (Assumption A.4).
    Used in the POSG results to make beliefs independent of policies; inherited from [58,66,29].
  • ad hoc to paper Strict convexity of the f-divergence generator in Proposition 3.1.
    The proposition states 'any choice of D_f', but the Appendix C proof requires strict convexity to force the unique minimizer q=uniform; total variation divergence is a counterexample.
  • standard math Finite-memory filter stability of [38, Theorem 4.1] with L >= Omega-tilde(gamma^{-4} log(SH/epsilon)).
    Used to pass from approximate beliefs on finite memory to near-optimality over all history-dependent policies in Theorems 5.1 and 5.3.
  • standard math EULER or reward-free exploration guarantees for MDPs from [88,89].
    Used in Algorithm 4 and Theorem F.5 to visit every state with enough probability while learning the model under privileged state access.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Provable Partially Observable Reinforcement Learning with Privileged Information." pith.science (2026). https://pith.science/paper/3IIWRSHH

@misc{pith2026241200985,
  author       = {Pith},
  title        = {Pith review of: Provable Partially Observable Reinforcement Learning with Privileged Information},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3IIWRSHH}},
  note         = {Machine review of arXiv:2412.00985}
}
read the original abstract

Partial observability of the underlying states generally presents significant challenges for reinforcement learning (RL). In practice, certain \emph{privileged information}, e.g., the access to states from simulators, has been exploited in training and has achieved prominent empirical successes. To better understand the benefits of privileged information, we revisit and examine several simple and practically used paradigms in this setting. Specifically, we first formalize the empirical paradigm of \emph{expert distillation} (also known as \emph{teacher-student} learning), demonstrating its pitfall in finding near-optimal policies. We then identify a condition of the partially observable environment, the \emph{deterministic filter condition}, under which expert distillation achieves sample and computational complexities that are \emph{both} polynomial. Furthermore, we investigate another useful empirical paradigm of \emph{asymmetric actor-critic}, and focus on the more challenging setting of observable partially observable Markov decision processes. We develop a belief-weighted asymmetric actor-critic algorithm with polynomial sample and quasi-polynomial computational complexities, in which one key component is a new provable oracle for learning belief states that preserve \emph{filter stability} under a misspecified model, which may be of independent interest. Finally, we also investigate the provable efficiency of partially observable multi-agent RL (MARL) with privileged information. We develop algorithms featuring \emph{centralized-training-with-decentralized-execution}, a popular framework in empirical MARL, with polynomial sample and (quasi-)polynomial computational complexities in both paradigms above. Compared with a few recent related theoretical studies, our focus is on understanding practically inspired algorithmic paradigms, without computationally intractable oracles.

Figures

Figures reproduced from arXiv: 2412.00985 by the authors.

Figure 1
Figure 1. A landscape of POMDP models that par￾tially observable RL with privileged information addresses, with both statistical and computational complexity considerations. The x and y axes de￾note the “restrictiveness” of the assumptions, on the emission channels/observations and transition dynamics, respectively. POMDPs, where the last k observation-action pairs can uniquely determine the state, and proposed polynomial-sam… view at source ↗
Figure 2
Figure 2. Results for POMDPs of different moderate sizes, where our methods achieve the best per￾formance with the lowest sample complexity (VI: value iteration; AAC: asymmetric actor-critic). one requires to avoid using computationally intractable oracles for POMDP learning, which is in fact our final goal. We present the guarantees in the next theorem and postpone the proof to Appendix F. Theorem 5.2. Consider a γ-observabl… view at source ↗
Figure 3
Figure 3. Results for POMDPs of larger sizes, where our methods achieve the best performance with [PITH_FULL_IMAGE:figures/full_fig_p057_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

95 extracted references · 70 canonical work pages

  1. [22]

    Learning in observable POMDPs, without computationally intractable oracles

    Noah Golowich, Ankur Moitra, and Dhruv Rohatgi. Learning in observable POMDPs, without computationally intractable oracles. In Advances in Neural Information Processing Systems, 2022. 18

    work page 2022

  2. [1]

    End-to-end training of deep visuomotor policies

    Sergey Levine, Chelsea Finn, Trevor Darrell, and Pieter Abbeel. End-to-end training of deep visuomotor policies. The Journal of Machine Learning Research, 17(1):1334–1373, 2016

    2016

  3. [2]

    Learning dex- terous in-hand manipulation

    OpenAI: Marcin Andrychowicz, Bowen Baker, Maciek Chociej, Rafal Jozefowicz, Bob McGrew, Jakub Pachocki, Arthur Petron, Matthias Plappert, Glenn Powell, Alex Ray, et al. Learning dex- terous in-hand manipulation. The International Journal of Robotics Research, 39(1):3–20, 2020

    2020

  4. [3]

    Safe, multi-agent, reinforcement learning for autonomous driving

    Shai Shalev-Shwartz, Shaked Shammah, and Amnon Shashua. Safe, multi-agent, reinforcement learning for autonomous driving. arXiv preprint arXiv:1610.03295, 2016

    arXiv 2016

  5. [4]

    Deep reinforcement learning for autonomous driving: A survey

    B Ravi Kiran, Ibrahim Sobh, Victor Talpaert, Patrick Mannion, Ahmad A Al Sallab, Senthil Yogamani, and Patrick P´erez. Deep reinforcement learning for autonomous driving: A survey. IEEE Transactions on Intelligent Transportation Systems, 23(6):4909–4926, 2021

    2021

  6. [5]

    Pomdp-based statistical spoken dialog systems: A review

    Steve Young, Milica Ga ˇsi´c, Blaise Thomson, and Jason D Williams. Pomdp-based statistical spoken dialog systems: A review. Proceedings of the IEEE, 101(5):1160–1179, 2013

    2013

  7. [6]

    Informing sequential clinical decision-making through reinforcement learning: an empirical study

    Susan M Shortreed, Eric Laber, Daniel J Lizotte, T Scott Stroup, Joelle Pineau, and Susan A Murphy. Informing sequential clinical decision-making through reinforcement learning: an empirical study. Machine learning, 84:109–136, 2011

    2011

  8. [7]

    The complexity of markov decision processes

    Christos H Papadimitriou and John N Tsitsiklis. The complexity of markov decision processes. Mathematics of operations research, 12(3):441–450, 1987. 17

    1987

Show all 95 references
  1. [8]

    Pac reinforcement learning with rich observations

    Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Pac reinforcement learning with rich observations. Advances in Neural Information Processing Systems, 29, 2016

    2016

  2. [9]

    Sample-e fficient reinforce- ment learning of undercomplete POMDPs

    Chi Jin, Sham Kakade, Akshay Krishnamurthy, and Qinghua Liu. Sample-e fficient reinforce- ment learning of undercomplete POMDPs. Advances in Neural Information Processing Systems , 33:18530–18539, 2020

    2020

  3. [10]

    A counterexample in stochastic optimum control

    Hans S Witsenhausen. A counterexample in stochastic optimum control. SIAM Journal on Control, 6(1):131–147, 1968

    1968

  4. [11]

    On the complexity of decentralized decision making and detection problems

    John Tsitsiklis and Michael Athans. On the complexity of decentralized decision making and detection problems. IEEE Transactions on Automatic Control, 30(5):440–446, 1985

    1985

  5. [12]

    Multi- agent actor-critic for mixed cooperative-competitive environments.Advances in Neural Informa- tion Processing Systems, 30, 2017

    Ryan Lowe, Yi I Wu, Aviv Tamar, Jean Harb, OpenAI Pieter Abbeel, and Igor Mordatch. Multi- agent actor-critic for mixed cooperative-competitive environments.Advances in Neural Informa- tion Processing Systems, 30, 2017

    2017

  6. [13]

    QMIX: Monotonic value function factorisation for deep multi-agent reinforcement learning

    Tabish Rashid, Mikayel Samvelyan, Christian Schroeder De Witt, Gregory Farquhar, Jakob Foer- ster, and Shimon Whiteson. QMIX: Monotonic value function factorisation for deep multi-agent reinforcement learning. In International Conference on Machine learning, pages 681–689, 2018

    2018

  7. [14]

    Counterfactual multi-agent policy gradients

    Jakob Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon White- son. Counterfactual multi-agent policy gradients. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018

    2018

  8. [15]

    Grandmas- ter level in StarCraft II using multi-agent reinforcement learning

    Oriol Vinyals, Igor Babuschkin, Wojciech M Czarnecki, Micha¨el Mathieu, Andrew Dudzik, Jun- young Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmas- ter level in StarCraft II using multi-agent reinforcement learning. Nature, 575(7782):350–354, 2019

    2019

  9. [16]

    Learning quadrupedal locomotion over challenging terrain

    Joonho Lee, Jemin Hwangbo, Lorenz Wellhausen, Vladlen Koltun, and Marco Hutter. Learning quadrupedal locomotion over challenging terrain. Science robotics, 5(47):eabc5986, 2020

    2020

  10. [17]

    Learning robust perceptive locomotion for quadrupedal robots in the wild

    Takahiro Miki, Joonho Lee, Jemin Hwangbo, Lorenz Wellhausen, Vladlen Koltun, and Marco Hutter. Learning robust perceptive locomotion for quadrupedal robots in the wild. Science Robotics, 7(62):eabk2822, 2022

    2022

  11. [18]

    Learning by cheating

    Dian Chen, Brady Zhou, Vladlen Koltun, and Philipp Kr ¨ahenb¨uhl. Learning by cheating. In Conference on Robot Learning, pages 66–75. PMLR, 2020

    2020

  12. [19]

    Asymmetric actor critic for image-based robot learning

    Lerrel Pinto, Marcin Andrychowicz, Peter Welinder, Wojciech Zaremba, and Pieter Abbeel. Asymmetric actor critic for image-based robot learning. Robotics: Science and Systems XIV , 2018

    2018

  13. [20]

    Learning in pomdps is sample- efficient with hindsight observability

    Jonathan Lee, Alekh Agarwal, Christoph Dann, and Tong Zhang. Learning in pomdps is sample- efficient with hindsight observability. In International Conference on Machine Learning , pages 18733–18773. PMLR, 2023

    2023

  14. [21]

    Sample- efficient learning of pomdps with multiple observations in hindsight

    Jiacheng Guo, Minshuo Chen, Huan Wang, Caiming Xiong, Mengdi Wang, and Yu Bai. Sample- efficient learning of pomdps with multiple observations in hindsight. In The Twelfth Interna- tional Conference on Learning Representations, 2023

    2023

  15. [23]

    On oracle-e fficient pac rl with rich observations

    Christoph Dann, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. On oracle-e fficient pac rl with rich observations. Advances in neural in- formation processing systems, 31, 2018

    2018

  16. [24]

    Provably e fficient rl with rich observations via latent state decoding

    Simon Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudik, and John Lang- ford. Provably e fficient rl with rich observations via latent state decoding. In International Conference on Machine Learning, pages 1665–1674. PMLR, 2019

    2019

  17. [25]

    Kinematic state abstraction and provably efficient rich-observation reinforcement learning

    Dipendra Misra, Mikael Hena ff, Akshay Krishnamurthy, and John Langford. Kinematic state abstraction and provably efficient rich-observation reinforcement learning. InInternational con- ference on machine learning, pages 6961–6971. PMLR, 2020

    2020

  18. [26]

    Exploration is harder than prediction: Cryptographically separating reinforcement learning from supervised learning

    Noah Golowich, Ankur Moitra, and Dhruv Rohatgi. Exploration is harder than prediction: Cryptographically separating reinforcement learning from supervised learning. arXiv preprint arXiv:2404.03774, 2024

    2024 arXiv

  19. [27]

    Provable reinforce- ment learning with a short-term memory

    Yonathan Efroni, Chi Jin, Akshay Krishnamurthy, and Sobhan Miryoosefi. Provable reinforce- ment learning with a short-term memory. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesv ´ari, Gang Niu, and Sivan Sabato, editors, International Conference on Machine Lea...

    2022

  20. [28]

    When is partially observable rein- forcement learning not scary? In Conference on Learning Theory, pages 5175–5220, 2022

    Qinghua Liu, Alan Chung, Csaba Szepesvari, and Chi Jin. When is partially observable rein- forcement learning not scary? In Conference on Learning Theory, pages 5175–5220, 2022

    2022

  21. [29]

    Partially observable multi-agent RL with (quasi-)e fficiency: the blessing of information sharing

    Xiangyu Liu and Kaiqing Zhang. Partially observable multi-agent RL with (quasi-)e fficiency: the blessing of information sharing. In International Conference on Machine Learning , pages 22370–22419. PMLR, 2023

    2023

  22. [30]

    Schapire

    Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E. Schapire. Contextual decision processes with low bellman rank are pac-learnable. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, ICML 2...

    2017

  23. [31]

    Represent to control partially ob- served systems: Representation learning with provable sample efficiency

    Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Represent to control partially ob- served systems: Representation learning with provable sample efficiency. In The Eleventh Inter- national Conference on Learning Representations, 2022

    2022

  24. [32]

    Partially observable RL with b-stability: Unified structural condition and sharp sample-e fficient algorithms

    Fan Chen, Yu Bai, and Song Mei. Partially observable RL with b-stability: Unified structural condition and sharp sample-e fficient algorithms. In The Eleventh International Conference on Learning Representations, 2023

    2023

  25. [33]

    Reinforcement learning from partial observation: Linear function approximation with provable sample e fficiency

    Qi Cai, Zhuoran Yang, and Zhaoran Wang. Reinforcement learning from partial observation: Linear function approximation with provable sample e fficiency. In International Conference on Machine Learning, pages 2485–2522. PMLR, 2022

    2022

  26. [34]

    Pessimism in the face of confounders: Provably efficient offline reinforcement learning in partially observable markov decision pro- cesses

    Miao Lu, Yifei Min, Zhaoran Wang, and Zhuoran Yang. Pessimism in the face of confounders: Provably efficient offline reinforcement learning in partially observable markov decision pro- cesses. In The Eleventh International Conference on Learning Representations, 2023

    2023

  27. [35]

    Optimistic MLE: A generic model-based algorithm for partially observable sequential decision making

    Qinghua Liu, Praneeth Netrapalli, Csaba Szepesvari, and Chi Jin. Optimistic MLE: A generic model-based algorithm for partially observable sequential decision making. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 363–376, 2023. 19

    2023

  28. [36]

    Wenhao Zhan, Masatoshi Uehara, Wen Sun, and Jason D. Lee. PAC reinforcement learning for predictive state representations. In The Eleventh International Conference on Learning Represen- tations, 2023

    2023

  29. [37]

    Partially observable multi-agent reinforcement learning with information sharing, 2024

    Xiangyu Liu and Kaiqing Zhang. Partially observable multi-agent reinforcement learning with information sharing, 2024

    2024

  30. [38]

    Planning in observable pomdps in quasipolynomial time

    Noah Golowich, Ankur Moitra, and Dhruv Rohatgi. Planning in observable pomdps in quasipolynomial time. arXiv preprint arXiv:2201.04735, 2022

    2022 arXiv

  31. [39]

    Planning and learning in partially observ- able systems via filter stability

    Noah Golowich, Ankur Moitra, and Dhruv Rohatgi. Planning and learning in partially observ- able systems via filter stability. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 349–362, 2023

    2023

  32. [40]

    Theoretical hardness and tractability of pomdps in rl with partial online state information, 2024

    Ming Shi, Yingbin Liang, and Ness Shro ff. Theoretical hardness and tractability of pomdps in rl with partial online state information, 2024

    2024

  33. [41]

    Leveraging fully observable policies for learning under partial observability

    Hai Nguyen, Andrea Baisero, Dian Wang, Christopher Amato, and Robert Platt. Leveraging fully observable policies for learning under partial observability. In Conference on Robot Learn- ing, 2022

    2022

  34. [42]

    Learning to jump from pixels

    Gabriel B Margolis, Tao Chen, Kartik Paigwar, Xiang Fu, Donghyun Kim, Sang bae Kim, and Pulkit Agrawal. Learning to jump from pixels. In 5th Annual Conference on Robot Learning , 2021

    2021

  35. [43]

    Tgrl: An algorithm for teacher guided reinforcement learning

    Idan Shenfeld, Zhang-Wei Hong, Aviv Tamar, and Pulkit Agrawal. Tgrl: An algorithm for teacher guided reinforcement learning. In International Conference on Machine Learning, pages 31077–31093. PMLR, 2023

    2023

  36. [44]

    Asymmetric DQN for partially observable reinforcement learning

    Andrea Baisero, Brett Daley, and Christopher Amato. Asymmetric DQN for partially observable reinforcement learning. In Uncertainty in Artificial Intelligence, pages 107–117. PMLR, 2022

    2022

  37. [45]

    Perfectdou: Dominating doudizhu with perfect information distillation.Advances in Neural Information Processing Systems, 35:34954–34965, 2022

    Guan Yang, Minghuan Liu, Weijun Hong, Weinan Zhang, Fei Fang, Guangjun Zeng, and Yue Lin. Perfectdou: Dominating doudizhu with perfect information distillation.Advances in Neural Information Processing Systems, 35:34954–34965, 2022

    2022

  38. [46]

    Towards unifying behavioral and response diversity for open-ended learn- ing in zero-sum games

    Xiangyu Liu, Hangtian Jia, Ying Wen, Yujing Hu, Yingfeng Chen, Changjie Fan, Zhipeng Hu, and Yaodong Yang. Towards unifying behavioral and response diversity for open-ended learn- ing in zero-sum games. Advances in Neural Information Processing Systems, 34:941–952, 2021

    2021

  39. [47]

    Unbiased asymmetric reinforcement learning under partial observability

    Andrea Baisero and Christopher Amato. Unbiased asymmetric reinforcement learning under partial observability. In Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, 2022

    2022

  40. [48]

    A deeper understanding of state-based critics in multi-agent reinforcement learning

    Xueguang Lyu, Andrea Baisero, Yuchen Xiao, and Christopher Amato. A deeper understanding of state-based critics in multi-agent reinforcement learning. InProceedings of the AAAI conference on artificial intelligence, volume 36, pages 9396–9404, 2022

    2022

  41. [49]

    On cen- tralized critics in multi-agent reinforcement learning

    Xueguang Lyu, Andrea Baisero, Yuchen Xiao, Brett Daley, and Christopher Amato. On cen- tralized critics in multi-agent reinforcement learning. Journal of Artificial Intelligence Research, 77:295–354, 2023

    2023

  42. [50]

    Learning belief representations for partially observable deep rl

    Andrew Wang, Andrew C Li, Toryn Q Klassen, Rodrigo Toro Icarte, and Sheila A McIlraith. Learning belief representations for partially observable deep rl. In International Conference on Machine Learning, pages 35970–35988. PMLR, 2023. 20

    2023

  43. [51]

    Learning belief representations for imitation learning in pomdps

    Tanmay Gangwani, Joel Lehman, Qiang Liu, and Jian Peng. Learning belief representations for imitation learning in pomdps. In uncertainty in artificial intelligence, pages 1061–1071. PMLR, 2020

    2020

  44. [52]

    Belief-grounded networks for accelerated robot learning under partial observability

    Hai Nguyen, Brett Daley, Xinchao Song, Christopher Amato, and Robert Platt. Belief-grounded networks for accelerated robot learning under partial observability. In Conference on Robot Learning, pages 1640–1653. PMLR, 2021

    2021

  45. [53]

    Learned belief search: Efficiently improving policies in partially observable settings

    Hengyuan Hu, Adam Lerer, Noam Brown, and Jakob Foerster. Learned belief search: Efficiently improving policies in partially observable settings. arXiv preprint arXiv:2106.09086, 2021

    2021 arXiv

  46. [54]

    Flow-based recurrent belief state learning for pomdps

    Xiaoyu Chen, Yao Mark Mu, Ping Luo, Shengbo Li, and Jianyu Chen. Flow-based recurrent belief state learning for pomdps. In International Conference on Machine Learning, pages 3444–

  47. [55]

    Belief state actor-critic algorithm from separation principle for POMDP

    Yujie Yang, Yuxuan Jiang, Jianyu Chen, Shengbo Eben Li, Ziqing Gu, Yuming Yin, Qian Zhang, and Kai Yu. Belief state actor-critic algorithm from separation principle for POMDP. In 2023 American Control Conference (ACC), pages 2560–2567. IEEE, 2023

    2023

  48. [56]

    Neural belief states for partially observed domains

    Pol Moreno, Jan Humplik, George Papamakarios, Bernardo Avila Pires, Lars Buesing, Nicolas Heess, and Theophane Weber. Neural belief states for partially observed domains. In NeurIPS 2018 Workshop on Reinforcement Learning under Partial Observability, 2018

    2018

  49. [57]

    The wasserstein believer: Learning belief updates for partially observable environments through reliable latent space models

    Rapha ¨el Avalos, Florent Delgrange, Ann Nowe, Guillermo Perez, and Diederik M Roijers. The wasserstein believer: Learning belief updates for partially observable environments through reliable latent space models. In The Twelfth International Conference on Learning Representat...

    2023

  50. [58]

    Common informa- tion based markov perfect equilibria for stochastic games with asymmetric information: Finite games

    Ashutosh Nayyar, Abhishek Gupta, Cedric Langbort, and Tamer Bas ¸ar. Common informa- tion based markov perfect equilibria for stochastic games with asymmetric information: Finite games. IEEE Transactions on Automatic Control, 59(3):555–570, 2013

    2013

  51. [59]

    Decentralized stochastic con- trol with partial history sharing: A common information approach

    Ashutosh Nayyar, Aditya Mahajan, and Demosthenis Teneketzis. Decentralized stochastic con- trol with partial history sharing: A common information approach. IEEE Transactions on Auto- matic Control, 58(7):1644–1658, 2013

    2013

  52. [60]

    Sample-e fficient reinforcement learning of par- tially observable Markov games

    Qinghua Liu, Csaba Szepesv ´ari, and Chi Jin. Sample-e fficient reinforcement learning of par- tially observable Markov games. In Advances in Neural Information Processing Systems, 2022

    2022

  53. [61]

    When can we learn general-sum Markov games with a large number of players sample-efficiently? arXiv preprint arXiv:2110.04184, 2021

    Ziang Song, Song Mei, and Yu Bai. When can we learn general-sum Markov games with a large number of players sample-efficiently? arXiv preprint arXiv:2110.04184, 2021

    2021 arXiv

  54. [62]

    A sharp analysis of model-based reinforce- ment learning with self-play

    Qinghua Liu, Tiancheng Yu, Yu Bai, and Chi Jin. A sharp analysis of model-based reinforce- ment learning with self-play. InInternational Conference on Machine Learning, pages 7001–7010. PMLR, 2021

    2021

  55. [63]

    V-learning–a simple, efficient, decen- tralized algorithm for multiagent rl

    Chi Jin, Qinghua Liu, Yuanhao Wang, and Tiancheng Yu. V-learning–a simple, efficient, decen- tralized algorithm for multiagent rl. arXiv preprint arXiv:2110.14555, 2021

    2021 arXiv

  56. [64]

    Algorithmic game theory

    Tim Roughgarden. Algorithmic game theory. Communications of the ACM, 53(7):78–86, 2010

    2010

  57. [65]

    Kakade, and Yishay Mansour

    Eyal Even-Dar, Sham M. Kakade, and Yishay Mansour. The value of observation for monitoring dynamic systems. In Manuela M. Veloso, editor,IJCAI 2007, Proceedings of the 20th International Joint Conference on Artificial Intelligence, Hyderabad, India, January 6-12, 2007, pages 2...

    2007

  58. [66]

    Common information based markov perfect equilibria for linear-gaussian games with asymmetric information

    Abhishek Gupta, Ashutosh Nayyar, C ´edric Langbort, and Tamer Basar. Common information based markov perfect equilibria for linear-gaussian games with asymmetric information. SIAM Journal on Control and Optimization, 52(5):3228–3260, 2014

    2014

  59. [67]

    Poste- rior sampling for competitive rl: Function approximation and partial observation

    Shuang Qiu, Ziyu Dai, Han Zhong, Zhaoran Wang, Zhuoran Yang, and Tong Zhang. Poste- rior sampling for competitive rl: Function approximation and partial observation. Advances in Neural Information Processing Systems, 36, 2024

    2024

  60. [68]

    Learning to communicate with deep multi-agent reinforcement learning

    Jakob Foerster, Ioannis Alexandros Assael, Nando De Freitas, and Shimon Whiteson. Learning to communicate with deep multi-agent reinforcement learning. Advances in Neural Information Processing Systems, 29, 2016

    2016

  61. [69]

    Computationally efficient pac rl in pomdps with latent determinism and conditional embeddings

    Masatoshi Uehara, Ayush Sekhari, Jason D Lee, Nathan Kallus, and Wen Sun. Computationally efficient pac rl in pomdps with latent determinism and conditional embeddings. InInternational Conference on Machine Learning, pages 34615–34641. PMLR, 2023

    2023

  62. [70]

    Actor-critic algorithms

    Vijay R Konda and John N Tsitsiklis. Actor-critic algorithms. In Advances in Neural Information Processing Systems, pages 1008–1014, 2000

    2000

  63. [71]

    Provably e fficient exploration in policy optimization

    Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang. Provably e fficient exploration in policy optimization. In International Conference on Machine Learning, pages 1283–1294. PMLR, 2020

    2020

  64. [72]

    Optimistic policy optimization with bandit feedback

    Lior Shani, Yonathan Efroni, Aviv Rosenberg, and Shie Mannor. Optimistic policy optimization with bandit feedback. In International Conference on Machine Learning, pages 8604–8613. PMLR, 2020

    2020

  65. [73]

    Proximal policy optimization algorithms

    John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017

    2017 arXiv

  66. [74]

    A natural policy gradient

    Sham M Kakade. A natural policy gradient. InAdvances in Neural Information Processing Systems, pages 1531–1538, 2002

    2002

  67. [75]

    Optimality and approxi- mation with policy gradient methods in Markov decision processes

    Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. Optimality and approxi- mation with policy gradient methods in Markov decision processes. In Conference on Learning Theory, pages 64–66, 2020

    2020

  68. [76]

    Information state embedding in partially observable cooperative multi-agent reinforcement learning

    Weichao Mao, Kaiqing Zhang, Erik Miehling, and Tamer Bas ¸ar. Information state embedding in partially observable cooperative multi-agent reinforcement learning. In2020 59th IEEE Con- ference on Decision and Control (CDC), pages 6124–6131. IEEE, 2020

    2020

  69. [77]

    Approximate infor- mation state for approximate planning and reinforcement learning in partially observed sys- tems

    Jayakumar Subramanian, Amit Sinha, Raihan Seraj, and Aditya Mahajan. Approximate infor- mation state for approximate planning and reinforcement learning in partially observed sys- tems. J. Mach. Learn. Res., 23:12–1, 2022

    2022

  70. [78]

    Stochastic games with one step delay sharing information pattern with application to power control

    Eitan Altman, Vijay Kambley, and Alonso Silva. Stochastic games with one step delay sharing information pattern with application to power control. In2009 International Conference on Game Theory for Networks, pages 124–129. IEEE, 2009

    2009

  71. [79]

    A mea- surement study of internet delay asymmetry

    Abhinav Pathak, Himabindu Pucha, Ying Zhang, Y Charlie Hu, and Z Morley Mao. A mea- surement study of internet delay asymmetry. In Passive and Active Network Measurement: 9th International Conference, PAM 2008, Cleveland, OH, USA, April 29-30, 2008. Proceedings 9, pages 182–19...

    2008

  72. [80]

    Repeated games with incomplete information

    Robert J Aumann, Michael Maschler, and Richard E Stearns. Repeated games with incomplete information. MIT press, 1995

    1995

  73. [81]

    Information theory: From coding to learning

    Yury Polyanskiy and Yihong Wu. Information theory: From coding to learning . Cambridge uni- versity press, 2025

    2025

  74. [82]

    On value functions and the agent-environment boundary

    Nan Jiang. On value functions and the agent-environment boundary. arXiv preprint arXiv:1905.13341, 2019

    1905 arXiv

  75. [83]

    A short note on learning discrete distributions

    Cl ´ement L Canonne. A short note on learning discrete distributions. arXiv preprint arXiv:2002.11457, 2020

    2002 arXiv

  76. [84]

    A characteri- zation of multiclass learnability, 2022

    Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, and Amir Yehudayo ff. A characteri- zation of multiclass learnability, 2022

    2022

  77. [85]

    A characteriza- tion of multiclass learnability

    Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, and Amir Yehudayoff. A characteriza- tion of multiclass learnability. In2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 943–955. IEEE, 2022

    2022

  78. [86]

    Approximately optimal approximate reinforcement learning

    Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In International Conference on Machine Learning, volume 2, pages 267–274, 2002

    2002

  79. [87]

    Convex optimization: Algorithms and complexity

    S ´ebastien Bubeck. Convex optimization: Algorithms and complexity. Found. Trends Mach. Learn., 8(3-4):231–357, 2015

    2015

  80. [88]

    Tighter problem-dependent regret bounds in reinforce- ment learning without domain knowledge using value function bounds

    Andrea Zanette and Emma Brunskill. Tighter problem-dependent regret bounds in reinforce- ment learning without domain knowledge using value function bounds. In International Con- ference on Machine Learning, pages 7304–7312. PMLR, 2019

    2019

  81. [89]

    Reward-free exploration for reinforcement learning

    Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for reinforcement learning. In International Conference on Machine Learning, pages 4870–4879. PMLR, 2020

    2020

  82. [90]

    Is Q-learning provably efficient? In Advances in Neural Information Processing Systems, pages 4863–4873, 2018

    Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. Is Q-learning provably efficient? In Advances in Neural Information Processing Systems, pages 4863–4873, 2018

    2018

  83. [91]

    No-regret learning in convex games

    Geo ffrey J Gordon, Amy Greenwald, and Casey Marks. No-regret learning in convex games. In Proceedings of the 25th international conference on Machine learning, pages 360–367, 2008

    2008

  84. [92]

    No-regret learning in bayesian games

    Jason Hartline, Vasilis Syrgkanis, and Eva Tardos. No-regret learning in bayesian games. Ad- vances in Neural Information Processing Systems, 28, 2015

    2015

  85. [93]

    distilled

    Kaito Fujii. Bayes correlated equilibria and no-regret dynamics. arXiv preprint arXiv:2304.05005, 2023. 23 Supplementary Materials Contents 1 Introduction 1 1.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 Preliminaries...

    2023 arXiv

  86. [94]

    By pluggingLt−1(π) into Equation (C.1), with simple algebric manipulations, we prove that: πt h(·|τh)∝πt−1 h (·|τh)exp ηEsh∼bh(τh) h Qt−1 h (τh,sh,·) i

    update has the policy improvement as follows πt← argmax π  Lt−1(π)−η−1EP πt−1   X h∈[H] KL(πh(·|τh)|πt−1 h (·|τh))    , (C.1) whereη is some learning rate andLt−1(π) is a first-order approximation of the expected accumulated rewards atπt−1: Lt...

  87. [95]

    bV (mi⋄πk i )⊙πk −i,G i,h+1 (ch+1) # ,H−h + 1 ) , where the last step is by inductive hypothesis. Now note that for anysh,ph,ah, we have bk−1 h (sh,ah) +Eoh+1∼bJk−1 h (·|sh,ah)

    We define the optimistic Q-function recursively as follows for a memory-state pair (zh,sh)∈Zh×S : eQπ H+1(zH+1,sH+1,·) = 0, ∀zH+1∈ZH+1,sH+1∈S eQπ h (zh,sh,ah) = min  H−h + 1, Esh+1∼bTh(·|sh,ah), oh+1∼bOh+1(·|sh+1) [eVπ h+1(zh+1,sh+1)] +r(sh,ah) +H· min  2,C· s S ...

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.