Edge computing enables low-latency services by deploying application instances near users. Application vendors tend to serve more users with higher service satisfaction and a limited budget. This raises a critical yet open problem - optimally deploying application instances and allocating users to edge servers to maximize service utility while fulfilling multiple constraints, including user latency requirements, budget limitations, and edge resource constraints. To address this problem, we formulate it as a constrained optimization problem that jointly solves two tightly coupled sub-problems:ApplicationDeployment andUserAllocation (named as ADUA problem). The objective is to maximize overall service utility by optimizing resource utilization and service satisfaction under latency, budget, and resource constraints. We reformulate the ADUA problem as a multi-armed bandit (MAB) problem and then propose a novel approach namedUMESPbased on penalized MAB framework. Specifically, we design a marginal utility–aware reward function to align bandit learning with the optimization objective. We introduce a penalty mechanism to effectively handle constraint violations. By further integrating the upper confidence bound policy,UMESPachieves adaptive and constraint-aware balance between exploration and exploitation. Theoretical analysis demonstrates thatUMESPachieves bounded regret. Extensive experiments verify thatUMESPexhibits stable convergence in all tests and, on average, outperforms six representative approaches in overall service utility.