{"id":"f9dc612b-59ee-410f-8bc5-a0ffd50f316d","arxiv_id":"2412.00033","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"Given a sufficiently accurate model of social dynamics, there provably exist policies that are near-optimal for a chosen social welfare function with high probability, plus a safety filter for arbitrary black-box policies.","lead":"This paper defines what it would mean for an AI policymaker to be 'probably approximately aligned' with society, and proves that near-optimal policies exist if the AI has an accurate enough model of how actions affect people. It also shows how to restrict the actions of any black-box AI so that every action it is allowed to take is verifiably safe for society.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 5's q<0 concentration bound is false: a two-point counterexample violates it, so Theorem 2's all-q existence claim is unproved for q<0.","rationale":"The stress-test confirms the reader's concern and sharpens it. The q<0 branch of Lemma 5 is not merely missing a proof step; the bound itself is numerically false. The example N=2, X={1,2}, q=-1, n=1, ε=0.6 gives an exact tail probability of 0.5, while the bound used in Theorem 3 is ≈0.396. Since Theorem 2 is stated for all real q, and the paper's own Table 1 supports negative-q SWFs (e.g., CRSI allows any q∈R), this is a load-bearing gap in the central existence theorem. The safe-policy theorem also invokes Γ for q∈R and therefore inherits the issue. I find no similar counterexample for q≥1 or q=0; the utilitarian case and the general proof skeleton seem sound modulo the Γ-placement typo in Eq. (8). Because the theorem may be repairable (e.g., by restricting q or substituting a valid bound), the appropriate disposition remains conditional: the manuscript should be revised before the all-q claim is accepted.","tokens_in":25962,"tokens_out":28955,"duration_ms":247271,"concrete_test":"Compute the exact probability for the two-point case q=-1, a=1, b=2, N=2, n=1, ε=0.6 and compare it with Lemma 5's bound as used in Theorem 3 (Eq. (9)'s Γ placed in the numerator). The exact probability is 1/2; the claimed bound is 2e^{-1.62}≈0.396. If 0.5 > 0.396, the q<0 branch of Lemma 5 is false, confirming the proof gap. A secondary check is to re-derive the q<0 branch via the mean-value theorem, which yields a bound with q^2 b^{2q-2}/(a^q-b^q)^2 in the exponent and does not justify the stated (1-2q)^2 constant.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim (Theorem 2) asserts existence of PAA policies for every q∈R. The proof (Theorem 3) relies on Lemma 5 to bound the assessor-sampling error Z1 for all q. The q<0 branch of Lemma 5 is false. Its proof uses the inequality (1+x)^q ≤ 1-(1-2q)x, which fails; e.g., q=-1 and x=0.1 gives 0.909 ≤ 0.7. More importantly, the resulting bound is contradicted by a finite example. Let q=-1, a=1, b=2, N=2, X={1,2}, n=1, ε=0.6. The population harmonic mean is 4/3; the sample is 1 or 2 with equal probability, so P(|S-4/3|≥0.6)=0.5. Using Eq. (9)'s Γ for q<0 in the numerator, as the proof and Theorem 3 do, the Lemma 5 bound is 2 exp(-2·1·0.6^2·2.25 / ((1-1/2)(1+1/1))) = 2 exp(-1.62) ≈ 0.396 < 0.5. Thus the stated concentration inequality is not just unproved but false. Since no alternative q<0 bound is supplied, the existence theorem is unproved for the negative-power-mean social welfare functions (including harmonic and near-egalitarian rules), which the paper explicitly claims to cover. The safe-policy Theorem 8 inherits the same issue through Γmax.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper defines a Social Markov Decision Process whose reward is the expected future discounted power-mean social welfare W_q of the members of a society, and defines a policy to be δ-ε-PAA if, with probability at least 1−δ, its expected social welfare is within ε of the optimal policy. The central theoretical contribution is Theorem 2: under a uniform KL-divergence bound on an approximate world model, a computable δ-ε-PAA policy exists for every q∈R. The proof adapts the sparse-sampling planner of Kearns et al., bounding separately the error from sampling a subset of assessors, from the approximate dynamics model, and from Monte Carlo rollouts. The paper also introduces δ-ω-safe policies and proves in Theorem 8 that any black-box policy can be restricted to a safe action set while preserving a desired safety level.","tokens_in":26236,"tokens_out":7224,"duration_ms":68819,"significance":"If the technical gaps are repaired, the paper offers a useful formal bridge between social choice and MDP planning: alignment is quantified as ε-δ near-optimality in a constructed social MDP, and the sufficient condition on model accuracy is explicit and checkable in principle. The proof architecture is transparent and largely faithful to sparse sampling, and the claimed sample complexities are independent of the number of states. I found no circularity: PAA is defined independently as near-optimality in the constructed MDP, and the theorems are derived from standard concentration and planning results rather than by fitting the definitions to the conclusions. The main blocker is a false concentration lemma used for negative power-mean social welfare functions.","major_comments":[{"comment":"The q<0 branch of Lemma 5 is invalid. The proof asserts the inequality (1+x)^q ≤ 1−(1−2q)x for 0<x≤1 and q<0, which is false; for q=−1 and x=0.1 it gives 0.909 ≤ 0.7. The stated bound is not merely unproved but contradicted by a finite example: take q=−1, X={1,2}, N=2, n=1, ε=0.6. The population power mean is 4/3, the sample is 1 or 2 with equal probability, so P(|S−4/3|≥0.6)=0.5. With Γ(ε,a,b,q)=(1−2q)^2 b^{2q−2}/(a^q−b^q)^2=9/4, Eq. (8) gives 2 exp(−2·1·0.36·2.25/((1−1/2)(1+1/1)))=2e^{−1.62}≈0.396<0.5. Since Theorem 3 uses Lemma 5 to bound the term Z1 for every q∈R, and Theorem 2 claims existence of PAA policies for every q∈R, the existence theorem is unproved for negative-power-mean social welfare functions, including the harmonic and near-egalitarian cases the paper explicitly claims to cover. Theorem 8 inherits the same gap through Γmax in the definition of α. A valid substitute concentration bound for q<0, or a restriction of the theorems to q≥0, is needed.","section":"Appendix A.2.1, Lemma 5 (Eqs. (8)–(9))"}],"minor_comments":[{"comment":"The lemma statement contains a dangling fragment: \"such that D_KL(p∥p̂) ≤ d ∈ R and .\" This should be completed or the stray \"and .\" removed.","section":"Appendix A.2.1, Lemma 6"},{"comment":"The text says Umin=0 is allowed in specific cases, but the q=0 branch of Lemma 5 requires log a to be defined and hence requires Umin>0 for the geometric mean. Please clarify which values of q are admissible when Umin=0.","section":"Section 2.1.1 and Eq. (9)"},{"comment":"The bookkeeping of the γ^k term is hard to follow because the displayed expression and the definition of β contain unbalanced parentheses and a conditional formatting artifact. Rewriting that line with explicit parentheses would improve readability.","section":"Theorem 3 proof, near Eq. (18)"},{"comment":"The notation \\hat E^K_{s'∼\\hat p} is used in Eq. (3) before it is defined in the surrounding text; please define the empirical expectation operator before first use.","section":"Eq. (3)"}],"recommendation":"major_revision","confidential_remarks":"The paper is well within the scope of the venue and the high-level idea is interesting. The only load-bearing technical defect I found is the q<0 branch of Lemma 5, but it directly undermines Theorem 2, Theorem 3, and Theorem 8 for a nontrivial range of q. I did not find evidence of circular reasoning or problematic citation practices. The authors should be asked either to supply a correct concentration inequality for negative power means or to restrict the theorems and explain why q<0 is excluded."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: the paper gives a serious formal framework—Social MDPs with power-mean welfare, probably approximately aligned policies, and a safe-policy shield—but the main theorem claiming PAA policies for every q in R is not proven. I checked the stress-test counterexample for Lemma 5 and it lands: for q=-1, a=1, b=2, N=2, n=1, eps=0.6, the true probability is 0.5, while the bound produced by the proof is about 0.396. The culprit is the inequality (1+x)^q <= 1-(1-2q)x for q<0, which is false; the subsequent step cannot be repaired without a different argument. Theorem 2 and Theorem 3 therefore only have support for the q range where Lemma 5 actually holds.\n\nWhat is new and good: the Social MDP formalization, the epsilon-delta PAA definition, and the idea of certifying near-optimal alignment from world-model KL accuracy and finite utility samples are all legitimate contributions. The q=1 utilitarian case is a clean adaptation of Kearns-Mansour-Ng sparse sampling, and the safe-policy restriction is a sensible practical fallback. The alignment definition is not circular; the fact that the SWF and the reward share a functional is explicit.\n\nSoft spots beyond the q<0 break: the Gamma constants in Eq. (9) for q=0 and q=1 look reciprocal to what the supplied Hoeffding-Serfling argument actually establishes. That is an inconsistency inside the lemma statement, not just a typo, because Theorem 3 plugs Gamma directly into the sample-size requirement. The safe-policy theorem inherits the same Gamma_max issue. None of this kills the q=1-only version, but the manuscript as written overclaims: the abstract and theorems say q in R.\n\nWho should read it: people working on formal alignment, social choice + RL, or verifiable safe decision-making. The framework is worth engaging with, but don't cite the all-q existence theorem until the concentration lemma is fixed or the theorem is restricted.\n\nRecommendation: send to serious referees. This deserves review, not desk rejection; but it needs major revision—either a valid q<0 bound, corrected Gamma constants, or a clearly supported q range.","headline":"A worthwhile SMDP/PAA framework whose all-q existence theorem is undercut by a false concentration lemma for q<0 and mismatched Gamma constants for q=0,1.","tokens_in":26796,"tokens_out":6985,"would_cite":false,"duration_ms":60386,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B14","68Q32"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that a computable near-optimal social-welfare policy exists whenever a predictive world model is accurate enough, and that any black-box policy can be made safe by blocking destructive actions.","keywords":["probably approximately aligned","social welfare","power mean","Markov decision process","AI alignment","safe policies","sample complexity","social choice"],"falsifier":"Evaluate the claimed inequality used in Lemma 5 with $q=-1$ and $x=0.1$: it asserts $(1+x)^q \\le 1-(1-2q)x$, i.e. $0.909 \\le 0.7$, which is false; that single failure means the concentration bound for $q<0$ is not established, and the theorem's negative-$q$ branch collapses unless a different bound is found.","tokens_in":25723,"feed_emoji":"🏛️","tokens_out":9120,"duration_ms":83122,"temperature":0.7,"pith_summary":"This paper asks whether an autonomous AI agent can be trusted to make social decisions and answers with a formal conditional yes. It defines social welfare in a Markov decision process as the power-mean aggregation of individual utilities, and calls a policy probably approximately aligned (PAA) if it achieves near-optimal expected discounted social welfare with high probability. The paper proves that a computable PAA policy exists whenever the predictive world model's worst-case KL divergence from the true dynamics is below an explicit threshold. The proof also specifies how many sampled utility reports, how many model calls, and what planning depth suffice. A separate result shows that any black-box policy can be wrapped into a safe policy that verifiably avoids destructive states.","feed_headline":"Good enough world models yield provably aligned AI policies","feed_subtitle":"Near-optimal social welfare is certified from a KL-accurate model plus sampled utilities; unsafe actions can be blocked.","key_machinery":"The carrying object is the sparse-sampling $Q$-estimator $\\hat Q^h$ defined recursively in Eq. (6), where the reward is the power-mean welfare of a random subset of assessors and the next-state expectations are taken under the approximate model. The proof skeleton follows the classic sparse-sampling planner, but the approximation machinery is new: Lemma 5 gives a Hoeffding--Serfling concentration bound for the power mean, Lemma 6 bounds the reward error from approximating $p$ by $\\hat p$, and Lemma 7 bounds the value loss incurred by acting greedily with respect to an approximate $Q$-function. The planner's parameters $K$, $C$, $n$, and $H$ are chosen so that all six error terms fit inside the approximation budget determined by $\\epsilon$ and the model error.","core_discovery":"The central claim is Theorem 2: for any social MDP with power-mean welfare $W_q$ and any tolerances $\\epsilon>0$, $\\delta\\in[0,1)$, if there exists an approximate dynamics model $\\hat p$ with $\\sup_{(s,a)} D_{\\mathrm{KL}}(p(\\cdot|s,a)\\,\\|\\,\\hat p(\\cdot|s,a)) < \\epsilon^2(1-\\gamma)^4 / (8\\,\\Delta W^2)$, then a computable $\\delta$-$\\epsilon$-PAA policy exists. The policy is the greedy action on recursively estimated $Q$-values from a sparse-sampling planner that simulates transitions with $\\hat p$ and estimates rewards from a finite panel of sampled utilities. The proof decomposes the error into six terms and bounds each with concentration inequalities: Lemma 5 controls sampling error of the power mean, Lemma 6 controls model mismatch through KL divergence, and Lemma 7 converts approximate $Q$-values into a value-function loss. Consequently, near-optimal alignment can be certified from model accuracy and finite utility feedback without ever observing the agent's true objective.","pith_inferences":["If the theorem survives the $q<0$ gap, alignment audits could shift from inspecting an agent's objective to validating the predictive model, because the guarantee is driven entirely by world-model accuracy and sampled utilities.","The safe-policy wrapper suggests a practical deployment path: keep a black-box policy for its competence, compute $\\hat Q^H$ from a learned simulator, and veto any action whose estimated continuation value falls below the safe threshold; this is testable in any simulator with known ground truth.","Because the reward class is tied to the power mean, the framework's applicability depends on which informational basis a society adopts for comparing utilities; changing that basis changes the concentration constants and hence the required sample sizes."],"forward_implications":["For any $\\epsilon>0$ and $\\delta\\in[0,1)$, a computable $\\delta$-$\\epsilon$-PAA policy exists whenever the world model's worst-case KL error is below the stated threshold, with explicit sample sizes and horizon.","Because the bounds do not depend on the size of the state space, the existence result applies to infinite state spaces as long as the action space is finite.","Any black-box policy can be converted into a $\\delta$-$\\omega$-safe policy by action masking, at the cost of refusing actions whose estimated continuation value is too low.","The safe-policy result does not require the world model to meet the PAA accuracy threshold; lower model accuracy only shrinks the set of verifiably safe actions.","Alignment becomes an a priori, quantitative property: a society can verify the guarantee from the world model and a finite utility sample rather than from observed behavior."],"supporting_citations":[{"why":"Supplies the sparse-sampling planner that the proof adapts to approximate dynamics and estimated rewards.","marker":"[19]"},{"why":"Establishes that admissible social welfare functionals reduce to a social welfare function, justifying the use of a single welfare aggregator.","marker":"[29]"},{"why":"Shows the power mean covers the admissible social welfare functions, fixing the class of rewards considered.","marker":"[7]"},{"why":"Provides the Hoeffding--Serfling concentration inequality for sampling without replacement used in Lemma 5.","marker":"[4]"},{"why":"Original Serfling inequality used for the one-sided sampling bounds in the appendix.","marker":"[33]"},{"why":"Gives existence conditions for optimal policies in discounted MDPs, needed to identify the supremum with a maximum.","marker":"[12]"}],"fun_headline_variants":["Formal proof: AI can govern safely with near-optimal policies","Provably safe AI governance: alignment without knowing the goal","PAA exists: good models and sampled utilities certify safe AI","AI safety theorem: near-optimal policies from approximate models"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The existence theorem depends on a concentration bound for how well a random sample of citizens estimates the social-welfare average, and the proof of that bound for negative welfare exponents uses an algebraic inequality that does not hold, so the theorem's coverage of that range is not established.","fun_headline_variants_meta":{"raw":{"variants":["Formal proof: AI can govern safely with near-optimal policies","Provably safe AI governance: alignment without knowing the goal","PAA exists: good models and sampled utilities certify safe AI","AI safety theorem: near-optimal policies from approximate models"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000517,"raw_usage":{"total_tokens":2497,"prompt_tokens":925,"completion_tokens":1572,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":541,"completion_tokens_details":{"reasoning_tokens":1502}},"tokens_in":541,"tokens_out":1572,"duration_ms":12099,"temperature":1.0,"reasoning_tokens":1502,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T15:37:06.277819+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Evaluate the claimed inequality used in Lemma 5 with $q=-1$ and $x=0.1$: it asserts $(1+x)^q \\le 1-(1-2q)x$, i.e. $0.909 \\le 0.7$, which is false; that single failure means the concentration bound for $q<0$ is not established, and the theorem's negative-$q$ branch collapses unless a different bound is found.","supporting_citations":[{"cited_title":"A Sparse Sampling Algorithm for Near-optimal Planning in Large Markov Decision Processes","cited_arxiv_id":null,"evidence_quote":"Supplies the sparse-sampling planner that the proof adapts to approximate dynamics and estimated rewards."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes that admissible social welfare functionals reduce to a social welfare function, justifying the use of a single welfare aggregator."},{"cited_title":"An Axiomatic Theory of Provably-Fair Welfare-Centric Machine Learning","cited_arxiv_id":null,"evidence_quote":"Shows the power mean covers the admissible social welfare functions, fixing the class of rewards considered."},{"cited_title":"Concentration Inequalities for Sampling without Replace- ment","cited_arxiv_id":null,"evidence_quote":"Provides the Hoeffding--Serfling concentration inequality for sampling without replacement used in Lemma 5."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Original Serfling inequality used for the one-sided sampling bounds in the appendix."},{"cited_title":"Feinberg","cited_arxiv_id":null,"evidence_quote":"Gives existence conditions for optimal policies in discounted MDPs, needed to identify the supremum with a maximum."}],"review_version":1}