We propose a novel computational framework that models human social decision-making under uncertainty as an integrated Multi-Armed Bandit (MAB) and Markov Decision Process (MDP) optimization problem, in which agents adaptively balance the exploration of new social ties and the exploitation of existing relationships to maximize a socio-evolutionary fitness. The framework combines reinforcement learning, Bayesian belief updating, and agent-based simulation on a dynamic social graph, allowing each agent to use bandit-based Upper-Confidence-Bound (UCB) strategies for tie formation within an MDP of long-term social planning. We define a formal socio-evolutionary fitness function that captures both individual payoffs (e.g. shared information or support) and network-level benefits, and we derive update rules incorporating cognitive constraints and bounded rationality. Our Social-UCB algorithm, presented in full pseudocode, provably yields logarithmic regret and ensures stable exploitation via UCB-style bounds. In simulation experiments, Social-UCB consistently achieves higher cumulative social fitness and more efficient network connectivity than baseline heuristics. We include detailed descriptions of envisioned figures and tables (e.g. network evolution plots, model comparisons) to illustrate key phenomena. This integrated model bridges gaps in the literature by unifying exploration-exploitation dynamics, network evolution, and social learning, offering a rigorous new tool for studying adaptive human social behavior.