We consider a group of several non-Bayesian agents that can fully coordinat
e their activities and share their past experience in order to obtain a joi
nt goal in face of uncertainty. The reward obtained by each agent is a func
tion of the environment state but not of the action taken by other agents i
n the group. The environment state (controlled by Nature) may change arbitr
arily, and the reward function is initially unknown. Two basic feedback str
uctures are considered. In one of them - the perfect monitoring case - the
agents are able to observe the previous environment state as part of their
feedback, while in the other - the imperfect monitoring case - all that is
available to the agents are the rewards obtained. Both of these settings re
fer to partially observable processes, where the current environment state
is unknown. Our study refers to the competitive ratio criterion. It is show
n that, for the imperfect monitoring case, there exists an efficient stocha
stic policy that ensures that the competitive ratio is obtained for all age
nts at almost all stages with an arbitrarily high probability, where effici
ency is measured in terms of rate of convergence. It is also shown that if
the agents are restricted only to deterministic policies then such a policy
does not exist, even in the perfect monitoring case.