Messager RNA is a promising candidate with many applications in therapeutics, but its efficacy is affected by by mRNA instability and inefficient protein expression. Here we propose a framework utilizing reinforcement learning to design mRNA sequences for better stability and translation via combinatorial optimization by synonymous substitution. We combine dynamic programming based RNA folding algorithms, and RNAdegformer, a neural network that directly predicts mRNA degradation rates to create an environment in which the reinforcement learning agent could learn to design mRNA sequences. Additionally, we create a computational-experimental platform to test our computationally designed mRNA sequences by measuring in solution half-lives and in vivo translation output. Upon optimizing mRNA structure, degradation rates, and codon usage, we find that our approach produces design mRNA sequences that are not only more stable but also have higher translation output than previous design methods. Compared to wildtype baselines, our approach achieves up to over 4 time increase in in solution half-life and up to over 8 time increase in translation output. Our findings demonstrate that reinforcement learning is a promising approach to improve mRNA stability and translation and can help achieve more equitable access to mRNA vaccines around the world.