Balancing fairness: learning with conflicting objectives and user feedback

Large-scale learning systems are often evaluated across multiple, sometimes conflicting, objectives. How can we effectively learn and optimize such complex systems with potentially incompatible goals? Moreover, how do we improve these systems when user feedback, potentially highlighting previously unaddressed issues, becomes available? We propose a novel theoretical model for learning and optimizing such systems. Instead of relying on a static or predefined trade-off among objectives, our model dynamically adapts based on received feedback, updating its internal state accordingly. This approach accommodates multiple objectives in a general form, accounting for their potential incompatibilities. We explore both stochastic and adversarial settings. In the stochastic setting, we demonstrate that our framework can be naturally formulated as a Markov Decision Process with stochastic losses, for which we provide efficient algorithms that achieve vanishing regret. In the adversarial setting, we design algorithms with competitive ratio guarantees. Finally, we report a series of experimental results validating the effectiveness of our stochastic algorithms.