Optimality and Complexity of Opportunistic Spectrum Access: A Truncated Markov Decision Process Formulation
Bibliographic record
Abstract
We consider opportunistic spectrum access (OSA) which allows secondary users to identify and exploit instantaneous spectrum opportunities resulting from the bursty traffic of primary users. Within the framework of partially observable Markov decision process (POMDP), we develop decentralized cognitive MAC protocols that allow secondary users to independently search for spectrum opportunities without a central coordinator or a dedicated communication channel. The focus of this paper is the tradeoff between optimality and complexity of obtaining OSA protocols. We first analyze the computational complexity of designing OSA protocols within the POMDP framework and demonstrate that the complexity grows exponentially with the horizon length (i.e, the spectrum access time of secondary users). By exploiting the underlying structure of the problem, we aim to develop a quantitative characterization of the fundamental tradeoff between optimality and complexity so that a systematic way of balancing these two can be obtained. Specifically, by exploiting the mixing time of the underlying Markov process of spectrum occupancy, we develop a truncated MDP formulation of OSA and reduce the computational complexity from growing exponentially to linearly with the horizon length. More importantly, this truncated MDP formulation provides a systematical way of trading off performance with complexity by choosing an appropriate truncation parameter.
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
How this classification was reachedexpand
Full frame distilled prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. Learned from the 10,348 direct Codex labels and 10,348 direct Gemma labels. Candidate is the union of thresholded teacher heads; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels or direct frontier model labels.
Codex and Gemma teacher scores by category
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.001 | 0.000 |
| Meta-epidemiology (narrow) | 0.000 | 0.000 |
| Meta-epidemiology (broad) | 0.000 | 0.000 |
| Bibliometrics | 0.000 | 0.001 |
| Science and technology studies | 0.000 | 0.000 |
| Scholarly communication | 0.000 | 0.001 |
| Open science | 0.000 | 0.000 |
| Research integrity | 0.000 | 0.000 |
| Insufficient payload (model declined to judge) | 0.000 | 0.000 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from itClassification
machine, unvalidatedMachine predicted; a candidate call from one teacher head, not a consensus.
How this classification was reached, model by model and score by score, is at the end of the page under "How this classification was reached".