Source-linked AI summary
On the Complexity of Bayesian Signal Processing
Yi Liu
TL;DR
The paper asks when Bayesian decision-making can be computationally tractable, distinguishing exact from approximate optimality. It develops a computational framework and shows broad hardness results, with bounded signal support as a key tractable case and remaining limitations under some approximation settings.
Problem
The paper studies which notions of optimality—exact Bayes optimality or approximate—can be achieved computationally.
Method
The paper defines tractability through a uniform polynomial-time selector that implements Bayes-optimal choice for every signal-generating process.
Results
Bayes-optimal selection is tractable for every signal-generating process if and only if one action is optimal in every state; signalwise guarantees above the best signal-independent benchmark remain hard even with two supported signals.
Takeaways & Limitations
Bounded signal support is identified as the only remaining source of computational difficulty in one analyzed setting, while bounded support is the only problem in the framework that may admit a tractable solution.
Takeaways & Limitations
The paper currently has neither a polynomial-time deterministic ex ante tractability result where it conjectures one nor a deterministic ex ante tractability result under polynomially bounded support.
Abstract
from arXiv · showhide
We develop a computational framework for Bayesian decision-making. We show that as long as no action is optimal in every state, Bayes-optimal choice is intractable. This hardness need not arise from large action, state, or signal spaces, nor from a complicated represented utility function: extracting enough information from a hard-to-interpret signal to act optimally can itself be computationally hard. We also characterize tractability across approximation notions and identify their sources of difficulty. Under the probably approximately correct criterion, sample-based Bayesian learning is tractable if and only if the signal support is bounded. Our results provide justifications for bounded rationality, costly Bayesian inference, and sample-based Bayesian learning.
1 Introduction
The paper frames Bayesian signal processing as a computational problem even with fixed decision environments, then characterizes when exact and approximate optimal choice is tractable. Its results identify every-signal guarantees and signal-support size as distinct sources of difficulty.
- Framework: The framework fixes the state space, action space, and utility function while representing signal generation with a randomized sampler circuit.A selector receives the sampler description and realized signal and returns an action, with tractability defined by polynomial running time.
- Exact optimality: Exact Bayes-optimal choice is tractable for every signal-generating process if and only if one action is optimal in every state.When no single action is universally optimal, posterior probabilities can approach an action boundary and require extreme precision.
- Exact optimality: Hardness persists with only two supported signals, so exact Bayesian inference need not be difficult because the signal space is large.The construction instead exploits the requirement to succeed after every supported signal.
- Approximation: Any efficient deterministic approximation must be no better than the benchmark achieved by always choosing one signal-independent action.Any improvement over that benchmark, however small, is intractable under a standard complexity assumption, even with two signals.
- Approximation: For PAC ex ante performance, unrestricted signal support remains hard, whereas a known polynomial support bound permits efficient empirical-Bayes learning for fixed nonexact accuracy and confidence.Thus, under this criterion, potentially exponential signal support is the remaining source of computational difficulty.
- Implications: The paper interprets these results as support for bounded rationality, costly Bayesian inference, and sample-based Bayesian learning.It identifies difficult-to-interpret signals and the universal every-signal requirement as central obstacles.
2 Model
The model fixes a finite Bayesian decision environment and encodes experiments as randomized Boolean circuits. A selector maps the circuit description and realized signal to an action, and polynomial-time execution defines tractability.
- Decision environment: The decision environment consists of a full-support rational prior, a fixed finite state and action space, and a utility function determined by state and action.These objects remain fixed while the sampler varies.
- Signal generation: A randomized Boolean circuit takes the state and a uniformly random seed as inputs and outputs the realized signal.The sampler therefore induces a Blackwell experiment.
- Choice rule: The selector α(⟨q⟩,s) takes the sampler description and realized signal as inputs and returns an action.The instance size is based on the encoded sampler and signal lengths.
- Bayesian choice: For positive signal probability, posterior expected payoff is Wa(q,s)/Z(q,s), so maximizing expected payoff is equivalent to maximizing Wa(q,s).This provides the criterion used to define exact Bayes selectors.
- Complexity criterion: A selector is tractable when a deterministic algorithm outputs its action in time polynomial in |⟨q⟩|+|s|.The paper also analyzes selectors that output exact or approximately optimal actions.
3 Exact Bayesian Selectors
Exact Bayes selection is computationally hard when no action is optimal in every state, even with finite states and actions. The difficulty comes from extreme precision and the requirement to act optimally after every supported signal.
- No action being optimal in every state suffices for exact Bayes selection to be intractable.
- Exact optimality may require arbitrarily fine likelihood distinctions near posterior decision boundaries.Minute changes in signal likelihoods can change the optimal action.
- A signalwise exact selector cannot ignore even one signal whose interpretation encodes a difficult likelihood comparison.
- The hardness persists with at most two supported signals, so it is not caused solely by exponentially large signal spaces.
- Relaxing exactness does not remove hardness when guarantees still apply after every supported signal.Theorem 2 and Corollary 2 show that this remains true for signalwise approximation.
4 Approximate Selectors
Approximation remains hard when guarantees must hold after every signal, because selectors must extract decision-relevant information from even difficult signals. For ex ante guarantees, the remaining difficulty can instead arise from exponentially large signal support.
- Signalwise approximation: Signalwise approximation is intractable for any guarantee exceeding the best signal-independent benchmark, even by an arbitrarily small amount.
- Signalwise approximation: Signalwise hardness persists with at most two supported signals, showing that the universal quantifier—not signal count—is central.
- Ex ante approximation: Ex ante approximation remains hard once the target exceeds the no-information benchmark, because actions must condition on observed signals.
- Ex ante approximation: The deterministic ex ante hardness construction uses exponentially large signal support, leaving polynomially bounded support unresolved.
- Ex ante approximation: Under the considered high-probability relaxation, the remaining hardness is driven entirely by potentially exponential signal-space size.
5 Probably Approximately Correct Selectors
PAC ex ante approximation allows randomized selectors to succeed with high probability, but computational tractability is still governed by signal support. Monte Carlo empirical Bayes selectors achieve tractability when support is polynomially bounded, while large support remains the obstacle.
- PAC guarantees imply an expected-payoff guarantee for randomized selectors.
- A polynomial-time randomized PAC ex ante selector exists exactly when the signal support is bounded, under BPP ≠ SZK.
- Monte Carlo empirical Bayes selection uses a fixed training sample, an empirical experiment, and a fixed policy evaluated on query signals.
- For fixed approximation and confidence parameters, potentially exponential signal support is the only remaining computational obstacle to high-probability ex ante approximation.
- With polynomially bounded signal support, training and signal evaluation run in polynomial time for fixed approximation and confidence parameters.
- Finite-sample methods cannot satisfy an unconditional guarantee that must hold with probability one because unrepresentative samples have nonzero probability.
6 Discussions
The discussion shows that computational difficulty depends on the selection guarantee and signal representation, not merely on environment size. It distinguishes exact, signalwise, ex ante, and PAC settings while relating the results to bounded rationality and future structural analyses.
- Randomization and approximation: Randomization cannot improve exact selection beyond tie-breaking, because every action chosen with positive probability must be Bayes optimal.For approximate selection, randomization instead convexifies the action set, and sufficiently accurate approximations to optimizing lotteries can be polynomial-time attainable when the lottery is exactly implementable.
- Randomization and approximation: Under RP≠NP, exact and signalwise selection remain hard even with at most two supported signals.Amplification repeatedly invokes the selector on the same input and uses only internal randomness, leaving the sampler and signal support unchanged.
- Randomization and approximation: Requiring performance after every supported signal preserves the computational barrier once the guarantee exceeds the best signal-independent hedge.A selector must then exploit signal-specific information rather than relying on a randomized hedge across states.
- Interpretation and scope: The hardness results concern asymptotic worst-case scalability: Bayesian performance can fail even the weak requirement of polynomial running time.This supports interpretations involving bounded rationality and costly Bayesian inference, while particular structured experiments may still admit efficient choice.
- Tractability boundaries: A known polynomial bound on signal-support size restores randomized polynomial-time PAC selection, whereas small support alone does not restore exact or signalwise tractability.The constant-support deterministic ex ante case remains open.
- Interpretation and scope: The analysis fixes the economic environment and Bayesian objective, locating difficulty in algorithmic implementability, signal interpretation, precision, and the selection guarantee.Future work includes identifying tractable sampler classes and studying representation-dependent interpretation costs, which the present results do not establish.
7 Conclusions
The conclusions identify the sources of computational hardness in Bayesian signal processing and characterize when approximation and sample-based methods become tractable. They also connect these results to bounded rationality and costly Bayesian inference while leaving deterministic ex ante tractability as an open question.
- Bayes-optimal choice: A uniform polynomial-time selector implements Bayes-optimal choice for every signal-generating process if and only if one action is optimal in every state.This result supports boundedly rational choice and models assigning nonnegligible costs to full Bayesian inference.
- Sources of hardness: Exact choice can require resolving arbitrarily fine likelihood differences near an action boundary, while signalwise guarantees require success after every supported signal.The universal quantifier remains a hardness source even when exactness is relaxed.
- Signalwise approximation: Any signalwise guarantee above the best signal-independent benchmark remains hard even with only two supported signals.Thus, signal-space size is not necessary for this hardness.
- PAC ex ante performance: For PAC ex ante performance, potentially exponential signal support is the only remaining source of computational difficulty.When support is polynomially bounded, Monte Carlo empirical Bayes gives a tractable solution for any fixed nonexact approximation and confidence level.
- Sample-based methods: Under the uniform worst case, knowing the full signal-generating process may offer no tractability advantage over black-box sampling access.The results therefore provide a computational justification for sample-based methods in economics, computer science, and statistics.
- Open questions: A natural open question is whether bounded signal support restores deterministic ex ante tractability, which the authors conjecture it does.The paper also leaves restricted sampler classes and their tractable structural properties for future work.
A Omitted Proofs
The omitted proofs establish the paper’s hardness and tractability claims through reductions, posterior constructions, selector calls, and polynomial-time verification steps.
- Tractable cases: The proofs also establish tractability at the benchmark level by showing that a constant selector is exactly optimal in the corresponding construction.A randomized polynomial-time procedure is used in the associated Statistical Difference argument.
- Proof constructions: The proofs construct rational posterior lines that cross decision boundaries, allowing optimal actions to encode computational instances.The construction uses two distinct signals and full-support beliefs.
- Proof constructions: A fair-coin sampler realizes the required posterior line without supplying the line parameter to the sampler.The induced acceptance probability is used to encode the relevant computational quantity.
- Hardness reductions: Exact Bayes selection is PP-hard because one selector call followed by a fixed decoder solves the source problem.The construction is polynomial time, with at most O(n) selector calls in the relevant proof.
- Hardness reductions: The hardness reductions use selector outputs to compress SAT lists while preserving whether at least one residual formula is satisfiable.Repeated safe deletions maintain a bounded list and yield a polynomial-time procedure.
B Sample Lower Bounds
The sample lower-bound section studies fixed-training-sample selectors and proves that limited samples cannot reliably recover hidden signal-dependent actions.
- Testing argument: The posterior-optimal action at signal (j,x) is b_jx under one hidden vector and −b_jx under its negation.Every policy therefore incurs a signalwise error trade-off across the paired hypotheses.
- Learning model: A fixed-training-sample forward-sampling selector observes N independent draws from each state and then produces a deterministic policy.The policy is held fixed during evaluation and makes no additional sampler calls.
- Lower-bound construction: The lower bound hides a binary vector in paired signal probabilities, so coordinate errors cause incorrect actions on corresponding signals.This reduction relates policy performance to Hamming error in estimating the hidden vector.
- Sample lower bound: If N ≤ K/(128γ^2), transcript distributions remain close enough that the hidden vector cannot be recovered accurately.The proof uses KL divergence, Pinsker’s inequality, and total variation testing bounds.
- Testing argument: The confidence term is obtained by reducing successful PAC performance to a binary testing problem between transcript distributions.The final comparison applies the Bretagnolle–Huber inequality and the stated confidence restriction.
C Preliminaries
This section provides an informal, self-contained guide to the computational concepts used in the paper.
- Preliminaries: The section is an informal guide to the paper’s computational concepts.It is intended to be self-contained.
- Preliminaries: The guide is designed to support understanding of the computational framework used in the paper.The passage characterizes the guide as self-contained rather than presenting a technical result.
- Preliminaries: The section focuses on computational concepts used throughout the paper.No specific concept is named in the supplied passage.
C.1 Circuits and representations
Boolean circuits represent finite bounded-time deterministic or randomized processes, with ordinary inputs encoding states and random inputs serving as seeds. Forward signal generation is efficient, but evaluating an observed signal’s likelihood may require aggregating over exponentially many seeds.
- A Boolean circuit is a finite directed acyclic network whose gates apply fixed Boolean operations to incoming bits.
- Randomized circuits use independent fair-bit inputs; fixing the state and random seed makes the circuit deterministic and produces signal s=q(θ;R).
- A forward draw is easy to generate by sampling R and evaluating the circuit, whereas observed-signal likelihoods may require aggregating over exponentially many seeds.
- Gate-list encodings support polynomial-time circuit evaluation, and reasonable gate bases and numbering conventions are intertranslatable with polynomial overhead.
- Circuit representations encode states, records, messages, actions, and bounded-time deterministic or randomized algorithms with only polynomial overhead.
C.2 Complexity classes
The section introduces standard complexity classes for deterministic, randomized, verifiable, majority-based, and zero-knowledge computation. It also states relevant containments, conjectures, and canonical complete problems.
- P contains problems decidable deterministically in polynomial time, while NP contains problems whose yes-instances have polynomial-length certificates verifiable in polynomial time.
- PP accepts yes-instances when a strict majority of random tapes accept; Majsat asks whether more than half of assignments satisfy a formula and is PP-complete.
- SZK uses interactive proofs whose verifier’s view can be efficiently simulated without the prover up to negligible statistical distance; Statistical Difference is SZK-complete.
- The section uses the conjecture P=BPP, which would imply RP=P, and notes that RP≠NP together with P≠NP would follow under the stated implications.