Given an average strain, rigorous bounds are established for the stress in a deformation of a plastic composite material, which follows a power law. The deformation theory of strain gradient plasticity, which introduces an internal material length scale, is used. It falls into the classical deformation theory of elasto-plasticity when this length scale equals zero. The method employs the idea by Milton and Serkov [J. Mech. Phys. Solids, 48 (2000), pp. 1259-1324] and other techniques for bounding effective energy. We derive two stress bounds which closely relate to the Reuss lower bound and the Hashin-Shtrikman upper bound for the energy. We then study numerically the dependence on the internal length scale of the magnitude of the stress and the region in the stress space determined by these two bounds in which the macro stress must lie. The results confirm the prediction made by Fleck and Willis [J. Mech. Phys. Solids, 52 (2004), pp. 1855-1888] for the macroscopic uniaxial response by differentiating their energy bounds.