Research map / Probabilistic and scientific modeling / Molecules and proteins
Formal Quality Measures for Predictors in Markov Decision Processes
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces formal quality measures (confusion-matrix-based precision, recall, f-score, MCC, averaged over uniformly sampled memoryless randomized policies) and probability-raising causal volumes for predictors in MDPs, with complexity results for checking PR policies.
Problem
How to quantify how well a set of states predicts reaching failure/undesired terminal states in an MDP whose non-determinism is unresolved, since prediction quality depends on how decisions are resolved.
Approach
Average binary-classifier quality measures (precision, recall, f-score, MCC) over a uniform (Lebesgue) measure on memoryless randomized policies, and define the causal volume of a predictor as the fraction of memoryless policies under which it is a probability-raising cause of the outcome.
Key results
- On a small network MDP, the average f-score of predictor {A} is about 0.43 versus about 0.60 for predictor {B}, so B is on average the better predictor for message loss.
- For the Suzy/Billy-style network example with C={B}, the strict and global causal volumes are both 1, since almost all memoryless randomized policies are PR policies.
- Deciding existence of a strict probability-raising policy is in P; deciding existence of a global probability-raising policy is in NP.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use predictor B instead of predictor A | Average predictor-quality measure on the communication network MDP · Communication network MDP example | average f-score: \approx 0.43 -> \approx 0.60 | Helped |
| use predictor B for message loss prediction | Causal-volume measure on the communication network MDP · Communication network MDP example | global causal volume: 1 | Helped |
Limitations
- Exact integration of the average quality measures is generally out of reach; Monte Carlo approximation is needed.
- GPR existence check is only shown in NP, not a tight complexity bound.
- Evaluation is limited to small illustrative examples without empirical benchmarks.
Experimental setup
Metrics: precision recall f-score Matthews correlation coefficient causal volume
Builds on: probability-raising causality in MDPs canonical MDP / MEC quotient state-action frequency LP formulation
Closest papers by meaning
- Efficient and Sharp Off-Policy Evaluation in Robust Markov Decision Processes (NeurIPS 2024 · similarity 0.85)
- SaVeR: Optimal Data Collection Strategy for Safe Policy Evaluation in Tabular MDP (ICML 2024 · similarity 0.84)
- Soft Robust MDPs and Risk-Sensitive MDPs: Equivalence, Policy Gradient, and Sample Complexity (ICLR 2024 · similarity 0.83)
- Solving Robust Markov Decision Processes: Generic, Reliable, Efficient (AAAI 2025 · similarity 0.83)
- The Number of Trials Matters in Infinite-Horizon General-Utility Markov Decision Processes (ICML 2025 · similarity 0.83)
- Robust Active Measuring under Model Uncertainty (AAAI 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.