Adaptive wireless channel allocation in a multi-user environment based on quality of received video streams. During the transmission of encoded media streams from a wireless access device to at least first and second video devices over a wireless channel, transmission windows are allocated in shared transmission frame intervals for transmission of media packets to the first and second video devices, respectively. Relative priorities are set/adjusted for the video devices based, at least in part, on one or more of the following: channel estimation information, reception characteristics, transmission acknowledgment information, video device characteristics and/or user feedback. The relative priorities are utilized to adaptively (re)allocate at least one portion of the transmission frame intervals. In addition to channel reallocation, the prioritization of devices may be utilized to adaptively alter the encoding bit rate of one or more media streams.