Increasing automation requires open, distributed, service-oriented systems capable of multicriteria-driven, dynamic adaptation for appropriate response to changing operating conditions. We combine a simple architecture with a novel algorithm to enable openness, distribution, and multi-criteria-driven service composition at runtime. The service-oriented architecture involves mediator web services coordinating other web services into compositions necessary to fulfil user requests. By basing mediator services' behavior on a novel multicriteria-driven (including quality of service, deadline, reputation, cost, and user preferences) reinforcement learning algorithm, which integrates the exploitation of acquired knowledge with optimal, undirected, continual exploration, we ensure that the system is responsive to changes in the availability of web services. The reported experiments indicate the algorithm behaves as expected and outperforms two standard approaches.