Breathlessness is a common symptom in clinical practice, yet evidence for cost-effective strategies to diagnose the underlying health conditions causing breathlessness remains limited. Using Swedish population data with individuals with moderate to severe breathlessness, we developed an artificial intelligence (AI) reinforcement learning model to identify optimal, low-cost diagnostic pathways for breathlessness tailored to subgroups based on sex and smoking exposure. Sixteen clinically relevant conditions were defined, along with their diagnostic tests and standard healthcare costs. The AI-based approach successfully produced efficient and low-cost diagnostic pathways for breathlessness with high diagnostic yield. The optimal sequences were overall similar between the subgroups. For all participant subgroups, the AI-derived pathways initially identified (or order of effectiveness in relation to costs) clinical evaluations of body mass index, anxiety and depression, physical activity levels, and spirometry. Subsequent steps included diffusing capacity measurements, chest computer tomography, and hemoglobin assessment. Overall, investigations of the lungs were prioritized ahead of investigations of the heart. This strategy has the potential to streamline the evaluation of breathlessness, reduce unnecessary testing, lead to an earlier diagnosis at lower cost, and support more targeted clinical management.